Teorie grafů (1763- 1963)

OBSAH
Úvod . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
Definice základních pojmů . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
1 Cesty v grafech . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
1.1 Eulerovské tahy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .13
1.1.1 Problém k¨onigsberský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
2
4 Faktorizace grafů . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70
4.1. Rozklady grafů . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70
4.1.1 Problém čtyř barev . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70
4.1.2 Petersenova věta . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71
4.1.3 Další důkaz Petersenovy věty . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76
4.1.4 Rozklady bipartitních grafů . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .77
4.2 Vývoj po roce 1936 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79
4.2.1 Kritérium existence lineárního faktoru . . . . . . . . . . . . . . . . . . . . . . . 79
4.2.2 Pravidelné faktory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .81
4.3. Práce Antona Kotziga . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82
4.3.1 O istých rozkladoch grafu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .82
4.3.2 Poznámky k Listingovej vete o rozklade grafu
na otvorené ťahy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83
4.3.3 Rozklad konečného pravidelného grafu nepárného stupňa
na dva faktory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84
4.3.4 Eulerovské čiary a rozklady pravidelného grafu párného
stupňa na dva faktory rovnakého stupňa . . . . . . . . . . . . . . . . . . . 84
4.3.5 Z teorie konečných pravidelných grafov tretieho
a štvrtého stupňa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84
4.3.6 Súvislosť a pravidelná súvislosť konečných grafov . . . . . . . . . . .85
4.3.7 Poznámka k rozkladom konečných párných pravidelných
grafov na lineárné faktory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86
4.3.8 O rovnovážne orientovaných konečných grafoch . . . . . . . . . . . . 87
4.3.9 Z teórie konečných grafov s lineárnym faktoreom I, II, III . . 87
4.3.10 Postrojenije gamiltonovskich grafov treťjej stěpeni . . . . . . . . 90
5 Orientované grafy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91
5.1 Definice základních pojmů . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91
5.2 Cesty v orientovaných grafech . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .92
5.3 Báze . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97
5.4 Matice . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .99
Doslov – Bohdan Zelinka: A jak to bylo dál . . . . . . . . . . . . . . . . . . . . . . 101
Příloha 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106
Příloha 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 146
Literatura . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 159