Gráf szívóssága
A matematika, azon belül a gráfelmélet területén egy gráf szívóssága (toughness) a gráf összefüggőségének egyik mértéke. Adott t valós számra egy G gráf akkor t-szívós, ha minden k > 1 egész számra igaz, hogy G nem osztható fel k különböző összefüggő komponensre tk-nál kevesebb csúcs eltávolításával. Például egy gráf akkor 1-szívós, ha csúcsok egy halmazának eltávolításával legfeljebb annyi új komponense keletkezik, ahány csúcsot eltávolítunk. Egy gráf szívóssága, τ(G), az a maximális t, amire a gráf t-szívós; ez minden véges gráfra véges, a teljes gráfok kivételével, melyeknek megállapodás szerint végtelen szívósságot tulajdonítunk. A G gráfot minimálisan t-szívósnak nevezzük, ha τ (G) = t, és bármely e ∈ E(G) él esetén τ (G − e) < t teljesül. A gráfok szívósságával először Václav Chvátal (1973) foglalkozott. Azóta jelentős irodalma keletkezett a kérdésnek, (Bauer, Broersma & Schmeichel 2006) összefoglaló munkája 99 tételt és 162 tanulmányt jegyez fel a témában. Analóg fogalom a csúcsok helyett élek eltávolításával definiált erősség (strength of a graph).
Példák
Egy útgráf k csúcsának eltávolítása a megmaradó gráfok akár k + 1 összefüggő komponensre bonthatja. A komponensek és az eltávolított csúcsok aránya akkor a legnagyobb, ha egyetlen csúcsot törlünk az útgráf belsejéből, így két komponensre bontva azt. Így az útgráfok ½-szívósak. Ezzel szemben egy körgráfból k csúcs eltávolításával legfeljebb k, időnként pedig pontosan k összefüggő komponenst hagy meg, ezért a kör 1-szívós.
Csúcsösszefüggőséggel való kapcsolata
Ha egy gráf t-szívós, annak egyik következménye, hogy (a k = 2 esetből láthatóan) bármely 2t − 1 csúcsa eltávolítható a gráf kettészakadása nélkül. Más szóval, minden t-szívós gráf egyben 2t-szeresen összefüggő.
Kapcsolat a Hamilton-körrel
(Chvátal 1973) megfigyelte, hogy minden kör, és így minden Hamilton-kört tartalmazó gráf is 1-szívós; tehát az 1-szívósság a Hamilton-kör létezésének szükséges feltétele. Sejtése szerint a szívósság és a Hamilton-kör létezése közötti kapcsolat kétirányú: létezik olyan t küszöbérték, amire minden t-szívós gráf tartalmaz Hamilton-kört. Chvátal eredeti sejtése szerint t = 2, amiből következett volna a Fleischner-tétel is, de (Bauer, Broersma & Veldman 2000) ellenpéldát adott rá. Nyitott kérdés, hogy létezik-e nagyobb küszöbérték a Hamilton-kör létezésére, ez Chvátal szívóssági sejtése (Chvátal's toughness conjecture). Mindenesetre, ha igaz a sejtés, a küszöbérték biztosan nagyobb -nél.
Szívóssággal kapcsolatos sejtések
Kriesell-sejtés: Legyen G egy minimálisan 1-szívós gráf. Ekkor G-ben létezik másodfokú csúcs.
Számítási bonyolultság
Annak tesztelése, hogy egy gráf 1-szívós-e, co-NP-teljes probléma. Tehát az az eldöntési probléma, melyre a válasz „igen” a nem 1-szívós gráfokra és „nem” az 1-szívósakra, NP-teljes. Ugyanez igaz bármely állandóra vett q racionális számra: a q-szívósság tesztelése co-NP-teljes (Bauer, Hakimi & Schmeichel 1990).
Kapcsolódó szócikkek
- Gráf erőssége, analóg elgondolás éltörlésekre
- Tutte–Berge-képlet, gráfok maximális elemszámú párosításának kapcsolódó jellemzése
Fordítás
- Ez a szócikk részben vagy egészben a Graph toughness című angol Wikipédia-szócikk ezen változatának fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel. Ez a jelzés csupán a megfogalmazás eredetét és a szerzői jogokat jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.
Jegyzetek
- Bauer, Douglas; Broersma, Hajo & Schmeichel, Edward (2006), "Toughness in graphs—a survey", Graphs and Combinatorics 22 (1): 1–35, DOI 10.1007/s00373-006-0649-0.
- Bauer, D.; Broersma, H. J. & Veldman, H. J. (2000), "Not every 2-tough graph is Hamiltonian", Discrete Applied Mathematics 99: 317–321, DOI 10.1016/S0166-218X(99)00141-9.
- Bauer, D.; Hakimi, S. L. & Schmeichel, E. (1990), "Recognizing tough graphs is NP-hard", Discrete Applied Mathematics 28 (3): 191–195, DOI 10.1016/0166-218X(90)90001-S.
- Chvátal, Václav (1973), "Tough graphs and Hamiltonian circuits", Discrete Mathematics 5 (3): 215–228, DOI 10.1016/0012-365X(73)90138-6.