Összefüggőség (gráfelmélet)

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

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 $K n$ -hez, egyáltalán nem tartozik elvágó csúcshalmaz, de $κ (K n) = 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 \notin X$ csúcsnak sem. Ekkor $G$ 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.^[5]

Menger tétele

Bővebben: Menger-tétel

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) \leq λ (G) \leq δ (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$ fokszámú csúcstranzitív gráf esetében $2(d + 1)/3 \leq κ (G) \leq λ (G) = d$ .^[10]
Egy $d \leq 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]

Egyéb tulajdonságai

Az összefüggőség tulajdonságát a gráfhomomorfizmusok megőrzik.
Ha $G$ összefüggő, akkor élgráfja, $L (G)$ is összefüggő.
Egy $G$ gráf pontosan akkor $2$ -élösszefüggő, ha van erősen összekötött orientációja.
A Balinski-tétel szerint bármely $k$ dimenziós konvex politóp 1-váza (politópgráfja) k-összefüggő gráfot alkot.^[12] 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 $k$ -összefüggő valamely $k \geq 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.

Kapcsolódó szócikkek

Fordítás

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.

Jegyzetek

↑ ^a ^b Diestel, R., Graph Theory, Electronic Edition, 2005, p 12.
↑ Handbook of graph theory. CRC Press, 335. o. (2004). ISBN 978-1-58488-090-5
↑ Liu, Qinghai (2010. március 1.). „The existence and upper bound for two types of restricted connectivity”. Discrete Applied Mathematics 158, 516-521. o. DOI:10.1016/j.dam.2009.10.017.
↑ Handbook of graph theory. CRC Press, 338. o. (2004). ISBN 978-1-58488-090-5
↑ Balbuena, Camino (2001. október 1.). „On the connectivity and superconnectivity of bipartite digraphs and graphs”. Ars Combinatorica 61, 3-22. o. DOI:10.1.1.101.1458.
↑ Gibbons, A.. Algorithmic Graph Theory. Cambridge University Press (1985)
↑ Algorithmic Aspects of Graph Connectivity. Cambridge University Press (2008)
↑ Reingold, Omer (2008). „Undirected connectivity in log-space”. Journal of the ACM 55 (4), Article 17, 24 pages. o. DOI:10.1145/1391289.1391291.
↑ Provan, J. Scott & Ball, Michael O. (1983), "The complexity of counting cuts and of computing the probability that a graph is connected", SIAM Journal on Computing 12 (4): 777–788, DOI 10.1137/0212053.
↑ Algebraic Graph Theory. Springer Verlag (2001)
↑ Babai, L.. Automorphism groups, isomorphism, reconstruction [archivált változat], Technical Report TR-94-10. University of Chicago (1996). Hozzáférés ideje: 2017. február 28. [archiválás ideje: 2010. június 11.] Chapter 27 of The Handbook of Combinatorics.
↑ Balinski, M. L. (1961). „On the graph structure of convex polyhedra in $n$ -space”. Pacific Journal of Mathematics 11 (2), 431–434. o. [2012. szeptember 11-i dátummal az eredetiből archiválva]. DOI:10.2140/pjm.1961.11.431. (Hozzáférés: 2017. február 28.)
↑ Dirac, Gabriel Andrew (1960). „In abstrakten Graphen vorhandene vollständige 4-Graphen und ihre Unterteilungen”. Mathematische Nachrichten 22, 61–85. o. DOI:10.1002/mana.19600220107. .
↑ (2007) „A generalization of Dirac's theorem on cycles through $k$ vertices in $k$ -connected graphs”. Discrete Mathematics 307 (7–8), 878–884. o. DOI:10.1016/j.disc.2005.11.052. .

[diestel-1] Diestel, R., Graph Theory, Electronic Edition, 2005, p 12.

[2] Handbook of graph theory. CRC Press, 335. o. (2004). ISBN 978-1-58488-090-5

[3] Liu, Qinghai (2010. március 1.). „The existence and upper bound for two types of restricted connectivity”. Discrete Applied Mathematics 158, 516-521. o. DOI:10.1016/j.dam.2009.10.017.

[4] Handbook of graph theory. CRC Press, 338. o. (2004). ISBN 978-1-58488-090-5

[5] Balbuena, Camino (2001. október 1.). „On the connectivity and superconnectivity of bipartite digraphs and graphs”. Ars Combinatorica 61, 3-22. o. DOI:10.1.1.101.1458.

[6] Gibbons, A.. Algorithmic Graph Theory. Cambridge University Press (1985)

[7] Algorithmic Aspects of Graph Connectivity. Cambridge University Press (2008)

[8] Reingold, Omer (2008). „Undirected connectivity in log-space”. Journal of the ACM 55 (4), Article 17, 24 pages. o. DOI:10.1145/1391289.1391291.

[9] Provan, J. Scott & Ball, Michael O. (1983), "The complexity of counting cuts and of computing the probability that a graph is connected", SIAM Journal on Computing 12 (4): 777–788, DOI 10.1137/0212053.

[GandR-10] Algebraic Graph Theory. Springer Verlag (2001)

[11] Babai, L.. Automorphism groups, isomorphism, reconstruction [archivált változat], Technical Report TR-94-10. University of Chicago (1996). Hozzáférés ideje: 2017. február 28. [archiválás ideje: 2010. június 11.] Chapter 27 of The Handbook of Combinatorics.

[12] Balinski, M. L. (1961). „On the graph structure of convex polyhedra in $n$ -space”. Pacific Journal of Mathematics 11 (2), 431–434. o. [2012. szeptember 11-i dátummal az eredetiből archiválva]. DOI:10.2140/pjm.1961.11.431. (Hozzáférés: 2017. február 28.)

[13] Dirac, Gabriel Andrew (1960). „In abstrakten Graphen vorhandene vollständige 4-Graphen und ihre Unterteilungen”. Mathematische Nachrichten 22, 61–85. o. DOI:10.1002/mana.19600220107. .

[14] (2007) „A generalization of Dirac's theorem on cycles through $k$ vertices in $k$ -connected graphs”. Discrete Mathematics 307 (7–8), 878–884. o. DOI:10.1016/j.disc.2005.11.052. .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]