Punte (teoria grafurilor)

De la Wikipedia, enciclopedia liberă
Jump to navigation Jump to search
Graf cu 16 noduri și 6 punți (evidențiate cu roșu)
Graf neorientat conex fără punți

În teoria grafurilor, o punte este o muchie a unui graf a cărei ștergere ar crește numărul de componente conexe⁠(d).[1] 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.

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[modificare | modificare sursă]

Un graf cu noduri poate conține cel mult punți, deoarece adăugarea de muchii suplimentare trebuie să creeze un ciclu. Grafurile cu exact 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.[2]

Legătura cu conectivitatea nodurilor[modificare | modificare sursă]

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⁠(d) 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[modificare | modificare sursă]

Un graf fără punți este un graf care nu are nicio punte. Condiții echivalente sunt ca fiecare componentă conexă⁠(d) a grafului are o open ear decomposition⁠(d),[3] 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.[4]

Algoritmul de găsire a punților al lui Tarjan[modificare | modificare sursă]

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

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

Detecția de poduri cu descompuneri în lanț[modificare | modificare sursă]

Un algoritm foarte simplu de găsire de punți[6] 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 Ci. C=C1,C2,... 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 C1 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 - C1.
  6. Dacă G este biconex, C este un open ear decomposition⁠(d).

Note[modificare | modificare sursă]

  1. ^ Bollobás, Béla (), Modern Graph Theory, Graduate Texts in Mathematics, 184, New York: Springer-Verlag, p. 6, doi:10.1007/978-1-4612-0619-4, ISBN 0-387-98488-7, MR 1633290 .
  2. ^ Westbrook, Jeffery; Tarjan, Robert E. (), „Maintaining bridge-connected and biconnected components on-line”, Algorithmica, 7 (5-6): 433–464, doi:10.1007/BF01758773  Mai multe valori specificate pentru |DOI= și |doi= (ajutor).
  3. ^ Robbins, H. E. (), „A theorem on graphs, with an application to a problem of traffic control”, American Mathematical Monthly⁠(d), 46: 281–283, doi:10.2307/2303897  Mai multe valori specificate pentru |author-link= și |authorlink= (ajutor); Mai multe valori specificate pentru |DOI= și |doi= (ajutor).
  4. ^ Jaeger, F. (), „A survey of the cycle double cover conjecture”, Annals of Discrete Mathematics 27 – Cycles in Graphs, North-Holland Mathematics Studies, 27, pp. 1–12, doi:10.1016/S0304-0208(08)72993-1  Mai multe valori specificate pentru |DOI= și |doi= (ajutor).
  5. ^ Tarjan, R. Endre, „A note on finding the bridges of a graph”, Information Processing Letters, 2 (6): 160–161, doi:10.1016/0020-0190(74)90003-9  Mai multe valori specificate pentru |DOI= și |doi= (ajutor).
  6. ^ Schmidt, Jens M. (), „A Simple Test on 2-Vertex- and 2-Edge-Connectivity”, Information Processing Letters, 113 (7): 241–244, doi:10.1016/j.ipl.2013.01.016  Mai multe valori specificate pentru |DOI= și |doi= (ajutor).