gráftulajdonság From Wikipedia, the free encyclopedia
A matematika és a számítástudomány területén az összefüggőség vagy konnektivitás az alapvető gráfelméleti fogalmak egyike: azon elemek (csúcsok vagy élek) minimális számára kérdez rá, melyek törlésével a gráf szétesik, azaz a megmaradó csúcsok több komponensbe kerülnek.[1] Szoros kapcsolatban van a hálózati folyam-problémákkal. Egy gráf összefüggősége, konnektivitása a hálózat hibákkal szembeni ellenálló képességének fontos mértéke.
Ha egy gráfban bármely két csúcs között van út, akkor a gráf összefüggő. Egy összefüggő gráfban nincsenek elérhetetlen csúcsok. Egy G gráf akkor nem összefüggő, ha található benne olyan csúcspár, melyek között nem vezet út.
Az egyetlen csúcsból álló gráf összefüggő. Az egynél több csúcsból álló élmentes gráf nem összefüggő.
Egy G irányítatlan gráfban, az u és v csúcsokat akkor mondjuk összefüggőnek, ha létezik u és v közötti út (egyébként nem összefüggőek). Ha két csúcsot 1 hosszúságú út (tehát egy él) köt össze, a csúcsok szomszédosak. Egy gráf akkor összefüggő, ha bármely két csúcsa összefüggő.
Egy összefüggő komponens G egy maximális összefüggő részgráfja. Bármely csúcs és bármely él pontosan egy összefüggő komponensbe tartozhat. Példa: Legyenek egy gráf csúcsai egy sakktábla mezői, két csúcs közé pontosan akkor vegyünk fel élt, ha egyik a másikról üthető futóval. E gráf nem összefüggő; a sötét, ill. világos mezők egy-egy komponenst alkotnak.
Egy irányított gráf gyengén összefüggő vagy összefüggő, ha az alapul szolgáló irányítatlan gráf, tehát az irányított éleinek irányítatlanra való cseréjével kapott irányítatlan gráf összefüggő. Egy irányított gráf erősen összefüggő vagy erős, ha bármely u, v csúcspár esetén létezik irányított út u-ból v-be és v-ből u-ba is. Az erős komponensek a maximális erősen összefüggő részgráfok.
Egy összefüggő G gráf elvágó csúcshalmazán (vertex cut, separating set) csúcsok olyan halmazát értjük, melyek törlése után G szétesik. Egy gráf összefüggősége vagy csúcsösszefüggősége (jelölése: κ(G), ahol G nem egy teljes gráf) a minimális elvágó csúcshalmaz mérete. Egy gráf k-szorosan összefüggő vagy k-összefüggő, ha összefüggősége k vagy nagyobb.
Precízebben, bármely G gráf (teljes vagy sem) akkor k-szorosan összefüggő, ha tartalmaz legalább k+1 csúcsot, de nem tartalmaz olyan k − 1 elemű csúcshalmazt, melyek eltávolítása után szétesik a gráf; κ(G) pedig a legnagyobb olyan k, amire G k-összefüggő. Az n csúcsú teljes gráfhoz, azaz Kn-hez, egyáltalán nem tartozik elvágó csúcshalmaz, de κ(Kn) = n − 1. Az u és v (nem szomszédos) csúcshoz tartozó elvágó csúcshalmaz olyan csúcsok halmaza, melyek eltávolítása után u és v különböző összefüggő komponensekbe kerülnek. A κ(u, v) lokális összefüggőség az u és v csúcsokhoz tartozó legkisebb elvágó csúcshalmaz mérete. A lokális összefüggőség irányítatlan gráfokon szimmetrikus, tehát κ(u, v) = κ(v, u). A teljes gráfok kivételével κ(G) megegyezik a κ(u, v) értékek minimumával az összes u, v nem szomszédos csúcspárt tekintve.
Az 1-összefüggő gráf neve egyszerűen összefüggő gráf. A 2-összefüggő gráfok fontos szerepet játszanak a hálózati redundancia biztosításában. Az összefüggő, de nem 2-összefüggő gráfokat néha „szétválasztható gráfoknak” is nevezik.
Az előzőekkel analóg fogalmak meghatározhatók a gráfok éleit tekintve is. Abban az egyszerű esetben, ha egyetlen él törlése után a gráf szétesne, az ilyen él neve hídél vagy elválasztó él. Általánosabban egy G-beli élvágás élek olyan halmaza, melyek eltávolítása után a gráf szétesik. Egy gráf élösszefüggősége (jelölése: κ’(G) vagy λ(G)) a legkisebb élvágásának mérete, az u, v-hez tartozó λ(u, v) lokális élösszefüggőség pedig az u-t v-től elválasztó legkisebb élvágás nagysága. Itt is elmondható, hogy a lokális élösszefüggőség szimmetrikus, tehát λ(u, v) = λ(v, u). Egy gráf akkor k-élösszefüggő, ha élösszefüggősége k vagy nagyobb.
Egy gráf akkor maximálisan összefüggő (maximally connected), ha összefüggősége megegyezik minimális fokszámával. Egy gráf akkor maximálisan élösszefüggő (maximally edge-connected), ha élösszefüggősége megegyezik minimális fokszámával.[2]
Egy gráf akkor szuperösszefüggő (super-connected) vagy super-κ, ha minden minimális csúcsvágása izolál egy csúcsot. Egy gráf akkor hiperösszefüggő (hyper-connected) vagy hyper-κ, ha bármely minimális csúcsvágásának törlésével a gráf pontosan két komponensre esik szét, melyek legalább egyike izolált csúcs. Egy gráf fél-hiperösszefüggő, majdnem hiperösszefüggő (semi-hyper-connected) vagy semi-hyper-κ, ha a minimális csúcsvágás a gráfot pontosan két komponensre választja szét.[3]
Precízebben: egy G összefüggő gráf akkor szuperösszefüggő vagy super-κ, ha minden minimális csúcsvágása triviális, tehát egyetlen (minimális fokszámú) csúcs szomszédságából áll. Egy G összefüggő gráf akkor szuper-élösszefüggő (super-edge-connected) vagy super-λ, ha minden minimális élvágása egyetlen (minimális fokszámú) csúccsal érintkező élből áll.[4]
G gráf X vágás-csúcshalmazát akkor nevezzük nemtriviálisnak, ha X nem tartalmazza az N(u) szomszédságát egyetlen u ∉ X csúcsnak sem. Ekkor G szuperösszefüggősége, κ1 a következőképp határozható meg:
A nem triviális élvágás és a λ1(G) élösszefüggőség (edge-superconnectivity) analóg módon meghatározhatók.[5]
A gráfok összefüggőségével kapcsolatos legfontosabb eredmények egyike a Menger-tétel, ami a gráf összefüggőségét és élösszefüggőségét a csúcsok közötti független utak tekintetében vizsgálja.
Ha u és v a G gráf csúcsai, akkor az u és v közötti utak gyűjteményét függetlennek (csúcsdiszjunktnak) nevezzük, ha semelyik kettőnek sincs közös csúcsa (az u és v végpontokat kivéve). Hasonlóan, a gyűjtemény élfüggetlen (éldiszjunkt) ha semelyik két út nem tartalmaz közös élt. Az u és v közötti csúcsdiszjunkt utak száma κ′(u, v), az u és v közötti éldiszjunkt utaké pedig λ′(u, v).
Menger tételének állítása szerint azu,v különböző csúcsokat tekintve λ(u, v) megegyezik λ′(u, v)-vel és ha u és v nem szomszédosak, akkor κ(u, v) megegyezik κ′(u, v)-vel.[6][7] Ez az eredmény a maximális folyam-minimális vágás tételének speciális esete.
Annak a problémája, hogy a gráf két csúcsa összefüggő-e, keresőalgoritmussal, például szélességi kereséssel hatékonyan megoldható. Általánosabb esetben, könnyen meghatározható, hogy egy gráf összefüggő-e (például diszjunkt halmaz-adatstruktúra segítségével), vagy meg is számolhatók az összefüggő komponensek. Az alábbi egyszerű algoritmus pszeudokódban olvasható:
A Menger-tétel alapján egy összefüggő G gráfban bármely u és v csúcspárra κ(u, v) és λ(u, v) hatékonyan meghatározható a maximális folyam-minimális vágás algoritmusa segítésével. A G gráf összefüggősége és élösszefüggősége kiszámítható κ(u, v), illetve λ(u, v) minimális értékeinek meghatározásával.
A számítási bonyolultság elméletében SL (Symmetric Logspace) a neve annak a problémaosztálynak, ami logaritmikus tárban redukálható gráfban két csúcs összefüggősége vizsgálatának problémájára, amiről Omer Reingold 2004-ben igazolta, hogy megegyezik az LSPACE bonyolultsággal.[8] Ebből következően az irányítatlan gráfok összefüggőségének kérdése O(log n) tárban megoldható.
Annak a valószínűségnek a kiszámítását, hogy egy Bernoulli-véletlen gráf összefüggő-e hálózati megbízhatóságnak nevezik, adott két csúcs összefüggőségének vizsgálata pedig az s-t megbízhatóság problémához köthető. Mindkettő #P-nehéz.[9]
Az n csúcsú különböző, címkézett összefüggő gráfok leszámlálását n = 15-ig az A001187 sorozata végzi el. A sorozat első néhány nemtriviális tagja:
| n | gráfok |
|---|---|
| 2 | 1 |
| 3 | 4 |
| 4 | 38 |
| 5 | 728 |
| 6 | 26704 |
| 7 | 1866256 |
| 8 | 251548592 |
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.
