miniatura| Acest graf devine neconex atunci când nodul din dreapta din zona gri din stânga este eliminat miniatura| Acest grafic devine neconex atunci când muchia punctată este eliminată. Î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. 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.

Noduri conectate și grafuri conexe miniatura| Cu vârful 0, acest graf este neconex. Restul grafului este conex. Într-un graf neorientat , două noduri și se numesc conectate dacă conține undrum de la la . Dacă două noduri sunt, mai mult, conectate printr-un drum de lungime , 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 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 la , fie un drum orientat de la la pentru fiecare pereche de noduri . Este tare conex sau pur și simplu tare, dacă conține un drum orientat de la la și un drum orientat de la la pentru fiecare pereche de noduri .

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 sau o mulțime de separare a unui graf conex este o mulțime de noduri a căror îndepărtare îl face pe să nu mai fie conex. Conexitatea pe noduri (unde nu este un graf complet) este dimensiunea unei tăieturi minimale de noduri. Un graf se numește -conex în noduri sau -conex dacă conectivitatea sa pe noduri este sau mai mare.

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

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

-conexitatea se numește și biconexitate, iar -conexitatea se numește și triconexitate.Dana Lica, Descompunerea unui graf in componente triconexe: Algoritmul - J.E. Hopcroft si R.E. Tarjan, edu.ro, 2007, accesat 2022-08-21 Un graf care este conex, dar nu este -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 este o mulțime de muchii a căror eliminare face graful să nu mai fie conex. este dimensiunea celei mai mici tăieturi de muchii, iar conexitatea locală pe muchii a două noduri este dimensiunea celei mai mici tăieturi de muchii care deconectează de . Din nou, conexitatea locală de muchii este simetrică. Un graf se numește -conex pe muchii dacă conexitatea sa pe muchii este 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.

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.

Mai precis: se spune că un graf conex 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 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).

O mulțime de tăieturi a lui se numește mulțime de tăieturi netrivială dacă nu conține vecinătatea a vreunui nod . 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.

Teorema lui Menger

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

Dacă și sunt noduri ale unui graf , atunci o colecție de drumuri între și este numită "cu noduri disjuncte" dacă niciunul dintre ele nu are în comun un nod (altul decât și î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 și este scris ca , iar numărul de drumuri cu muchii disjuncte două câte două dintre și este scris ca .

Teorema lui Menger afirmă că pentru noduri distincte u, v, este egal cu , iar dacă u nu este adiacent cu v, atunci este egal cu . Acest fapt este de fapt un caz special al .

Aspecte computaționale Problema de a determina dacă două noduri dintr-un graf sunt conexe poate fi rezolvată eficient folosind un , 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 ) 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 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 , atunci graful este conex

Conform teoremei lui Menger, pentru oricare două noduri și dintr-un graf conex , numerele și pot fi determinate eficient folosind algoritmul . Conexitatea pe noduri și pe muchii ale lui pot fi apoi calculate ca valori minime ale lui și respectiv .

În teoria complexității, este clasa de probleme 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 în 2004. Prin urmare, conexitatea grafurilor neorientate poate fi rezolvată în spațiu .

Problema calculării probabilității ca un 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 -hard..

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 . -conexitatea este echivalentă cu conexitatea pentru grafuri de cel puțin 2 vârfuri. Graful complet pe vârfuri are conexitatea pe muchii egală cu . Orice alt graf simplu de noduri are o conexitate pe muchii strict mai mică. Într-un arbore, conexitatea locală a muchiei dintre fiecare pereche de noduri este .

Limite ale conexității

Conexitatea pe noduri a unui graf este mai mică sau egală cu conexitatea pe muchii, adică . 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. Pentru un de grad , avem: . Pentru un de grad sau pentru orice minimal (neorientat) de grad , sau pentru orice de grad , ambele tipuri de conexitate sunt egale: . Chapter 27 of The Handbook of Combinatorics.

Alte proprietăți

Conexitatea este conservată de . Dacă este conex, atunci este de asemenea conex. Un graf este 2-conex pe muchii dacă și numai dacă are o orientare care este tare conexă. Teorema lui Balinski afirmă că graful politopic (-scheletul) al unui politop convex -dimensional este un graf -conex pe noduri, Teorema anterioară a lui conform căreia orice graf planar 3-conex pe noduri este un graf politopal () dă o reciprocă parțială. Conform unei teoreme a lui , dacă un graf este -conex pentru , atunci pentru orice mulțime de noduri din graf există un ciclu care trece prin toate nodurile din mulțime... Reciproca este adevărată dacă .

Bibliografie

Categorie:Teoria grafurilor