Punte (teoria grafurilor)

În teoria grafurilor, o punte este o muchie a unui graf a cărei ștergere ar crește numărul de componente conexe. Echivalent, o muchie este punte dacă și numai dacă nu este conținută în niciun ciclu. Un graf este declarat a fi fără punți dacă nu conține nicio punte.

Graf cu 16 noduri și 6 punți (evidențiate cu roșu)

Graf neorientat conex fără punți

Un alt sens al „punții” apare în termenul punte a unui subgraf. Dacă H este un subgraf al G, o punte a lui H în G este un subgraf maximal al lui G care nu este conținut în H și nu este separat de H.

Arbori și păduri

Un graf cu $n$ noduri poate conține cel mult $n-1$ punți, deoarece adăugarea de muchii suplimentare trebuie să creeze un ciclu. Grafurile cu exact $n-1$ punți sunt exact arbori, iar grafurile în care toate muchiile sunt punți sunt exact păduri.

În orice graf neorientat, există o relație de echivalență pe noduri în funcție de care două noduri sunt legate reciproc ori de câte ori există două căi de legătură cu muchii disjuncte. (Fiecare nod este legat la sine prin intermediul a două drumuri de lungime zero identice dar totuși cu muchii disjuncte.) Clasele de echivalență ale acestei relații se numesc componente conexe în 2 muchii, și punțile din graf sunt exact muchiile ale căror capete aparțin unir astfel de componente diferite. Arborele bloc cu punți asociat grafului are un nod pentru fiecare componentă netrivială și o muchie pentru fiecare punte.

Legătura cu conectivitatea nodurilor

Punțile sunt strâns legate de conceptul de puncte de articulație^⁠(d), noduri care aparțin tuturor drumurilor între unele perechi de alte noduri. Cele două extremități ale unei punți sunt puncte de articulație, cu excepția cazului în care au gradul 1, deși se poate ca o muchie care nu este punte să conecteze două puncte de articulație. În mod analog cu noțiunea de grafuri conexe în 2 muchii ca fiind grafuri fără punți, grafurile fără puncte de articulație sunt conexe în 2-noduri sau biconexe.

Într-un graf cubic, fiecare punct de articulație este o extremitate a cel puțin unei punți.

Grafuri fără punți

Un graf fără punți este un graf care nu are nicio punte. Condiții echivalente sunt ca fiecare componentă conexă a grafului are o open ear decomposition^⁠(d), ca fiecare componentă conexă să fie conexă în 2 muchii^⁠(d), sau (conform teoremei lui Robbins^⁠(d)) ca fiecare componentă conexă să aibă orientare tare^⁠(d).

O importantă problemă deschisă care implică punțile este conjectura dublei acoperiri cu cicluri^⁠(d), datorată lui Seymour^⁠(d) și Szekeres^⁠(d) (1978 și 1979, independent), care prevede că fiecare graf fără punți admite o mulțime de cicluri simple care conțin fiecare muchie de exact două ori.

Algoritmul de găsire a punților al lui Tarjan

Primul algoritm în timp liniar pentru găsirea punților într-un graf a fost descris de Robert Tarjan în 1974. Se efectuează următorii pași:

• Se găsește o pădure de acoperire^⁠(d) a lui $G$
• Se creează o pădure cu rădăcini $F$ din arborele de acoperire
• Se parcurge pădurea $F$ in preordine^⁠(d) și se numără nodurile. Nodurile părinte din pădure au acum numere mai mici decât nodurile copil.
• Pentru fiecare nod $v$ preordonat (notând fiecare nod cu numărul său de la parcurgere), se efectuează:
  • Se calculează numărul pădurilor descendente $ND(v)$ pentru acest nod, adăugând unu la suma descendenților copiilor.
  • Se calculează $L(v)$, cea mai mică etichetă preordonată la care se poate ajunge din $v$ pe un drum pentru care toate muchiile cu excepția ultimei rămân în subarborele cu rădăcina în $v$. Aceasta este minimul din mulțimea ce constă din valorile lui $L(w)$ în nodurile copil ale lui $v$ și a etichetelor preordonate ale nodurilor la care se poate ajunge din $v$ prin muchii ce nu aparțin lui $F$.
  • Similar, se calculează $H(v)$, cea mai mare etichetă preordonată la care se poate ajunge pe un drum pentru care toate muchiile cu excepția ultimei rămân în subarborele cu rădăcina în $v$. Acesta este maximul mulțimii formate din valorile lui $H(w)$ în nodurile copil ale lui $v$ și eticheta preordonată a nodurilor la care se poate ajunge din $v$ prin muchii ce nu aparțin lui $F$.
  • Pentru fiecare nod $w$ cu un nod părinte $v$, dacă $L(w)=w$ și $H(w)<w+ND(w)$ atunci muchia de la $v$ la $w$ este o punte.

Detecția de poduri cu descompuneri în lanț

Un algoritm foarte simplu de găsire de punți folosește descompuneri în lanțuri. Acestea nu numai că permit calculul tuturor punților unui graf, ci permit și citirea fiecărui punct de articulație al lui G, oferind un cadru general pentru testarea conexității în 2 muchii și în 2 noduri (cu extindere la teste de conexitate în 3 muchii și 3 noduri rulabile în timp liniar).

Descompunerile în lanțuri sunt ear-decompositions speciale ale unui arbore de parcurgere în adâncime T al lui G și poate fi calculat foarte simplu: fiecare nod se marchează ca nevizitat. Pentru fiecare nod v în ordine crescătoare a numărului de parcurgere în adâncime de la 1...n, se parcurge fiecare muchie transversală (adică fiecare muchie care nu aparține arborelui de parcurgere în adâncime) care este incidentă la v și se urmează calea muchiilor prin arbore înapoi la rădăcina lui T, oprindu-se la primul nod care marcat ca vizitat. În timpul unei astfel de parcurgeri, fiecare nod parcurs este marcat ca vizitat. Astfel, o parcurgere se oprește cel târziu la v și formează fie un drum orientat, fie un ciclu, începând cu v; această cale sau ciclu se numește lanț. Al i-lea lanț găsit prin această procedură este denumit C_i. C=C₁,C₂,... este apoi o descompunere în lanțuri a lui G.

Următoarele caracterizări permit apoi citirea eficientă a mai multor proprietăți ale lui G pe baza lui C, inclusiv toate punțile lui G. Fie C o descompunere în lanț a unui graf conectat simplu G=(V,E).

1. G este conex în 2 muchii dacă și numai dacă lanțurile din C sunt o partiție a mulțimii E.
2. O muchie e din G este punte dacă și numai dacă e nu este conținută în niciun lanț din C.
3. Dacă G este conex în 2 muchii, C este o Ear decomposition^⁠(d).
4. G este conex în 2 muchii, dacă și numai dacă G are grad minim 2 și C₁ este singurul ciclu în C.
5. Un nod v dintr-un graf conex în 2 muchii G este punct de articulație dacă și numai dacă v este primul nod al unui ciclu din C - C₁.
6. Dacă G este biconex, C este un open ear decomposition^⁠(d).