456-0097/01 – Grafové algoritmy (GRA)
Garantující katedra | Katedra informatiky | Kredity | 4 |
Garant předmětu | RNDr. Eliška Ochodková, Ph.D. | Garant verze předmětu | RNDr. Eliška Ochodková, Ph.D. |
Úroveň studia | pregraduální nebo graduální | Povinnost | povinně volitelný |
Ročník | | Semestr | zimní |
| | Jazyk výuky | čeština |
Rok zavedení | 1997/1998 | Rok zrušení | 2003/2004 |
Určeno pro fakulty | FEI | Určeno pro typy studia | magisterské |
Cíle předmětu vyjádřené dosaženými dovednostmi a kompetencemi
Cílem předmětu je seznámit studenty se základními grafovými algoritmy, možnostmi jejich využití a problémy, které se mohou řešit pomocí těchto algoritmů.
Vyučovací metody
Anotace
Cílem předmětu je seznámit studenty s grafovými algoritmy,
možnostmi jejich využití a problémy, které se pomocí
těchto algoritmů mohou řešit.
Povinná literatura:
Sylaby předmětu.
Internetové zdroje.
Nešetřil J.: Teorie grafů, SNTL, Praha, 1979.
Plesník J.: Grafové algoritmy, VEDA, Bratislava, 1983.
Demel J.: Grafy, SNTL, Praha, 1989
McHugh J. A.: Algorithmic graph theory, PRENTICE HALL, 1990.
Unčovský L. a kol.: Modely sieťovej analýzy, ALFA, Bratislava, 1991.
Cormen T.H., Leiserson Ch.E., Rivest R.L.: Introduction to algorithms, The MIT Press, 1990.
Kučera L.: Kombinatorické algoritmy, SNTL Praha, 1991
Doporučená literatura:
Forma způsobu ověření studijních výsledků a další požadavky na studenta
E-learning
Další požadavky na studenta
Prerekvizity
Předmět nemá žádné prerekvizity.
Korekvizity
Předmět nemá žádné korekvizity.
Osnova předmětu
Přednášky:
Reprezentace grafů - graficky, maticově, seznamem hran nebo seznamem vrcholů a jejich sousedů; volba reprezentace grafu v závislosti na aplikaci.
Prohledávání grafů - základní algoritmus, prohledávání do šířky a do hloubky; zjišťování dostupnosti vrcholů.
Nejkratší cesty - základní algoritmus, modifikovaný alg., Bellman-Fordův algoritmus; úpravy algoritmů při hledání nejdelších cest.
Topologické uspořádání vrcholů a hran - užití topolog. uspořádání k hledání nejkratších cest; test acykličnosti grafu.
Souvislé a silně souvislé grafy. Komponenty souvislosti - pomocí mocnin matice sousednosti (jejich součtová matice); Floydův algoritmus - testování existence cyklů se zápornou cenou.
Kostra grafu - Jarníkův a Borůvkův algoritmus. Souvislost s nejkratšími cestami v neorientovaném grafu. Kruskalův a Primův algoritmus.
Tranzitivní uzávěr a tranzitivní redukce.
Párování v bipartitních grafech - maximální párování, nejlevnější párování v bipartitních grafech.
Maximální párování v obecných grafech - redukce grafu.
Eulerovské tahy - podmínky existence; algoritmus pro nalezení eulerova tahu v grafu (pokud existuje); úloha čínského pošťáka.
Vrcholové a hranové barvení grafu. Rovinné grafy.
Toky v sítích - maximální tok - ekvivalence úlohy maximálního párování v bipartitním grafu a maximálního toku v specifické síti; Ford-Fulkersonův algoritmus; přípustný tok v síti.
Nejlevnější cirkulace v síti.
Heuristické algoritmy - izomorfismus, kliky a nezávislé množiny, Hamiltonovský cyklus, úloha obchodního cestujícího.
Podmínky absolvování předmětu
Výskyt ve studijních plánech
Výskyt ve speciálních blocích
Hodnocení Výuky
Předmět neobsahuje žádné hodnocení.