| dbo:abstract
|
- 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 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). (hu)
- 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 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). (hu)
|
