|
Vyučující
|
|
|
|
Obsah předmětu
|
Motivační přednáška. Historické poznámky, poznatky a úlohy vedoucí ke vzniku teorie grafů. Matematický aparát, množinový počet, základy kombinatoriky a teorie pravděpodobností. Základní pojmy a definice teorie grafů. Významné cesty na grafech. Cesta s maximální kapacitou, výpočet distanční matice (Floydova metoda). Informační, datové, komunikační a dopravní sítě. Toky na rovinných sítích. Definice řezové množiny, Ford -Fulkersonova věta. Toky v prostorových a intervalově ohodnocených sítích. Lokační analýza, Weber-Fermatův problém, Toriccelliho bod, spojitá a diskrétní lokace, lokace v grafech, alokace, atrakční obvody, typy lokačních úloh. Obsluha požadavků v uzlech a na hranách sítě. Kombinatorický charakter lokačních úloh. Iterativní algoritmus. Absolutní depo, p- centrum, p- medián. Hakimiho věta a algoritmus. Konstrukční úlohy na grafech, eulerovské tahy a hamiltonovské kružnice, Fleuryho algoritmus, Edmondsův algoritmus. Littlův algoritmus. Rovinné grafy, Kuratowského věta, homeomorfismus grafů, barvení grafů. Orientované grafy, síťová analýza, Critical Path Method. Programme Evaluation and Review Technique.
|
|
Studijní aktivity a metody výuky
|
|
Monologická (výklad, přednáška, instruktáž), Demonstrace, Projekce, Nácvik dovedností
|
|
Výstupy z učení
|
The main goal of the discipline is to familiarise students with the basic mathematical apparatus and terminology of Theory of Graphs as one of the basic disciplines of operational research, acquaint them with approaches and clarify methods and their applications in transportation, communication and information systems.
Po absolvování předmětu student 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
|
Předpokládají se základní znalosti konečné matematiky, teorie množin a matematického programování.
|
|
Hodnoticí metody a kritéria
|
Ústní zkouška, Písemná zkouška
Podmínkou k udělení zápočtu je úspěšné absolvování dvou praktických testů v průběhu semestru.
|
|
Doporučená literatura
|
-
Bertsekas, Dimitri P. Network optimization : continuos and discrete models. Belmont: Athena Scientific, 1998. ISBN 1-886529-02-7.
-
Demel, J. Grafy a jejich aplikace. Academia, 2002. ISBN 80-200-0990-6.
-
Christofides, N.:. Graph Theory - an Algorithmic Approach.. New York: Academic Press, 1975. ISBN 0-12-174350-0.
-
Nečas, J. Grafy a jejich použití. Polytechnická knižnice, SNTL, 1978.
-
Nešetřil, J. Teorie grafů. SNTL, 1979.
-
Sedláček, J. Kombinatorika v teorii a praxi. Nakladatelství ČSAV, 1964.
-
Tutte, W. T. Graph Theory. Addison-Wesley Publishing Company, 1984. ISBN 0-521-30241-2.
-
Volek, Josef. Operační výzkum I. Pardubice: Univerzita Pardubice, 2002. ISBN 80-7194-410-6.
|