{{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)