|
Vyučující
|
-
Rak Josef, RNDr. Ph.D.
-
Pozdílková Alena, Mgr. Ph.D.
|
|
Obsah předmětu
|
Lecture topics by week of the semester: 1. Základní pojmy (základní pojmy z teorie grafů - neorientovaný a orientovaný graf, podgraf, nadgraf, doplněk grafu, speciální, historické poznámky, poznatky a úlohy vedoucí ke vzniku teorie grafů, typy grafů) 2. Maticová reprezentace grafů (datové struktury pro uložení grafů, matice přilehlosti, incidence a matice přímých vzdáleností) 3. Souvislost grafů (souvislost grafů, komponenta souvislosti, most, artikulace, číslo vrcholové a hranové souvislosti) 4. Izomorfismus (izomorfismus grafů, autokomplementární grafy) 5. Prohledávání labyrintu (algoritmus prohledávání labyrintu) 6. Nejkratší cesta (Dijsktrův a Floydův algoritmus pro určení nekratší cesty v grafu a distanční matice) 7. Cesta s maximální kapacitou (řezová množina, řez, cesta s maximální kapacitou) 8. Maximální dráha (algoritmus na určení maximální dráhy grafu) 9. Metoda kritické cesty (znázornění projektu orientovaným grafem, metoda kritické cesty, kritická cesta) 10. Toky na sítích (toky na rovinné stíti, nejvýše položená dráha, Fordův-Fulkersonův algoritmus pro obecné sítě, algoritmus na přiřazení pracovníků ke strojům) 11. Stromy a kostra grafu (strom, les, izolovaný vrchol, excentricita vrcholu, síla vrcholu, poloměr stromu, průměr stromu, centrum a centroid stromu, kostra grafu, algoritmus na určení minimální kostry grafu) 12. Eulerovský tah (Eulerovský tah, uzavřený tah minimální délky, Fleuryho a Edmondsův algoritmus) 13. Barvení grafu (rovinný graf, podmínky rovinnosti grafu, barvení grafu) Obsah cvičení odpovídá výše uvedeným tématům přednášek.
|
|
Studijní aktivity a metody výuky
|
Monologická (výklad, přednáška, instruktáž), Metody samostatných akcí, Demonstrace, Nácvik dovedností
- Kontaktní výuka
- 52 hodin za semestr
- Domácí příprava na výuku
- 38 hodin za semestr
- Příprava na zápočet
- 30 hodin za semestr
- Příprava na zkoušku
- 30 hodin za semestr
|
|
Výstupy z učení
|
Cílem předmětu je seznámit studenty s matematickým aparátem, přístupy a metodami teorie grafů jako jednoho ze základních teoretických nástrojů operačního výzkumu.
Student po absolvování předmětu ovládá základní definice, metody a algoritmy teorie grafů. Je schopen formulovat vybrané úlohy dopravní praxe, sestavit grafický model, vypočíst řešení a toto potom interpretovat pro praktické využití.
|
|
Předpoklady
|
nespecifikováno
|
|
Hodnoticí metody a kritéria
|
Písemná zkouška, Didaktický test
Účast na přednáškách, aktivní účast na cvičeních. Zvládnutí zápočtového a zkouškového testu na hranici minimálně 50 procent.
|
|
Doporučená literatura
|
-
BALAKRISHNAN, V. K. Schaum's Outline of Theory and Problems of Graph Theory. Schaum's Outline Series. New York: McGraw-Hill, 1997. ISBN 0-07-005489-4.
-
DEMEL, Jiří. Grafy a jejich aplikace. Praha: Academia, 2002. ISBN 80-200-0990-6.
-
NEČAS, Jiří. Grafy a jejich použití. Polytechnická knižnice. Řada 2. Příručky, sv. 90. Praha: Státní nakladatelství technické literatury, 1978.
-
NEŠETŘIL, Jaroslav. Teorie grafů. Praha: Státní nakladatelství technické literatury, 1979.
-
VOLEK, Josef. Operační výzkum I. Vyd. 2., nezm. Pardubice: Univerzita Pardubice, 2008. ISBN 978-80-7395-073-6.
|