Tartalom
Elõszó a második
kiadáshoz i
Elõszó iii
Bevezetõ
jelölések v
1. Gráfelméleti
alapfogalmak 1
1.1. Bevezetõ
példák 1
1.2. Egyszer gráfok 2
1.3. Részgráfok, izomorfizmus,
példák 6
1.4. Gráfok 12
1.5. Séta, vonal, út 15
1.6. Mveletek gráfokkal 18
1.7. Irányított gráfok 21
1.8. Páros gráfok 25
1.9. Síkgráfok 27
1.10. Fokszámok 27
2.
Összefüggõség 31
2.1.
Összefüggõség 31
2.2. Távolság 34
2.3. Minimális összefüggõ
gráfok, fák 37
2.4. Minimális költség
feszítõfa 43
2.5. Mohó algoritmusok 47
2.6. Feszítõfák száma 50
2.7. Elektromos hálózatok elmélete 55
2.8. Irányított gráfok
összefüggõsége 63
2.9. Kétszeresen élösszefüggõ
gráfok 68
2.10. Kétszeresen összefüggõ
gráfok 73
2.11. k-szorosan
élösszefüggõ és k-szorosan
összefüggõ gráfok 78
2.12. Folyamok 80
2.13. Általánosított
folyamprobléma 89
2.14. A folyamok és a lineáris
programozás kapcsolata 93
3.
Párosítások 97
3.1. Történeti
megjegyzések 97
3.2. Páros gráfok
párosításai 98
3.3. Alkalmazások 101
3.4. Javító utak 103
3.5. Magyar módszer 105
3.6. Páros gráfok
párosításainak lineáris programozási
értelmezése 110
3.7. Véletlen számokat használó
algoritmusok 114
3.8. Tutte és Berge tételei 118
3.9. Edmonds párosítási algoritmusa 122
3.10. Gallai---Edmonds-struktúratétel 130
3.11. További struktúratételek 134
3.12. Teljes párosítások száma
páros gráfokban, permanens 134
3.13. Párosítások száma,
párosítási polinom 137
4. Vonalak, körök és
utak 143
4.1. Euler-vonal 143
4.2. A kínai postás problémája
148
4.3. Hamilton-utak, Hamilton-körök 151
4.4. Az utazó ügynök
problémája 154
5. Független
ponthalmazok 159
5.1. Alapfogalmak 159
5.2. Mohó algoritmus 161
5.3. Rangbecslés 165
5.4. Pontpakolási politóp és
lineáris programozási módszerek 166
5.5. Élfeltételek 167
5.6. Rangfeltételek 168
6. Gráfok
színezése 169
6.1. Bevezetés 169
6.2. Színezhetõség kevés
színnel 173
6.3. Mohó színezési algoritmus 174
6.4. Átszínezést alkalmazó
színezési algoritmusok,
Kempe-átszínezés 183
6.5. Gráfok kromatikus száma és
maximális fokszáma közötti
összefüggés 187
6.6. Háromszöget nem tartalmazó,
nagy kromatikus számú gráfok 188
6.7. Hadwiger-sejtés 190
6.8. Nem k-színezhetõ
gráfok
karakterizációja, Hajós tétele 191
6.9. k-színezések
száma,
kromatikus polinom 193
6.10. Élszínezések 194
7. Extremális
gráfelmélet 199
7.1. Az
alapkérdés 199
7.2. Turán tétele 201
7.3. Erdõs---Stone-tétel 205
7.4. Négyszögeket nem tartalmazó
gráfok 205
7.5. További kérdések 207
7.6. Alkalmazások 208
7.7. Extremális kérdések rendezett
struktúrákra 210
7.8. Topologikus részgráfokra
vonatkozó extremális kérdések
215
8.
Ramsey-elmélet 219
8.1. Ramsey-típusú
tételek 219
8.2. Felsõ becslések a
Ramsey-számokra 220
8.3. Alsó becslések a
Ramsey-számokra,
valószínségszámítási
módszer 223
8.4. Ramsey tételének geometriai
alkalmazásai 225
8.5. Ramsey tételének algebrai
alkalmazásai 227
9. Gráfelméleti
problémák ekvivalenciája 229
9.1. Gráfproblémák
redukciói 229
9.2. Gráfosztályok 238
9.3. Páros gráfok 240
10.
Síkgráfok 243
10.1. Síkra
rajzolhatóság 243
10.2. Dualitás 247
10.3. Euler tétele és
következményei 249
10.4. Topologikus részgráfok, minorok 252
10.5. Nem síkgráfok
karakterizációja 255
10.6. Adott felületre nem rajzolható
gráfok karakterizációja 258
10.7. Gráfok génusza 259
10.8. Síkgráfok színezése 259
10.9. Hadwiger-sejtés 261
11. Perfekt
gráfok 265
11.1. Alapfogalmak,
példák 265
11.2. Perfekt gráfok
karakterizációja 266
11.3. Perfektgráf-tétel 267
11.4. Gráfosztályok, amelyek tagjai
perfektek 270
11.5. Független ponthalmazok,
pontpakolási politóp 272
11.6. Univerzális gráfok 277
12. Vegyes
gráfosztályok 281
Jelölések 283
Név és
tárgymutató 295
Irodalomjegyzék 305