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 valós számra egy gráf akkor -szívós, ha minden egész számra igaz, hogy nem osztható fel különböző összefüggő komponensre -nál kevesebb csúcs eltávolításával. Például egy gráf akkor -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 , amire a gráf -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 foglalkozott. Azóta jelentős irodalma keletkezett a kérdésnek, ö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 csúcsának eltávolítása a megmaradó gráfok akár ö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 csúcs eltávolításával legfeljebb , időnként pedig pontosan összefüggő komponenst hagy meg, ezért a kör -szívós.
Csúcsösszefüggőséggel való kapcsolata Ha egy gráf -szívós, annak egyik következménye, hogy (a esetből láthatóan) bármely csúcsa eltávolítható a gráf kettészakadása nélkül. Más szóval, minden -szívós gráf egyben -szeresen összefüggő.
Kapcsolat a Hamilton-körrel megfigyelte, hogy minden kör, és így minden Hamilton-kört tartalmazó gráf is -szívós; tehát az -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 küszöbérték, amire minden -szívós gráf tartalmaz Hamilton-kört. Chvátal eredeti sejtése szerint , amiből következett volna a Fleischner-tétel is, de 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 -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 -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 racionális számra: a -szívósság tesztelése co-NP-teljes .
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
Jegyzetek . . . .
További információk Varga Kitti: Minimálisan 1-szívós gráfok minimális fokszámai (TDK dolgozat, 2014)
Kategória:Gráfok összefüggősége Kategória:Gráfinvariánsok