Bridge (teoria grafurilor)

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită pe 10 noiembrie 2021; verificarea necesită 1 editare .

O punte este o muchie în teoria grafurilor , a cărei îndepărtare crește numărul de componente conectate [1] . Astfel de nervuri sunt cunoscute și sub denumirea de nervuri de tăiere , arcuri de tăiere sau istmuri . O definiție echivalentă este aceea că o muchie este o punte dacă și numai dacă nu este conținută în niciun ciclu .

Copaci și păduri

Un grafic cu vârfuri poate conține cel mult poduri, deoarece adăugarea unei laturi suplimentare va duce inevitabil la apariția unui ciclu. Graficele care au exact poduri sunt cunoscute sub numele de copaci , iar graficele în care orice margine este un pod sunt păduri . $n$ $n-1$ $n-1$

În orice graf nedirecționat, există o relație de echivalență a vârfurilor , conform căreia două vârfuri sunt echivalente dacă există două căi care le conectează care nu se intersectează de-a lungul muchiilor (orice vârf este considerat echivalent cu el însuși). Clasele de echivalență ale acestei relații sunt numite componente conectate cu 2 muchii , iar punțile unui graf sunt exact acele muchii ale căror capete aparțin unor componente diferite. Diagrama bloc de legătură a unui grafic are un vârf pentru orice componentă netrivială și o muchie pentru fiecare punte [2] .

Conexiune cu conexiune la vârf

Podurile sunt strâns legate de conceptul de balamale , vârfuri care intră în orice cale care leagă două vârfuri. Cele două vârfuri ale unui pod sunt articulate, cu excepția cazului în care sunt de gradul 1, deși marginile fără punte pot fi, de asemenea, articulate la ambele capete. Ca și graficele fără punți, care sunt conectate cu 2 muchii, graficele fără balamale sunt conectate cu 2 vârfuri .

În graficele cubice , orice balama este un vârf terminal al cel puțin o punte.

Grafice fără punți

După cum sugerează și numele, un grafic fără punte este un grafic care nu are punți. Condițiile echivalente sunt că fiecare componentă conexă a unui grafic are o descompunere în ureche deschisă [3] , că fiecare componentă conexă este conectată cu 2 muchii sau (după teorema lui Robbins ) că fiecare componentă conectată are o orientare puternică [3 ] ] .

O problemă deschisă importantă legată de punți este conjectura de acoperire cu ciclu dublu , propusă de Seymour și Székeres (în 1978 și 1979, independent), care afirmă că orice graf fără punte poate fi acoperit de cicluri simple care conțin fiecare muchie de două ori [4] .

Algoritmul de căutare a podului lui Tarjan

Primul algoritm pentru găsirea punților într-un grafic cu timp de rulare liniar a fost descris de Robert Tarjan în 1974 [5] . Algoritmul funcționează astfel:

Găsiți pădurea care se întinde pe grafic . $G$
Creați o pădure cu rădăcini dintr-un copac întins. $F$
Ocolim pădurea în ordine directă și numărăm vârfurile. Vârfurile părinte sunt acum numerotate mai jos decât copiii lor. $F$

Vom nota marginea (v,w) conținută în arbore ca , și nu conținută ca . $v\la w$ $v-w$

Pentru fiecare vârf în timpul traversării directe, executăm: $v$
- Calculăm numărul de copii pentru vârf, adăugând unul când trecem la următorul vârf (inclusiv vârf ). $ND(v)$ $v$

$ND(v) = 1 + \sum_{v \to w} ND(w)$ .

- Calculați , numărul minim care poate fi atins de la vârf , urmând muchiile subarborescului începând de la (cu excepția ultimei muchii). Acesta este numărul minim din mulțimea format din valorile descendenților vârfului și numerele de vârfuri la care se poate ajunge de -a lungul muchiilor care nu aparțin . $L(v)$ $v$ $v$ $L(w)$ $v$ $v$ $F$

$L(v)=\min(\{v\}\cup \{L(w)\mid v\to w\}\cup \{w\mid v--w\})$

- În mod similar, calculați , cel mai mare număr care poate fi atins urmărind marginile subarborescului începând cu . Acesta este numărul maxim din setul de valori format din valorile descendenților vârfului și numerele vârfurilor la care se poate ajunge de -a lungul muchiilor care nu aparțin . $H(v)$ $v$ $H(w)$ $v$ $v$ $F$

$H(v)=\max(\{v\}\cup \{H(w)\mid v\to w\}\cup \{w\mid v--w\})$

