Gráfelmélet

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