Předmět Graph Theory (KID / PXTGE)

Na serveru studentino.cz naleznete nejrůznější studijní materiály: zápisky z přednášek nebo cvičení, vzorové testy, seminární práce, domácí úkoly a další z předmětu KID / PXTGE - Graph Theory, Dopravní fakulta J. Pernera, Univerzita Pardubice (UPa).

Materiál	Typ	Datum	Počet stažení

Obsah

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.

Získané způsobilosti

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í.

Literatura

Christofides, N.:. Graph Theory - an Algorithmic Approach. New York: Academic Press, 1975. ISBN 0-12-174350-0.Volek, J. Operační výzkum I, skripta DFJP. Pardubice, 2002. ISBN 80-7194-410-6.Demel, J. Grafy a jejich aplikace. Academia, 2002. Nečas, J. Grafy a jejich použití. Polytechnická knižnice, SNTL, 1978. Tutte, W. T. Graph Theory. Addison-Wesley Publishing Company, 1984. ISBN 0-521-30241-2.Sedláček, J. Kombinatorika v teorii a praxi. Nakladatelství ČSAV, 1964. Bertsekas, D. P. Network Optimization - Continuous and Discrete Models. Belmont: Athena Scientific, 1998. ISBN 1-886529-02-7.Nešetřil, J. Teorie grafů. SNTL, 1979.

Požadavky

Podmínkou k udělení zápočtu je úspěšné absolvování dvou praktických testů v průběhu semestru.

Garant

Ing. Filip Vízner, Ph.D.

Vyučující

Ing. Filip Vízner, Ph.D.Ing. Filip Vízner, Ph.D.