Úvod . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . 5
Definice základních pojmů . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 11
1 Cesty v grafech . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . 13
1.1 Eulerovské tahy . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .13
1.1.1 Problém konigsberských mostů . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
1.1.2. Eulerovské grafy . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
1.2 Hamiltonovské kružnice . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
1.2.1 Úloha šachového jezdce . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . 21
1.2.2 Postačující podmínky existence hamiltonovské kružnice . . . . 23
1.2.3 Hamiltonovsky souvislé grafy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
2 Kostra grafu . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. 30
2.1 Stromy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . 30
2.2 Kostra grafu a fundamentální systém kružnic . . . . . . . . . . . . . . . . . . . . .33
2.2.1 Fundamentální systém kružnic . . . . .. . . . . . . . . . . . . . . . . . . . . . . . 33
2.2.2 Práce A. Kotziga . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . 35
2.3. Počet koster . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . 39
2.4. Minimální kostra grafu . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .41
2.4.1 Práce O. Borůvky . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
2.4.2 Příspěvek V. Jarníka . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . 43
2.4.3 Kruskalův algoritmus . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . 45
2.4.4 Primův-Dijkstrův algoritmus . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . .46
2.45. Některé další otázky . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . .48
3 Problém čtyř barev, barvení grafů, rovinné grafy . . . . . . . . . . . . . . . 51
3.1 Problém čtyř barev . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . 51
3.1.1 Vznik problému a Kempeho důkaz . . . . . . . . . . . . . . . . . . . . . . . . . 51
3.1.2. Práce P. J. Heawooda a L. W. J. Hefftera . . . . . . . . . . . . . . . . . 54
3.1.3. Práce amerických matematiků . . . . . . . . . . .. . . . . . . . . . . . . . . . . 57
3.1.4. Vyřešení problému . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . .59
3.1.5 Barvení uzlů . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . 61
3.2 Rovinné grafy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . 63