Gráfelméleti feladatok

Tartalom

Előszó 7
I. rész FELADATOK 9
1. Gráfelméleti alapfogalmak 11
1.1. Izomorfizmus 11
1.2. Fokszámsorozatok 12
1.3. Fák 13
1.4. Cayley-tétel, Prüfer-kód 14
1.5. Minimális súlyú feszítőfa 14
1.6. Összefüggőség 16
1.7. Irányított gráfok 16
1.8. Vegyes feladatok 17
2. Euler-körök, Euler-utak 19
2.1. Euler-bejárás létezése 19
2.2. Euler-bejárás alkalmazásai 21
2.3. A bejárás változatai 22
3. Hamilton-kör és Hamilton-út 25
3.1. Hamilton-körök és -utak megadása 25
3.2. Szükséges feltételek 26
3.3. Elégséges feltételek 28
3.4. Vegyes feladatok 30
4. Síkbarajzolhatóság 33
4.1. Euler-formula 33
4.2. Kuratowski-tétel, Fáry-Wagner-tétel 35
4.3. Dualitás 37
4.4. Gyenge izomorfia 38
4.5. Vegyes feladatok 39
4.6. A síkbarajzolhatóságnál általánosabb fogalmak 40
4.7. A síkbarajzolhatóságnál speciálisabb fogalmak 41
5. Párosítások 43
5.1. Maximális párosítás 43
5.2. Párosítás páros gráfban - Hali-feltétel 44
5.3. Vegyes feladatok 47
5.4. Lefogás és függetlenség 48
6. Folyamok, többszörös összefüggőség 53
6.1. Folyamok 53
6.2. Többszörös összefüggőség 58
7. Gráfok színezése 61
7.1. Csúcsok színezése 61
7.2. Elek színezése 65
7.3. Perfekt gráfok 66
7.4. Mycielski-konstrukció 67
7.5. Listaszínezés 67
8. Gráfok mátrixai 69
8.1. Szomszédossági mátrix 69
8.2. A szomszédossági mátrix determinánsa, sajátértékei 70
8.3. Illeszkedési mátrix 71
8.4. Körmátrix és vágásmátrix 72
9. Bonyolultságelmélet 75
9.1. Körök és utak 75
9.2. Színezések és klikkek 78
9.3. Eldöntési és keresési problémák 80
9.4. Vegyes feladatok 81
II. rész MEGOLDÁSOK 85
10. Gráfelméleti alapfogalmak 87
10.1. Izomorfizmus 87
10.2. Fokszámsorozatok 91
10.3. Fák 93
10.4. Cayley-tétel, Prüfer-kód 96
10.5. Minimális súlyú feszítőfa 98
10.6. Összefüggőség 100
10.7. Irányított gráfok 101
10.8. Vegyes feladatok 103
11. Euler-körök, Euler-utak 109
11.1. Euler-bejárás létezése 109
11.2. Euler-bejárás alkalmazásai 114
11.3. A bejárás változatai 118
12. Hamilton-kör és Hamilton-út 123
12.1. Hamilton-körök és -utak megadása 123
12.2. Szükséges feltételek 126
12.3. Elégséges feltételek 132
12.4. Vegyes feladatok 139
13. Síkbarajzolhatóság 147
13.1. Euler-formula 147
13.2. Kuratowski-tétel, Fáry-Wagner-tétel 153
13.3. Dualitás 159
13.4. Gyenge izomorfia 162
13.5. Vegyes feladatok 165
13.6. A síkbarajzolhatóságnál általánosabb fogalmak 167
13.7. A síkbarajzolhatóságnál speciálisabb fogalmak 169
14. Párosítások 173
14.1. Maximális párosítás 173
14.2. Párosítás páros gráfban - Hali-feltétel 178
14.3. Vegyes feladatok 184
14.4. Lefogás és függetlenség 189
15. Folyamok, többszörös összefüggőség 199
15.1. Folyamok 199
15.2. Többszörös összefüggőség 210
16. Gráfok színezése 217
16.1. Csúcsok színezése 217
16.2. Élek színezése 230
16.3. Perfekt gráfok 236
16.4. Mycielski-konstrukció 239
16.5. Listaszínezés 241
17. Gráfok mátrixai 247
17.1. Szomszédossági mátrix 247
17.2. A szomszédossági mátrix determinánsa, sajátértékei 253
17.3. Illeszkedési mátrix 258
17.4. Körmátrix és vágásmátrix 261
18. Bonyolultságelmélet 265
18.1. Körök és utak 265
18.2. Színezések és klikkek 273
18.3. Eldöntési és keresési problémák 280
18.4. Vegyes feladatok 282
Jelölések 291
Hivatkozott tételek 293
Irodalom 299

Témakörök