A kínai hadseregtől az utazó ügynökig

Tartalom

Előszó az Olvasóhoz 5
1. Gráfelméleti alapfogalmak 9
2. Gráfok megadása, tárolása, adatkonverziók 14
2.1. Tárolás csúcsmátrixban 14
2.2. Tárolás éllistán 16
2.3. Tárolás pontláncolással 16
2.4. Számítástechnikai megvalósítás és struktúrák közötti konverziók 19
3. Lényeges adatszerkezetek és velük végzett műveletek 21
3.1. A FIFO sor 21
3.2. A verem (stack) 22
3.3. Halmazok, halmazműveletek 22
4. Gráfok bejárása 24
4.1. Euler-bejárás 24
4.2. Vaktában bejárható gráfok 37
4.3. Hamilton-kör és -út keresése 41
5. Fák, favázak 44
5.1. Megtanítjuk a számítógépet arra, hogy favázat
„gyártson" (Faváz kijelölése összefüggő gráfban) 45
5.2. Amikor megjelenik a korrupció (Kötött faváz keresése) 47
5.3. A technológia tovább fejlődik... (Minimális költségű faváz keresése) 51
5.4. Az összefüggőség problémája 55
5.5. A Prüfer-kód 56
5.6. A kiállítás megtekintésének programja 58
6. Labirintusproblémák 59
6.1. Tervezzünk labirintust! 59
6.2. A kínai hadsereg (BFS algoritmus) 62
6.3. A hadsereg nem segít (DFS algoritmus) 65
6.4. A világ az egér szemével 67
6.5. Összefoglalás 68
7. Folyamproblémák 69
7.1. Maximális értékű folyam keresése 69
7.2. Minimális költségű szállítás 73
8. Optimális utak 76
8.1. PERT-módszer 76
8.2. Dijkstra algoritmusa 79
8.3. A kritikus út 80
9. Érdekes feladatok 83
9.1. A házasságközvetítési probléma (maximális párosítás) 83
9.2. Maximális független ponthalmaz keresése 89
9.3. Az utazó ügynök problémája 92
9.4. Tartalmazási feladatok 93
9.5. Véletlen gráfok generálása 97
10. Példaprogram: Logikai hálózat szimulációja 99
Gyakorlófeladatok 103
Tárgymutató 107
A lemez tartalomjegyzéke | 111
Irodalomjegyzék 114

Témakörök