Harjutustund nr 4

Graafid

Vajalikud graafi mõisted - kas mäletad, mis on mis? Küsi, mida ei mäleta!
- Orienteerimata graaf ning orienteeritud ehk suunatud graaf
- Tee ehk ahel
- Tsükkel
- Suunatud atsükliline graaf
- Tipu naaber

Ülesanne 1 Lihtsalt graaf
Järgnevad punktid võib joonistada ja kirjutada paberile. Võib ka proovida arvutis pusida. Külgnevusahelate joonistamine on paberil vast mugavam. Kõik nimetatud failid leiad tabelist ühe lingi alt.
Failis graafike.txt on esitatud graaf järgmiselt:
esimeses reas on kirjas tippude arv ja järgmistel ridadel kaared oma alguse ja lõputipuga, näiteks 2 3 tähendab, et tipust 2 läheb kaar tippu 3.
1. Joonista kirjelduse järgi graaf. Arvesta, et graaf on orienteeritud. Failis graaf_harjutustunnis.odg on olemas tipud, millega oma elu lihtsustada (juhul kui joonistad arvutis). 
2. Esita sama graaf külgnevus- ehk naabrusmaatriksina.
3. Joonista sama graaf külgevusahelloenditena.
4. Kas graafis on tsükleid? Mitu tükki leiad?
5. Millised naabrid on tipul 9?


Ülsanne 2 Topoloogiline sorteerimine.
Vaatame üle loengumaterjalis oleva näite.

Failis graaf_topo.txt on suunatud atsüklilise graafi kirjeldus. Joonista see graaf välja ja sorteeri topoloogiliselt.
Tekita vähemalt 2 erinevat tippude järgnevust.

Ülesanne 3 Laiuti otsing
Räägime algoritmi põhimõttest koos tabelite koostamisega.

Ülesande lahendamiseks kasuta Dijkstra algoritmi graafi (fail BFS_ja_Dijkstra_harjutus.pdf (.odg)), kuid ei arvesta kaartele kaale.
Teeme koos läbi alguse ja kodus lõpeta.
Peale laiuti otsingu tabelite moodustamist leia nende alusel lühim tee tipust A tippu G.

Kas sama tabeli alusel saab leida ka lühima tee tipust E tippu D? 
Kas samamoodi saab teha laiutiotsimist ka suunamata graafis?