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

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)