FPF:UIDI012 Graphs and Graph Algorithms - Course Information
UIDI012 Graphs and Graph Algorithms
Faculty of Philosophy and Science in OpavaSummer 2007
- Extent and Intensity
- 0/0. 0 credit(s). Type of Completion: dzk.
- Guaranteed by
- doc. RNDr. Luděk Cienciala, Ph.D.
Institute of Computer Science – Faculty of Philosophy and Science in Opava - Course Enrolment Limitations
- The course is also offered to the students of the fields other than those the course is directly associated with.
- fields of study / plans the course is directly associated with
- Autonomous Systems (programme FPF, P1801 Inf)
- Course objectives (in Czech)
- Grafy a podgrafy. Grafy a jednoduché grafy, izomorfismus grafů. Podgrafy, stupeň vrcholu. Incidenční matice a matice sousednosti. Cesty a cykly. Důležité třídy grafů. Souvislé a nesouvislé grafy. Kompletní grafy, bipartitní a multi-partitní grafy. Stromy, kostra grafu. Vrcholová a hranová souvislost grafů. Hranové a vrcholové barvení grafu. Hranové barvení, chromatický index grafu, Vizingova věta. Vrcholové barvení, chromatické číslo grafu. Brooksova věta. Rovinné a planární grafy. Reprezentace grafů - graficky, maticově, seznamem hran nebo seznamem vrcholů a jejich sousedů; volba reprezentace grafu v závislosti na aplikaci. Algoritmy prohledávání grafů. Topologické uspořádání vrcholů a hran - užití topologického uspořádání k hledání nejkratších cest; test acykličnosti grafu. Komponenty souvislostí; 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. 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. 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.
- Language of instruction
- Czech
- Further Comments
- The course can also be completed outside the examination period.
- Enrolment Statistics (Summer 2007, recent)
- Permalink: https://is.slu.cz/course/fpf/summer2007/UIDI012