{{statnice|bc|Státnice|Informatika|Informatika|Bakalářská státnice - Informatika - Základy matematiky|Základy matematiky}}
{{Not_complete}}

# Základní pojmy teorie grafů, reprezentace grafu. #

* Definice grafu. (zdroj: Kapitoly z diskrétní matematiky, str. 96)
* Úplný graf, kružnice, cesta, úplný bipartitní graf. (zdroj: Kapitoly z diskrétní matematiky, str. 97-98)
* Isomorfizmus grafů. (zdroj: Kapitoly z diskrétní matematiky, str. 98)
* Počet neisomofrních grafů. (zdroj: Kapitoly z diskrétní matematiky, str. 99)
* Podgraf, indukovaný podgraf. (zdroj: Kapitoly z diskrétní matematiky, str. 101)
* Souvislost, komponenty grafu. (zdroj: Kapitoly z diskrétní matematiky, str. 103-104)
* k-souvislost grafu. (zdroj: Kapitoly z diskrétní matematiky, str. 132)
* Vzdálenost v grafu. (zdroj: Kapitoly z diskrétní matematiky, str. 104)
* Matice sousednosti. (zdroj: Kapitoly z diskrétní matematiky, str. 105)
* Skóre grafu. Princip sudosti. Věta o skóre grafu. (zdroj: Kapitoly z diskrétní matematiky, str. 113-114)
* Násobné hrany a smyčky. (zdroj: Kapitoly z diskrétní matematiky, str. 120-121)

# Stromy a jejich základní vlastnosti, kostra grafu. #

* Definice stromu. (zdroj: Kapitoly z diskrétní matematiky, str. 140)
* Koncový vrchol stromu (list). Postupná výstavba stromu. (zdroj: Kapitoly z diskrétní matematiky, str. 141)
* Charakterizace stromu (5 ekvivalentních tvrzení). (zdroj: Kapitoly z diskrétní matematiky, str. 141-142)
* Isomorfizmus stromů. (zdroj: Kapitoly z diskrétní matematiky, str. 144-145)
* Definice kostry grafu. (zdroj: Kapitoly z diskrétní matematiky, str. 150)
* Algoritmus na hledání kostry grafu. (zdroj: Kapitoly z diskrétní matematiky, str. 151 / Kapitoly z diskrétní matematiky, str. 154)
* Ohodnocení hran grafu. (zdroj: Kapitoly z diskrétní matematiky, str. 156)
* Problém minimální kostry. (zdroj: Kapitoly z diskrétní matematiky, str. 156)
* Kruskalův algoritmus (hladový) na hledání minimální kostry grafu. (zdroj: Kapitoly z diskrétní matematiky, str. 157)
* Jarníkův algoritmus na hledání minimální kostry grafu. (zdroj: Kapitoly z diskrétní matematiky, str. 161)
* Borůvkův algoritmus na hledání minimální kostry grafu. (zdroj: Kapitoly z diskrétní matematiky, str. 163)
* Cayleyho formule o počtu koster grafu (resp. počtu stromů na n vrcholech). (zdroj: Kapitoly z diskrétní matematiky, str. 221)

# Eulerovské a hamiltonovské grafy. #

* Sled v grafu. (zdroj: Kapitoly z diskrétní matematiky, str. 106)
* Tah. Uzavřený eulerovský tah. (zdroj: Kapitoly z diskrétní matematiky, str. 118)
* Charakterizace eulerovských grafů. (zdroj: Kapitoly z diskrétní matematiky, str. 118)
* Hamiltonovská kružnice. (zdroj: Kapitoly z diskrétní matematiky, str. 120)
* Algoritmus kreslení grafu jedním tahem. (zdroj: Kapitoly z diskrétní matematiky, str. 124)
* Eulerovské orientované grafy. (zdroj: Kapitoly z diskrétní matematiky, str. 128)

# Rovinné grafy, barvení grafů. #

* Oblouk. (zdroj: Kapitoly z diskrétní matematiky, str. 167)
* Nakreslení grafu. (zdroj: Kapitoly z diskrétní matematiky, str. 168)
* Rovinné nakreslení grafu a rovinný graf. Topologický rovinný graf. (zdroj: Kapitoly z diskrétní matematiky, str. 168)
* Stěny rovinného topologického grafu. (zdroj: Kapitoly z diskrétní matematiky, str. 169)
* Jordanova věta o kružnici. (zdroj: Kapitoly z diskrétní matematiky, str. 175)
* Stěny a kružnice v 2-souvislých grafech. (zdroj: Kapitoly z diskrétní matematiky, str. 178)
* Kuratowského věta. (zdroj: Kapitoly z diskrétní matematiky, str. 180)
* Eulerův vzorec pro rovinné grafy. (zdroj: Kapitoly z diskrétní matematiky, str. 181)
* Maximální počet hran rovinného grafu. (zdroj: Kapitoly z diskrétní matematiky, str. 185)
* Barevnost grafu. (zdroj: Kapitoly z diskrétní matematiky, str. 192)
* Duál grafu. (zdroj: Kapitoly z diskrétní matematiky, str. 192)
* Problém 4 barev. (zdroj: Kapitoly z diskrétní matematiky, str. 194)
* Věta o 5 barvách. (zdroj: Kapitoly z diskrétní matematiky, str. 195)

# Základní grafové algoritmy. #

* Dijstrův algoritmus na hledání nejkratší cesty v grafu. (zdroj: Kapitoly z diskrétní matematiky, str. 109-110)
* Algoritmus pro kreslení grafu jedním tahem. (zdroj: Kapitoly z diskrétní matematiky, str. 124)
* Algoritmus na hledání kostry grafu. (zdroj: Kapitoly z diskrétní matematiky, str. 151 / Kapitoly z diskrétní matematiky, str. 154)
* Problém minimální kostry. (zdroj: Kapitoly z diskrétní matematiky, str. 156)
* Kruskalův algoritmus (hladový) na hledání minimální kostry grafu. (zdroj: Kapitoly z diskrétní matematiky, str. 157)
* Jarníkův algoritmus na hledání minimální kostry grafu. (zdroj: Kapitoly z diskrétní matematiky, str. 161)
* Borůvkův algoritmus na hledání minimální kostry grafu. (zdroj: Kapitoly z diskrétní matematiky, str. 163)
* Topologické třídění (zdroj: Algoritmy a programovací techniky, od str. 143)