Conexitate (teoria grafurilor)

În matematică și informatică, conexitatea (sau conectivitatea) este unul dintre conceptele de bază ale teoriei grafurilor. Gradul de conexitate este numărul minim de elemente (noduri sau muchii) care trebuie eliminate pentru a separa nodurile rămase în două sau mai multe subgrafuri izolate.^[1] Este strâns legat de teoria problemelor de flux în rețele. Conexitatea unui graf este o măsură importantă a robusteții sale ca rețea.

Acest grafic devine neconex atunci când muchia punctată este eliminată.

Noduri conectate și grafuri conexe

Cu vârful 0, acest graf este neconex. Restul grafului este conex.

Într-un graf neorientat $G$ , două noduri $u$ și $v$ se numesc conectate dacă $G$ conține undrum de la $u$ la $v$ . Dacă două noduri sunt, mai mult, conectate printr-un drum de lungime $1$ , adică printr-o singură muchie, nodurile se numesc adiacente.

Se spune că un graf este conex dacă fiecare pereche de noduri din graf este conexă. Aceasta înseamnă că există un drum între fiecare pereche de vârfuri. Prin urmare, un graf neorientat G este neconex dacă există două noduri în G astfel încât să nu existe nicio cale prin G care să înceapă dintr-un nod și să se termine în celălalt. Graful cu un singur nod este considerat conex. Un graf fără muchii^⁠(d) cu două sau mai multe noduri este neconex.

Un graf orientat se numește slab conex dacă, înlocuindu-i toate arcele cu muchii neorientate, se obține un graf neorientat conex. Este unilateral (sau semiconex) dacă conține fie un drum orientat de la $u$ la $v$ , fie un drum orientat de la $v$ la $u$ pentru fiecare pereche de noduri $u, v$ .^[2] Este tare conex sau pur și simplu tare, dacă conține un drum orientat de la $u$ la $v$ și un drum orientat de la $v$ la $u$ pentru fiecare pereche de noduri $u, v$ .

Componente și tăieturi

O componentă conexă este un subgraf conex maximal al unui graf neorientat. Fiecare nod aparține exact unei componente conexe, la fel ca fiecare muchie. Un graf este conex dacă și numai dacă are exact o componentă conexă.

Componentele tare conexe sunt subgrafurile maximale tare conexe ale unui graf orientat.

O tăietură de noduri^⁠(d) sau o mulțime de separare a unui graf conex $G$ este o mulțime de noduri a căror îndepărtare îl face pe $G$ să nu mai fie conex. Conexitatea pe noduri $κ (G)$ (unde $G$ nu este un graf complet) este dimensiunea unei tăieturi minimale de noduri. Un graf se numește $k$ -conex în noduri sau $k$ -conex dacă conectivitatea sa pe noduri este $k$ sau mai mare.

Mai precis, $G$ (complet sau nu) este $k$ -conex pe noduri dacă conține cel puțin $k +1$ noduri, dar nu conține o mulțime de $k - 1$ noduri a căror îndepărtare deconectează graful; și $κ (G)$ este definit ca cel mai mare $k$ astfel încât $G$ este $k$ -conex. În special, un graf complet cu $n$ vârfuri, notat $K n$ , nu are deloc tăieturi de vârfuri, dar $κ (K n) = n - 1$ .

O tăietură de noduri pentru două noduri $u$ și $v$ este o mulțime de noduri a căror eliminare din graf deconectează $u$ și $v$ . Conectivitatea locală $κ (u, v)$ este dimensiunea unei tăieturi de noduri care separă $u$ și $v$ . Conectivitatea locală este simetrică pentru grafurile neorientate; adică $κ (u, v) = κ (v, u)$ . Mai mult, cu excepția grafurilor complete, $κ (G)$ este egal cu $κ (u, v)$ minim peste toate perechile neadiacente de vârfuri $u, v$ .

$2$ -conexitatea se numește și biconexitate, iar $3$ -conexitatea se numește și triconexitate.^[3] Un graf $G$ care este conex, dar nu este $2$ -conex este uneori numit separabil.

