A kínai hadseregtől az utazó ügynökig (Gráfok gépközelben)

Gráfok gépközelben - Aki fellapozza ezt a könyvet, minden bizonnyal észreveszi, hogy a kicsit furcsa cím mögött korántsem egy izgalmas politikai krimi lapul, hanem egy programokkal megtűzdelt számítástechnikai szakkönyv. A szerzők néhány érdekes gráfelméleti problémát vesznek sorra, leírják megoldásaikat, valamennyihez kész programot is adnak. Ezekben a mintafeladatokban mutatják be a gráfelméleti algoritmusok programozástechnikáját. A könyv tartalmazza az algoritmusok megértéséhez szükséges legfontosabb elméleti tudnivalókat is. A könyvben is megvásárolhatók. 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