Bridge (teoria graficelor)

Un grafic cu 6 poduri (marcat cu roșu )

Un grafic nedirecționat, fără punți

În teoria graficelor , o punte (cunoscută și sub numele de pod , tăietură , arc tăiat sau istm ) este un arc a cărui eliminare crește numărul de componente conectate . În mod echivalent, un arc este o punte dacă și numai dacă nu este conținut în niciun ciclu .

Un grafic fără punți este echivalent cu un grafic cu un grad de conectivitate egal cu 2 pentru fiecare componentă non- trivială . O punte poate fi, de asemenea, identificată prin analiza matricei de conexiune .

Conjectura Cycle double cover

O problemă deschisă importantă referitoare la punți este conjectura cu dublă acoperire a ciclului propusă de Seymour și Szekeres (1978 și 1979, independent), care spune că orice grafic fără punți admite un set de cicluri care conțin fiecare arc exact de două ori. ^[1]

Algoritm pentru găsirea podurilor

Un algoritm de cost de calcul $O(|V|+|E|)$ ${\ displaystyle O (| V | + | E |)}$ ${\ displaystyle O (| V | + | E |)}$ pentru a găsi punți într-un grafic conectat a fost inventat de Robert Tarjan în 1974. ^[2] Există, de asemenea, o versiune distribuită a algoritmului. ^[3]

Algoritm:

Găsiți un copac minim care se întinde pe $G.$ ${\ displaystyle G}$ $G.$
Creați un copac înrădăcinat $T.$ ${\ displaystyle T}$ $T.$ din arborele capacului
Mergeți în copac $T.$ ${\ displaystyle T}$ $T.$ în precomandă și numerotează nodurile. Nodurile cele mai apropiate de rădăcină au un număr mai mic decât copiii lor.
Pentru fiecare nod de la $v$ $1$ {\ displaystyle v_ {1}} $v_1$ (nodul frunzei copacului) la 1 (rădăcina) faceți:
1. Numărați numărul descendenților $ND(v)$ ${\ displaystyle ND (v)}$ ${\ displaystyle ND (v)}$ pentru acel nod.
2. Numara $L(v)$ ${\ displaystyle L (v)}$ ${\ displaystyle L (v)}$ Și $H(v)$ ${\ displaystyle H (v)}$ ${\ displaystyle H (v)}$
3. Pentru fiecare $w$ ${\ displaystyle w}$ $w$ astfel încât $v\to w$ ${\ displaystyle v \ to w}$ ${\ displaystyle v \ to w}$ : de sine $L(w)\geq w$ ${\ displaystyle L (w) \ geq w}$ ${\ displaystyle L (w) \ geq w}$ și $H(w)<w+ND(w)$ ${\ displaystyle H (w) <w + ND (w)}$ ${\ displaystyle H (w) <w + ND (w)}$ asa de $(v,w)$ ${\ displaystyle (v, w)}$ ${\ displaystyle (v, w)}$ este un pod.

Definiții: un arc între nod $v$ ${\ displaystyle v}$ $v$ Și $w$ ${\ displaystyle w}$ $w$ care nu aparține copacului este indicat prin $v--w$ ${\ displaystyle v - w}$ ${\ displaystyle v - w}$ . Un arc de copac cu $v$ ${\ displaystyle v}$ $v$ ca tată este indicat de $v\to w$ ${\ displaystyle v \ to w}$ ${\ displaystyle v \ to w}$ .

$ND(v)=1+\sum _{v\to w}ND(w)$ ${\ displaystyle ND (v) = 1 + \ sum _ {v \ to w} ND (w)}$ ${\ displaystyle ND (v) = 1 + \ sum _ {v \ to w} ND (w)}$ unde este $v$ ${\ displaystyle v}$ $v$ este nodul părinte al $w$ ${\ displaystyle w}$ $w$ .

$ND(v)$ ${\ displaystyle ND (v)}$ ${\ displaystyle ND (v)}$ este numărul de descendenți ai $v$ ${\ displaystyle v}$ $v$ (inclusiv el însuși) în copacul acoperit înrădăcinat.

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

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

