Gráf szívóssága

Ebben a gráfban a négy piros csúcs eltávolítása négy (különböző színekkel jelölt) összefüggő komponenst eredményezne. Nincs azonban k olyan csúcs, melyek eltávolítása k-nál több komponenst hozna létre. Ezért a gráf szívóssága pontosan 1.

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 ${9 \over 4}$-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.

További információk

• Varga Kitti: Minimálisan 1-szívós gráfok minimális fokszámai (TDK dolgozat, 2014)