Concepte analoge pot fi definite pentru muchii. În cazul simplu în care tăierea unei singure muchii ar deconecta graful, acea muchie se numește punte. Mai general, o tăietură de muchii a lui $G$ este o mulțime de muchii a căror eliminare face graful să nu mai fie conex. Conexitatea pe muchii^⁠(d) $λ (G)$ este dimensiunea celei mai mici tăieturi de muchii, iar conexitatea locală pe muchii $λ (u, v)$ a două noduri $u, v$ este dimensiunea celei mai mici tăieturi de muchii care deconectează $u$ de $v$ . Din nou, conexitatea locală de muchii este simetrică. Un graf se numește $k$ -conex pe muchii dacă conexitatea sa pe muchii este $k$ sau mai mare.

Se spune că un graf este conex maximal dacă conectivitatea sa este egală cu gradul minim. Se spune că un graf este conex maximal pe muchii dacă conexitatea sa pe muchii este egală cu gradul minim.^[4]

Super- și hiper-conexitate

Se spune că un graf este super-conex sau super-κ dacă orice tăietură minimă de noduri izolează un nod. Se spune că un graf este hiperconex sau hiper-κ dacă ștergerea oricărei tăieturi minime de noduri creează exact două componente conexe, dintre care una este un nod izolat. Un graf este semi-hiper-conex sau semi-hiper-κ dacă orice tăietură minimă de noduri separă graful în exact două componente conexe.^[5]

Mai precis: se spune că un graf conex $G$ este super-conex sau super-κ dacă orice tăietură minimă de noduri este formată din noduri adiacente cu un nod (de grad minim). Un graf conex $G$ se spune a fi super-conex sau super-λ dacă orice tăietură minimă de muchii constă din muchiile incidente cu un anume nod (de grad minim).^[6]

O mulțime de tăieturi $X$ a lui $G$ se numește mulțime de tăieturi netrivială dacă $X$ nu conține vecinătatea $N(u)$ a vreunui nod $u \notin X$ . Atunci superconexitatea κ1 a lui G este:

κ1(G) = min{|X| : X este o mulțime de tăieturi netrivială}.

O tăietură de muchii netrivială și superconexitatea pe muchii λ1(G) sunt definite în mod analog.^[7]

Teorema lui Menger

Unul dintre cele mai importante fapte despre conexitatea grafurilor este teorema lui Menger^⁠(d), care caracterizează conexitatea și conexitatea pe muchii a unui graf în ceea ce privește numărul de drumuri independente dintre noduri.

Dacă $u$ și $v$ sunt noduri ale unui graf $G$ , atunci o colecție de drumuri între $u$ și $v$ este numită "cu noduri disjuncte" dacă niciunul dintre ele nu are în comun un nod (altul decât $u$ și $v$ înșiși). În mod similar, colecția are muchii disjuncte dacă nu există două drumuri din ea care au o muchie în comun. Numărul de drumuri cu noduri disjuncte între $u$ și $v$ este scris ca $κ' (u, v)$ , iar numărul de drumuri cu muchii disjuncte două câte două dintre $u$ și $v$ este scris ca $λ' (u, v)$ .

Teorema lui Menger afirmă că pentru noduri distincte u, v, $λ (u, v)$ este egal cu $λ' (u, v)$ , iar dacă u nu este adiacent cu v, atunci $κ (u, v)$ este egal cu $κ' (u, v)$ .^[8]^[9] Acest fapt este de fapt un caz special al teoremei max-flow min-cut^⁠(d).

Aspecte computaționale

Problema de a determina dacă două noduri dintr-un graf sunt conexe poate fi rezolvată eficient folosind un algoritm de căutare^⁠(d), cum ar fi căutarea în lățime. Mai general, este ușor să se determine computațional dacă un graf este conex (de exemplu, folosind o structură de date cu mulțimi disjuncte^⁠(d)) sau să se numere câte componente conexe are. Un algoritm simplu poate fi scris în pseudo-cod după cum urmează:

Se începe de la orice nod arbitrar al grafului $G$
Se continuă din acel nod folosind fie căutarea în adâncime, fie în lățime, numărând toate nodurile atinse.
Odată ce graful a fost parcurs în întregime, dacă numărul de noduri numărate este egal cu numărul de noduri ale lui $G$ , atunci graful este conex

Conform teoremei lui Menger, pentru oricare două noduri $u$ și $v$ dintr-un graf conex $G$ , numerele $κ (u, v)$ și $λ (u, v)$ pot fi determinate eficient folosind algoritmul max-flow min-cut^⁠(d). Conexitatea pe noduri și pe muchii ale lui $G$ pot fi apoi calculate ca valori minime ale lui $κ (u, v)$ și respectiv $λ (u, v)$ .

