Nacházíte se na starých stránkách ústavu, navštivte prosím uai.fme.vutbr.cz

Popis vyučovacího předmětu

CZ Verze pro tisk

Teorie grafů (VTG)


Garant: prof. RNDr. Ing. Miloš Šeda, Ph.D.


Anotace:

Předmět je úvodem do teorie grafů a seznamuje studenty s jeho základními pojmy. Zabývá se následujícími tématy: Reprezentace grafu v počítači. Časová složitost algoritmů. Datové struktury pro grafové algoritmy binární halda, disjunktní množiny, ...). Eulerovské tahy, hamiltonovské cesty. Prohledávání grafů (do šířky, do hloubky), backtracking, metoda větví a mezí. Souvislost a dosažitelnost. Nejkratší cesty. Síťové grafy. Stromy a kostry. Steinerovy stromy. Základy počítačové geometrie, Voronoiovy diagramy a Delaunayho triangulace. Toky v sítích. Barvení grafů. Párování v grafech.

Studijní opory:

1.Graph Theory (prof. RNDr. Ing. Miloš Šeda, Ph.D.)
HTTP://uai.fme.vutbr.cz/seda/teorie-grafu

©2004-2013 ÚAI FSI