english
Teorie grafů
- Kód předmětu:
- 11Y1TG
- Studium:
- bakalářské
- Studijní program:
-
Technika a technologie v dopravě a spojích (B1041A040001)
semestr jazyk obor / specializace 4 
DOS Dopravní systémy a technika - B-DOS 4 ITS Inteligentní dopravní systémy - B-ITS 4 LED Letecká doprava - B-LED 4 LOG Logistika a řízení dopravních procesů - B-LOG - Forma studia:
- prezenční
- Počet kreditů:
- 2
- Rozsah výuky:
-
2 + 0 hodin týdně - v prezenční formě studia
- Typ předmětu:
- povinně volitelný
- Zakončení:
- klasifikovaný zápočet (kz)
- Garantující ústav:
- Ústav aplikované matematiky (16111)
- Klíčová slova:
- Ohodnocený graf, algoritmus, minimální kostra, nejkratší dráha, maximální tok, cirkulace, kritická cesta, bipartitní graf.
- Anotace:
- Základní grafové pojmy, formalizace popisu grafů, způsoby reprezentace grafu. Úlohy teorie grafů, instance, zadání. Prohledávání grafu, minimální kostra grafu, stromy, nejkratší dráha, Eulerovské tahy, párování v bipartitních grafech, toky v sítích, cirkulace, kritická cesta, úloha obchodního cestujícího. Algoritmy řešení existenčních a optimalizačních úloh. Výpočetní složitost, přístup k řešení NP-těžkých úloh, heuristické postupy.
- Cíle:
- Student prohloubí své znalosti z teorie grafů. Seznámí se se základními pojmy a problémy z oblasti algoritmizace úloh. Setká se s klasickými úlohami teorie grafů a algoritmy pro jejich řešení. Nahlédne do problematiky časové náročnosti a efektivity algoritmů.
- www stránky předmětu
- http://www.fd.cvut.cz/department/k611/PEDAGOG/K611YTG.htm
aktualizováno 2.3.2022
Vyjádření podpory zaměstnancům a studentům s ohledem na situaci na Ukrajině
Vážené kolegyně, vážení kolegové, studentky a studenti,
na stránkách fakulty jsme se přidali k vyjádření AS ČVUT a odsoudili vojenskou agresi Ruské federace na území svrchovaného státu Ukrajina. Rád bych ale nabídl i konkrétní pomoc. Pokud byste se v souvislosti s kritickou situací na území Ukrajiny dostali do složité životní situace, která by ovlivňovala vaše studijní nebo pracovní povinnosti na fakultě, neváhejte se obrátit buď na studijní oddělení nebo vedoucího vašeho pracoviště. Jsme připraveni podat pomocnou ruku každému jednomu z Vás.
Buďme solidární a jednotní! Věřme, že tento neomluvitelný zásah Ruské federace na území svrchovaného státu Ukrajina brzy skončí a Evropa bude opět svobodným a mírovým kontinentem.
S pozdravem,
Ondřej Přibyl
Další informace (stanovisko rektora a vedení ČVUT, příkaz rektora, atd) naleznete na stránkách ČVUT .
Návod k používání kalendářů 