$L(v)$ ${\ displaystyle L (v)}$ ${\ displaystyle L (v)}$ Și $H(v)$ ${\ displaystyle H (v)}$ ${\ displaystyle H (v)}$ sunt etichetele nodului cu eticheta de precomandă minoră și majoră accesibilă de la $v$ ${\ displaystyle v}$ $v$ prin subarborele cu rădăcină $v$ ${\ displaystyle v}$ $v$ , și cel mult un arc care nu aparține copacului.

Acest algoritm funcționează deoarece $LD(v)$ ${\ displaystyle LD (v)}$ ${\ displaystyle LD (v)}$ , $H(v)$ ${\ displaystyle H (v)}$ ${\ displaystyle H (v)}$ Și $L(v)$ ${\ displaystyle L (v)}$ ${\ displaystyle L (v)}$ toate pot fi calculate pentru un singur nod $v$ ${\ displaystyle v}$ $v$ în consecință, le cunoaștem valorile din subarborele înrădăcinat în $v$ ${\ displaystyle v}$ $v$ . De asemenea, dacă și numai dacă arcul $v\to w$ ${\ displaystyle v \ to w}$ ${\ displaystyle v \ to w}$ este o punte, atunci este clar că în subarborele înrădăcinat în $w$ ${\ displaystyle w}$ $w$ , trebuie să fie imposibil să se ajungă la vreun nod care nu este un descendent al $w$ ${\ displaystyle w}$ $w$ . Acest lucru este ușor de verificat, deoarece subarborele înrădăcinat în $w$ ${\ displaystyle w}$ $w$ (adică toți descendenții lui w) constă din toate nodurile $\{w,w+1,\ldots ,w+ND(w)-1\}$ ${\ displaystyle \ {w, w + 1, \ ldots, w + ND (w) -1 \}}$ ${\ displaystyle \ {w, w + 1, \ ldots, w + ND (w) -1 \}}$ atunci putem verifica doar dacă $L(w),H(w)$ ${\ displaystyle L (w), H (w)}$ ${\ displaystyle L (w), H (w)}$ sunt în acest set sau nu pentru a verifica dacă un arc este o punte.

Poduri în copaci

Un arc $E=uv$ ${\ displaystyle E = uv}$ ${\ displaystyle E = uv}$ a unui copac $T.$ ${\ displaystyle T}$ $T.$ este un pod în $T.$ ${\ displaystyle T}$ $T.$ dacă și numai dacă gradul nodurilor $tu$ ${\ displaystyle u}$ $tu$ Și $v$ ${\ displaystyle v}$ $v$ este mai mare de 1. Podurile sunt definite și pentru graficele direcționate ^[4]

Notă

^ Ciclează capacul dublu
^ "O notă despre găsirea podurilor unui grafic", Robert Endre Tarjan, Informatii privind prelucrarea scrisorilor, aprilie 1974 pp160-161.
^ David Pritchard
^ Rao, SB ; Ramachandra Rao, A. Numărul de punți și puncte de articulare într-un grafic puternic orientat. (Engleză) Acta Math. Acad. Ski. Hung. 22, 411-421 (1972).

Bibliografie

Béla Bollobás , Teoria graficului modern , GTM 184 , Springer Verlag , 1998. Pagina 6.
Robert Endre Tarjan , O notă despre găsirea podurilor unui grafic , în Information Processing Letters , vol. 2, nr. 6, pp. 160–161, DOI : 10.1016 / 0020-0190 (74) 90003-9 .

Controlul autorității	LCCN ( EN ) sh90003473

Portalul de matematică : accesați intrările Wikipedia care se ocupă de matematică

[1] Ciclează capacul dublu

[2] "O notă despre găsirea podurilor unui grafic", Robert Endre Tarjan, Informatii privind prelucrarea scrisorilor, aprilie 1974 pp160-161.

[3] David Pritchard

[4] Rao, SB ; Ramachandra Rao, A. Numărul de punți și puncte de articulare într-un grafic puternic orientat. (Engleză) Acta Math. Acad. Ski. Hung. 22, 411-421 (1972).

[1]

[2]

[3]

[4]