Bakalářská státnice - Teorie grafů

Z ωικι.matfyz.cz
Přejít na: navigace, hledání
bc. Informatika
Okruh požadavků Základy matematiky
Tato stránka není kompletní a/nebo může obsahovat chyby!

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)