În teoria complexității, SL^⁠(d) este clasa de probleme reductibilă în logspace^⁠(d) la problema de a determina dacă două noduri dintr-un graf sunt conectate, clasă care a fost dovedită a fi egală cu L de către Omer Reingold^⁠(d) în 2004.^[10] Prin urmare, conexitatea grafurilor neorientate poate fi rezolvată în spațiu $O(log n)$ .

Problema calculării probabilității ca un graf aleatoriu Bernoulli^⁠(d) să fie conex se numește fiabilitatea rețelei, iar problema calculării dacă două noduri date sunt conectate este problema fiabilității ST. Ambele sunt #P^⁠(d)-hard.^[11]

Numărul de grafuri conexe

Numărul de grafuri etichetate conexe distincte cu n noduri este tabulat în Enciclopedia on-line a șirurilor de numere întregi ca șirul A001187. Primii câțiva termeni netriviali sunt:

Exemple

Conexitatea pe noduri și pe muchii ale unui graf neconex sunt ambele $0$ .
$1$ -conexitatea este echivalentă cu conexitatea pentru grafuri de cel puțin 2 vârfuri.
Graful complet pe $n$ vârfuri are conexitatea pe muchii egală cu $n - 1$ . Orice alt graf simplu de $n$ noduri are o conexitate pe muchii strict mai mică.
Într-un arbore, conexitatea locală a muchiei dintre fiecare pereche de noduri este $1$ .

Limite ale conexității

Conexitatea pe noduri a unui graf este mai mică sau egală cu conexitatea pe muchii, adică $κ (G) \leq λ (G)$ . Ambele sunt mai mici sau egale cu gradul minim din graf, deoarece ștergerea tuturor vecinilor unui nod de grad minim va deconecta acel vârf de restul grafului.^[1]
Pentru un graf tranzitiv pe noduri^⁠(d) de grad $d$ , avem: $2(d + 1)/3 \leq κ (G) \leq λ (G) = d$ . ^[12]
Pentru un graf tranzitiv pe noduri^⁠(d) de grad $d \leq 4$ sau pentru orice graf Cayley^⁠(d) minimal (neorientat) de grad $d$ , sau pentru orice graf simetric^⁠(d) de grad $d$ , ambele tipuri de conexitate sunt egale: $κ (G) = λ (G) = d$ .^[13]

Alte proprietăți

Conexitatea este conservată de omomorfismele de graf^⁠(d) .
Dacă $G$ este conex, atunci graful linie^⁠(d) $L (G)$ este de asemenea conex.
Un graf $G$ este 2-conex pe muchii dacă și numai dacă are o orientare care este tare conexă.
Teorema lui Balinski afirmă că graful politopic ( $1$ -scheletul) al unui politop convex $k$ -dimensional este un graf $k$ -conex pe noduri,^[14] Teorema anterioară a lui Steinitz^⁠(d) conform căreia orice graf planar 3-conex pe noduri este un graf politopal (teorema Steinitz^⁠(d)) dă o reciprocă parțială.
Conform unei teoreme a lui GA Dirac^⁠(d), dacă un graf este $k$ -conex pentru $k \geq 2$ , atunci pentru orice mulțime de $k$ noduri din graf există un ciclu care trece prin toate nodurile din mulțime.^[15]^[16] Reciproca este adevărată dacă $k = 2$ .

Bibliografie

