17.03.2011

Graafid ja graafialgoritmid

Leia vastused järgmisteel küsimustele:
1. Millistest osadest koosneb graaf? Mida tähendavad graafis kaared?
2. Mõisted suunatud graaf, suunamata graaf, kaalutud graaf.
3. Millised ahelad pakuvad graafiteoorias (ja praktilistes rakendustes) huvi?
4. Millised on kaks peamist graafi kõigi tippude läbimise algoritmi?
5. Milles seisnes Königsbergi sildade probleem ja kuidas seda esitada graafina?
6. Veel graafiprobleeme - milliseid nimesid leiad? Milliste ülesannete lahendamiseks nad sobivad?


Ülesanne 1 - Kobras
Lahenda siit ülesanne 8 - Kobras ja kaart
http://www.math.olympiaadid.ut.ee/kobras/Test.php?voistlus=8&grupp=2


Ülesanne 2 Kirjalik => vajalik paber ja pliiats!

1. 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 tippu 3
läheb kaar.
Võta see kirjeldus ja joonista endale selle järgi graaf.

2. Kirjuta sama graaf üles külgnevusmaatriksina.

3. Joonista see graaf paberile külgevusnimistuna.

4. Kas graaf on orienteeritud?

5. Kas graafis on tsükkel?

6. Leida tipuga 9 külgnevad tipud.

7. Kui graafis on tsükkel, siis muuda graafi selliselt, et tsükkel kaoks (täiesti omavoliliselt).

8. Eelmine ülesanne oli vajalik selleks, et sorteerida graafi tipud topoloogiliselt - tee seda.