Předmět je základní jednotka výuky, jejímž prostřednictvím si student osvojí ucelenou část souboru znalostí a dovedností, potřebnou pro zvládnutí studijního oboru/specializace. Za věcný obsah předmětu zodpovídá garant předmětu. Časovou náročnost předmětu zhruba vyjadřuje atribut předmětu rozsah kontaktní výuky. Například rozsah = 2+2  značí, že předmět bude mít týdně dvě hodiny přednášek a dvě hodiny cvičení týdně. Na závěr semestru musí vyučující provést vyhodnocení, nakolik si ten který student osvojil poznatky a dovednosti, kterých měl během výuky nabýt. Jakým způsobem toto hodnocení vyučující provedou určuje atribut způsob zakončení. U předmětu lze definovat, že předmět je zakončen pouze zápočtem(Z), klasifikovaným zápočtem(KZ), pouze zkouškou(ZK), nebo zápočtem a zkouškou(Z,ZK). Náročnost úspěšného absolvování předmětu je vyjádřena ECTS kreditními body. Výuka předmětu probíhá během semestru. Opakovaně se předmět vyučuje vždy v zimním(Z), nebo v letním(L) semestru každého akademického roku. Výjimečně může předmět být nabízen studentům v obou semestrech(Z,L). Za organizační zajištění výuky zodpovídá přiřazená katedra, která zejména vytvoří časový rozvrh předmětu a zajistí pro předmět vyučující. Někteří přednáší a zkouší, jiní vedou cvičení a udělují zápočty.
Obsahová náplň a další organizační informace, týkající se předmětu je popsána pomocí různých popisných textů(anotace, týdenní osnova, literatura, apod.)
$DODATEK_POPIS

Anotace:
Studenti získají základní přehled o používání grafových modelů v informatice, se zaměřením především na algoritmické otázky a řešení grafových problémů. Zahrnuta jsou rovněž další témata, která tento přehled doplňují o specifické aplikace nebo postupy (toky v sítích, heuristické hledání, aproximační algoritmy) nebo se týkají obecnější problematiky algoritmické řešitelnosti a složitosti úloh (Turingovy stroje, NP úplné problémy).

Osnovy přednášek:

1.		Grafové modely, neorientované grafy, izomorfismus. Sousednost, souvislost, orientované grafy.
2.		Silná souvislost, acyklické grafy, reprezentace grafů, procházení do šířky. Procházení do hloubky, topologické uspořádání, silně souvislé komponenty.
3.		Eulerovy grafy, dominující a nezávislé podmnožiny, barevnost, vzdálenost. Stromy, kostry, kružnice, minimální kostry.
4.		Nejkratší cesty, algoritmy hledání nejkratších cest 1 -> n. Algoritmy hledání nejkratších cest n -> n, planarita.
5.		Toky v sítích, určení maximálního toku v síti. Nejlevnější cirkulace, párování, řešení přiřazovací úlohy.
6.		Stavový prostor úloh, prohledávání, heuristické hledání. Turingovy stroje.
7.		Třídy složitosti, NP-úplné problémy. Aproximační algoritmy.

Osnovy cvičení:

1.		Indukce, rekurze, rekurence Druhy stromů a jejich reprezentace, procházení stromů. Vlastnosti grafů (izomorfismus, souvislost, komponenty, stupně uzlů). Silná souvislost, rozklad na silné komponenty, topologické uspořádání. Reprezentace a procházení grafu, použití. Určení Eulerova tahu, úloha čínského listonoše, zadání semestrální práce. Určování charakteristik (nezávislost, dominance, barevnost, cyklomatické číslo).
2.		Stromy, kostry a minimální kostry. Nejkratší cesty. Nejkratší cesty, planarita, konzultace k semestrální úloze. Maximální tok v síti, cirkulace, párování. Algoritmy heuristického hledání. Turingovy stroje.

Literatura:
Kolář, J. ''Teoretická informatika''. Praha: Česká informatická společnost, 2000. ISBN 80-900853-8-5. Demel, J. ''Grafy a jejich aplikace''. Praha: Academia, 2002. ISBN 80-200-0990-6. Kolář, J. ''Theoretical Computer Science''. Praha: ČVUT, 1998. ISBN 80-01-01788-5. Cormen, T. H., Leiserson, C. E., Rivest, R. L. ''Introduction to Algorithms''. The MIT Press, 2001. ISBN 0262032937. Sedgewick, R. ''Algorithms in Java, Part 5: Graph Algorithms (3rd Edition)''. Addison-Wesley Professional, 2003. ISBN 0201361213.

Požadavky:
Předpokládá se znalost základních abstraktních datových typů, jejich efektivní implementace a použitelnost při řešení grafových problémů na úrovni předmětu BI-EFA. Studenti by měli pasivně zvládat základní důkazové postupy známé z povinných matematických předmětů (důkaz úplnou indukcí, důkaz sporem, konstruktivní důkaz) a vedle návrhu nového či modifikace známého algoritmu by měli být schopni provést jeho analýzu složitosti.

Informace o předmětu a výukové materiály naleznete na https://courses.fit.cvut.cz/BI-FIP/ https://courses.fit.cvut.cz/BI-GRA/ Opozdicům: Dvojici předmětů EFA + GRA lze uznat, jestliže student úspěšně absolvuje dvojici předmětů AG1 + AG2. Student o to může požádat na studijním oddělení. Student, kterému chybí předmět GRA si musí zapsat předmět AG2 a podrobit se rozdílové zkoušce. Opakujícím studentům, kterým byl uznán předmět GRA, si musí zapsat předmět AG2 a požádat u uznání zápočtu.

Předmět je zahrnut do těchto studijních plánů:

Plán Obor Role Dop. semestr BIK-BIT.2015 Bezpečnost a informační technologie V 4 BIK-BIT.2020 Bezpečnost a informační technologie V 4 BIK-SPOL.2015 Nespecifikovaný/á obor/specializace studia - Unspecified Branch/Specialisation of Study VO 4 BIK-WSI-SI.2015 Webové a softwarové inženýrství V 4