A baloldali szürke körben lévő jobbszélső csúcspont törlésével a gráf megszűnik összefüggőnek lenni (szétesik)A szaggatott él törlésével a gráf szétesik.
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.
Összefüggő gráf
A 0-val jelölt csúcs miatt a gráf nem összefüggő, a gráf többi része összefüggő.
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 Girá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ő komponensG 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áfgyengé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 Gk-ö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]
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.[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 Gszuperö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.[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.
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 G 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 G 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ő 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]
Ö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 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
Példák
Egy nem összefüggő gráf összefüggősége és élösszefüggősége egyaránt 0.
Az 1-összefüggés egyszerűen az összefüggést jelenti a legalább 2 csúcsból álló gráfokon.
Az n csúcsú teljes gráf élösszefüggősége n − 1. Bármilyen más n 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 1.
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, κ(G) ≤ λ(G) ≤ δ(G). 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.[1]
Egy d ≤ 4 fokszámú csúcstranzitív gráf esetén, vagy bármely d fokszámú (irányítatlan) minimális Cayley-gráf esetén, továbbá bármely d fokszámú szimmetrikus gráf esetén mindkét fajta összefüggőség értéke megegyezik: κ(G) = λ(G) = d.[11]
G. A. Dirac egy tétele szerint ha egy gráf k-összefüggő valamely k ≥ 2-re, akkor a gráf minden k méretű csúcshalmazához tartozik olyan kör, ami a halmaz minden csúcsán áthalad.[13][14] A k = 2 esetben az állítás megfordítása is igaz.
Ez a szócikk részben vagy egészben a Connectivity (graph theory) 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.
↑ (2007) „A generalization of Dirac's theorem on cycles through k vertices in k-connected graphs”. Discrete Mathematics307 (7–8), 878–884. o. DOI:10.1016/j.disc.2005.11.052..
Strategi Solo vs Squad di Free Fire: Cara Menang Mudah!
