Bakalářská státnice - Teorie grafů
Z ωικι.matfyz.cz
| bc. Informatika | ||
|
Tato stránka není kompletní a/nebo může obsahovat chyby!
Obsah
Základní pojmy teorie grafů, reprezentace grafu.[editovat | editovat zdroj]
- 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.[editovat | editovat zdroj]
- 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.[editovat | editovat zdroj]
- 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ů.[editovat | editovat zdroj]
- 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.[editovat | editovat zdroj]
- 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)
