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