- Pentru fiecare vârf cu un părinte , verificăm dacă și , atunci muchia de la până este o punte. $w$ $v$ $L(w) = w$ $H(w) <w + ND(w)$ $v$ $w$

Dacă este o punte, atunci este clar că dintr-un subarboresc înrădăcinat nu ar trebui să existe nicio modalitate de a merge la un vârf care nu aparține acestui subarboresc. Pentru a verifica acest lucru, este suficient să verificăm L(w), H(w) - condiția înseamnă că nu vom merge la vârful care se află mai aproape de rădăcină, iar condiția înseamnă că nu vom merge la alt subarbore. $v\la w$ $w$ $L(w) = w$ $H(w) <w + ND(w)$

Găsirea punților folosind descompunerea în lanț

Un algoritm foarte simplu de căutare a podurilor [6] se bazează pe descompunerea în lanț. Descompunerea lanțului nu numai că dă toate punțile, ci produce și toate balamalele (și componentele dublu conectate) ale graficului G , oferind astfel o bază pentru testarea conectivității marginii și vârfurilor 2 (și această metodă poate fi extinsă la verificarea liniară în timp). de margine- și vârf 3-conexiuni).

Descompunerea în lanț este un caz special de descompunere a urechii bazat pe căutarea în adâncime pe arborele T al graficului G și poate fi făcută foarte simplu:

lăsați toate vârfurile să fie marcate ca nevizitate. Pentru toate vârfurile v în ordinea crescătoare a numerelor de parcurgere 1... n , parcurgem fiecare muchie înapoi (adică o muchie care nu aparține arborelui de traversare) incidentă la v și urmărim marginile arborelui până la rădăcină până când vom întâlni vârful vizitat. În timpul acestei treceri, marchem toate nodurile trecute ca vizitate. Această trecere se va termina cu o cale sau o buclă care începe la v , vom numi aceasta cale sau buclă un lanț . Vom nota i --lea șir obținut printr-o procedură precum C i . C=C 1 ,C 2 ,... este atunci o partiție a graficului G în lanțuri .

Următoarele proprietăți fac posibilă obținerea eficientă a unor informații despre graficul G din C , inclusiv toate punțile [6] :

Fie C o descompunere în lanț a unui graf conex simplu G=(V,E) .

G este conectat cu 2 muchii dacă și numai dacă lanțurile lui C conțin toate muchiile din E.
O muchie e în G este o punte dacă și numai dacă e nu este conținut în niciun lanț din C .
Dacă G este conectat cu două margini, C este o descompunere a urechii .
G este legat de 2 vârfuri dacă și numai dacă G are gradul minim 2 și C 1 este singurul ciclu din C .
Un vârf v într-un grafic G conectat cu 2 muchii este o balama dacă și numai dacă v este primul vârf dintr-un ciclu de la C - C 1 .
Dacă G este conectat la vârful 2, C este o descompunere deschisă în urechi .

Note

↑ Bela Bollobas. Teoria modernă a grafurilor. - New York: Springer-Verlag, 1998. - T. 184. - P. 6. - (Texte de absolvire în matematică). — ISBN 0-387-98488-7 . - doi : 10.1007/978-1-4612-0619-4 .
^ Jeffery Westbrook, Robert E. Tarjan. Menținerea componentelor conectate prin punte și biconectate on-line // Algorithmica. - 1992. - T. 7 , nr. 5-6 . - S. 433-464 . - doi : 10.1007/BF01758773 .
↑ 1 2 H. E. Robbins. O teoremă asupra graficelor, cu o aplicație la o problemă de control al traficului // The American Mathematical Monthly . - 1939. - T. 46 . - S. 281-283 .
↑ F. Jaeger. Analele matematicii discrete 27 - Cicluri în grafice. - 1985. - T. 27. - S. 1-12. — (Studii de matematică din Olanda de Nord). - doi : 10.1016/S0304-0208(08)72993-1 .
↑ R. Endre Tarjan. O notă despre găsirea punților unui grafic // Scrisori de procesare a informațiilor. - T. 2 , nr. 6 . - S. 160-161 . - doi : 10.1016/0020-0190(74)90003-9 .
↑ 1 2 Jens M. Schmidt. Un test simplu asupra conectivității cu 2 vârfuri și 2 margini // Scrisori de procesare a informațiilor. - 2013. - T. 113 , nr. 7 . - S. 241-244 . - doi : 10.1016/j.ipl.2013.01.016 .