Grafy (FIIT)

2006/07 Letný semester

Vyučujúci

• Doc. RNDr. Jana Galanová, PhD., jana.galanova@stuba.sk

Stručná osnova predmetu

Grafy a ich reprezentácia.Rôzne typy súvislosti grafov.Grafy relácií.Eulerovské grafy.Bludiskový algoritmus na nájdenie eulerovského ťahu. Problém čínskeho poštára.Hamiltonovské grafy. Problém obchodného cestujúceho.Algoritmy na nájdenie najkratšej cesty v grafe.Problém plánovania činnosti. Metóda kritickej cesty(CPM).Siete.Rez v grafe. Maximálmy tok v sieti. Maximálna cirkulácia.Stromy. Algoritmy na nájdenie minimálnej kostry grafu.Rozhodovacie stromy.Priraďovacie úlohy.Párovanie.Algoritmus na maximálne párovanie. Petroho siete ako model pre konkurujúce si procesy.

Literatúra

==1.Demel, J.: Grafy, SNTL, Praha,1989, 2000== ==2.Plesník, J.: Grafové algoritmy, VEDA, Bratislava 1983== ==3.Harary, F.: Graph Theory. Reading, Addison-Wesley 1969==

Podmienky na zápočet

==1.Účasť na prednáške a cvičení je predpokladom pre úspešné zvládnutie predmetu.== ==2.Na 2 testoch počas semestra je možné získať maximálne 30 bodov.== ==3. Zápočet získava študent s 15 - 30 bodmi získanými počas semestra.== ==4. Skúška je písomná. Pozostáva z teoretických otázok a príkladov.== ==5. Hodnotenie skúšky pozostáva zo súčtu bodov získaných počas semestra a na skúške.== ==6. Výsledná známka zodpovedá platnej stupnici známok. ==

Príklady a cvičenia

Príklady a cvičenia: attachment:priklady.pdf

Výsledky

Paralelka XY

[attachment:vysledky_A.xls Tuto je popis súboru s výsledkami]

Paralelka UV

[attachment:UV.xls Nejaký iný súbor]