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. 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.

Összefüggő gráf

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ő.

A komponensek, vágások és összefüggőség definíciói Egy irányítatlan gráfban, az és csúcsokat akkor mondjuk összefüggőnek, ha létezik és közötti út (egyébként nem összefüggőek). Ha két csúcsot 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 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 csúcspár esetén létezik irányított út -ból -be és -ből -ba is. Az erős komponensek a maximális erősen összefüggő részgráfok.

Egy összefüggő gráf elvágó csúcshalmazán (vertex cut, separating set) csúcsok olyan halmazát értjük, melyek törlése után 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 -szorosan összefüggő vagy -összefüggő, ha összefüggősége vagy nagyobb.

Precízebben, bármely gráf (teljes vagy sem) akkor -szorosan összefüggő, ha tartalmaz legalább csúcsot, de nem tartalmaz olyan elemű csúcshalmazt, melyek eltávolítása után szétesik a gráf; pedig a legnagyobb olyan , amire -összefüggő. Az csúcsú teljes gráfhoz, azaz -hez, egyáltalán nem tartozik elvágó csúcshalmaz, de . Az és (nem szomszédos) csúcshoz tartozó elvágó csúcshalmaz olyan csúcsok halmaza, melyek eltávolítása után és különböző összefüggő komponensekbe kerülnek. A lokális összefüggőség az és 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 . A teljes gráfok kivételével megegyezik a értékek minimumával az összes 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 -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 ) a legkisebb élvágásának mérete, az -hez tartozó lokális élösszefüggőség pedig az -t -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 . Egy gráf akkor -élösszefüggő, ha élösszefüggősége 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.

Szuper- és hiperösszefüggőség 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.

Precízebben: egy ö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 ö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.

gráf vágás-csúcshalmazát akkor nevezzük nemtriviálisnak, ha nem tartalmazza az szomszédságát egyetlen csúcsnak sem. Ekkor szuperösszefüggősége, κ1 a következőképp határozható meg: κ1(G) = min{ |X| : X nem triviális vágás}.

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.

Menger tétele

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 és a gráf csúcsai, akkor az és 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 és 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 és közötti csúcsdiszjunkt utak száma , az és közötti éldiszjunkt utaké pedig .

Menger tételének állítása szerint azu,v különböző csúcsokat tekintve megegyezik -vel és ha u és v nem szomszédosak, akkor megegyezik -vel. Ez az eredmény a maximális folyam-minimális vágás tételének speciális esete.

Számítási tényezők 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ó:

Kezdjünk a gráf tetszőleges csúcsában, Innen végezzünk akár mélységi, akár szélességi keresést, számoljuk meg az elért csúcsokat. Ha a bejárás befejeződött, hasonlítsuk össze a megszámolt csúcsok számát a csúcsainak számával; ha ezek megegyeznek a gráf összefüggő, egyébként nem.

A Menger-tétel alapján egy összefüggő gráfban bármely és csúcspárra és hatékonyan meghatározható a maximális folyam-minimális vágás algoritmusa segítésével. A gráf összefüggősége és élösszefüggősége kiszámítható , illetve 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. Ebből következően az irányítatlan gráfok összefüggőségének kérdése 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..

Összefüggő gráfok leszámlálása Az n csúcsú különböző, címkézett összefüggő gráfok leszámlálását n = 15-ig az 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

Példák Egy nem összefüggő gráf összefüggősége és élösszefüggősége egyaránt . Az -összefüggés egyszerűen az összefüggést jelenti a legalább 2 csúcsból álló gráfokon. Az csúcsú teljes gráf élösszefüggősége . Bármilyen más csúcsú egyszerű gráf esetében ez kisebb szám. Egy fában bármely két csúcs közötti lokális élösszefüggőség értéke .

Az összefüggőségre vonatkozó korlátok Egy gráf csúcsösszefüggősége mindig kisebb vagy egyenlő az élösszefüggőségével. Azaz, . Mindkettő kisebb vagy egyenlő a gráf minimális fokszámával, mivel egy minimális fokszámú csúcs összes szomszédjának törlése leválasztja azt a csúcsot a gráf többi részétől.Diestel, R., Graph Theory, Electronic Edition, 2005, p 12. Egy fokszámú csúcstranzitív gráf esetében . Egy fokszámú csúcstranzitív gráf esetén, vagy bármely fokszámú (irányítatlan) minimális Cayley-gráf esetén, továbbá bármely fokszámú szimmetrikus gráf esetén mindkét fajta összefüggőség értéke megegyezik: . Chapter 27 of The Handbook of Combinatorics.

Egyéb tulajdonságai Az összefüggőség tulajdonságát a gráfhomomorfizmusok megőrzik. Ha összefüggő, akkor élgráfja, is összefüggő. Egy gráf pontosan akkor -élösszefüggő, ha van erősen összekötött orientációja. A Balinski-tétel szerint bármely dimenziós konvex politóp 1-váza (politópgráfja) k-összefüggő gráfot alkot. Steinitz korábbi tétele ennek részleges megfordítását adja, mi szerint bármely 3-összefüggő egyszerű síkgráf egy konvex poliéder vázát alkotja. G. A. Dirac egy tétele szerint ha egy gráf -összefüggő valamely -re, akkor a gráf minden méretű csúcshalmazához tartozik olyan kör, ami a halmaz minden csúcsán áthalad... A esetben az állítás megfordítása is igaz.

Kapcsolódó szócikkek Algebrai összefüggőség Cheeger-állandó Dinamikus összefüggőség, Diszjunkt halmaz adatszerkezet, Partíció finomítása Expander gráf Gráftulajdonság Skálafüggetlen hálózat Kisvilág-tulajdonság, Hat lépés távolság, A kicsi világ kísérlet Gráf erőssége

Fordítás

Jegyzetek