|
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í
|
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.
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 aktivní účast na cvičeních a splnění zápočtového testu. Předmět je zakončen zkouškou. Aktivní účast lze nahradit vypracováním samostatné práce. Zápočtový test může být proveden elektronicky.
|
|
Doporučená literatura
|
-
Demel, Jiří. Grafy a jejich aplikace. Praha: Academia, 2002. ISBN 80-200-0990-6.
-
Nečas, Jiří. Grafy a jejich použití. Praha: Státní nakladatelství technické literatury, 1978.
-
Nešetřil, Jaroslav. Teorie grafů. Praha: Státní nakladatelství technické literatury, 1979.
-
Sedláček, Jiří. Kombinatorika v teorii a praxi : úvod do teorie grafů. Praha: Československá akademie věd, 1964.
-
V. Balakrishnan. Schaum's Outline of Graph Theory: Including Hundreds of Solved Problems.
-
Volek, Josef. Operační výzkum I. Pardubice: Univerzita Pardubice, 2002. ISBN 80-7194-410-6.
|