^ ^a ^b Diestel, R. (2005). „Graph Theory, Electronic Edition”. p. 12.
^ Chapter 11: Digraphs: Principle of duality for digraphs: Definition
^ Dana Lica, Descompunerea unui graf in componente triconexe: Algoritmul - J.E. Hopcroft si R.E. Tarjan, edu.ro, 2007, accesat 2022-08-21
^ Gross, Jonathan L.; Yellen, Jay (2004). Handbook of graph theory. CRC Press. p. 335. ISBN 978-1-58488-090-5.
^ Liu, Qinghai; Zhang, Zhao (1 martie 2010). „The existence and upper bound for two types of restricted connectivity”. Discrete Applied Mathematics. 158 (5): 516–521. doi:10.1016/j.dam.2009.10.017.
^ Gross, Jonathan L.; Yellen, Jay (2004). Handbook of graph theory. CRC Press. p. 338. ISBN 978-1-58488-090-5.
^ Balbuena, Camino; Carmona, Angeles (1 octombrie 2001). „On the connectivity and superconnectivity of bipartite digraphs and graphs”. Ars Combinatorica. 61: 3–22.
^ Gibbons, A. (1985). Algorithmic Graph Theory. Cambridge University Press.
^ Nagamochi, H.; Ibaraki, T. (2008). Algorithmic Aspects of Graph Connectivity. Cambridge University Press.
^ Reingold, Omer (2008). „Undirected connectivity in log-space”. Journal of the ACM^⁠(d). 55 (4): 1–24. 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^⁠(d). 12 (4): 777–788. doi:10.1137/0212053. .
^ Godsil, C.; Royle, G. (2001). Algebraic Graph Theory. Springer Verlag.
^ Babai, L. (1996). Automorphism groups, isomorphism, reconstruction. Technical Report TR-94-10. University of Chicago. Arhivat din original la 11 iunie 2010. Accesat în 5 noiembrie 2021. 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^⁠(d). 11 (2): 431–434. doi:10.2140/pjm.1961.11.431.
^ Dirac, Gabriel Andrew (1960). „In abstrakten Graphen vorhandene vollständige 4-Graphen und ihre Unterteilungen”. Mathematische Nachrichten^⁠(d). 22 (1–2): 61–85. doi:10.1002/mana.19600220107. .
^ Flandrin, Evelyne; Li, Hao; Marczyk, Antoni; Woźniak, Mariusz (2007). „A generalization of Dirac's theorem on cycles through $k$ vertices in $k$ -connected graphs”. Discrete Mathematics. 307 (7–8): 878–884. doi:10.1016/j.disc.2005.11.052. .

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

[2] Chapter 11: Digraphs: Principle of duality for digraphs: Definition

[3] Dana Lica, Descompunerea unui graf in componente triconexe: Algoritmul - J.E. Hopcroft si R.E. Tarjan, edu.ro, 2007, accesat 2022-08-21

[4] Gross, Jonathan L.; Yellen, Jay (2004). Handbook of graph theory. CRC Press. p. 335. ISBN 978-1-58488-090-5.

[5] Liu, Qinghai; Zhang, Zhao (1 martie 2010). „The existence and upper bound for two types of restricted connectivity”. Discrete Applied Mathematics. 158 (5): 516–521. doi:10.1016/j.dam.2009.10.017.

[6] Gross, Jonathan L.; Yellen, Jay (2004). Handbook of graph theory. CRC Press. p. 338. ISBN 978-1-58488-090-5.

[7] Balbuena, Camino; Carmona, Angeles (1 octombrie 2001). „On the connectivity and superconnectivity of bipartite digraphs and graphs”. Ars Combinatorica. 61: 3–22.

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

[9] Nagamochi, H.; Ibaraki, T. (2008). Algorithmic Aspects of Graph Connectivity. Cambridge University Press.

[10] Reingold, Omer (2008). „Undirected connectivity in log-space”. Journal of the ACM^⁠(d). 55 (4): 1–24. doi:10.1145/1391289.1391291.

[11] 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^⁠(d). 12 (4): 777–788. doi:10.1137/0212053. .

[GandR-12] Godsil, C.; Royle, G. (2001). Algebraic Graph Theory. Springer Verlag.

[13] Babai, L. (1996). Automorphism groups, isomorphism, reconstruction. Technical Report TR-94-10. University of Chicago. Arhivat din original la 11 iunie 2010. Accesat în 5 noiembrie 2021. Chapter 27 of The Handbook of Combinatorics.

[14] Balinski, M. L. (1961). „On the graph structure of convex polyhedra in $n$ -space”. Pacific Journal of Mathematics^⁠(d). 11 (2): 431–434. doi:10.2140/pjm.1961.11.431.

[15] Dirac, Gabriel Andrew (1960). „In abstrakten Graphen vorhandene vollständige 4-Graphen und ihre Unterteilungen”. Mathematische Nachrichten^⁠(d). 22 (1–2): 61–85. doi:10.1002/mana.19600220107. .

[16] Flandrin, Evelyne; Li, Hao; Marczyk, Antoni; Woźniak, Mariusz (2007). „A generalization of Dirac's theorem on cycles through $k$ vertices in $k$ -connected graphs”. Discrete Mathematics. 307 (7–8): 878–884. doi:10.1016/j.disc.2005.11.052. .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]