Artikulációs pont

Az oldal jelenlegi verzióját még nem ellenőrizték tapasztalt közreműködők, és jelentősen eltérhet a 2021. július 18-án felülvizsgált verziótól ; az ellenőrzéshez 1 szerkesztés szükséges .

Az artikulációs pont a gráfelméletben egy gráf csúcsa , amelynek eltávolításakor megnő az összekapcsolt komponensek száma. Az "elválasztó csúcs" és a "csuklópánt" kifejezéseket is használják ennek a fogalomnak a jelölésére.

Definíciók

Egy gráf csúcsát csuklónak nevezzük , ha a gráfból a csúcs és a rá eső élek eltávolításával kapott részgráf több összefüggő komponensből áll, mint az eredeti gráf . $v$ $G$ $G_{1}$ $G$ $v$ $G$

A bikonnektivitás fogalma összefügg a csuklópánt fogalmával is. A duplán összefüggő gráf olyan összefüggő gráf , amely nem tartalmaz csuklópántokat. A bikapcsolt komponens az eredeti gráf maximális (befoglalással) kétszeresen összefüggő részgráfja. A kettős kapcsolódású alkatrészeket néha blokknak is nevezik.

A csuklópánt élanalógja a híd . A híd a gráf olyan éle, amelynek eltávolítása a gráf összekapcsolt komponenseinek számának növekedését eredményezi.

Zsanérok keresése

A gráf összes csuklópántjának megtalálásának problémájának hatékony megoldása a mélységi keresési algoritmuson alapul .

Legyen adott egy gráf . Jelölje a -val szomszédos összes gráfcsúcs halmazával . Tegyük fel, hogy a gráfot mélységben pásztáztuk, valamilyen tetszőleges csúcsból kiindulva. Felsoroljuk a gráf összes csúcsát abban a sorrendben , ahogyan beírtuk , és minden csúcshoz hozzárendeljük a megfelelő számot . Ha először a csúcsból jutottunk el a csúcshoz , akkor a csúcsot a leszármazottjának és az ősének nevezzük . Egy csúcs összes leszármazottjának halmazát jelöli . Jelölje a minimális számmal a szomszédos és azokkal a csúcsokkal, amelyekhez az áthaladó útvonal mentén eljutottunk . $G$ $Adj(v)$ $v$ $v$ $n(v)$ $u$ $v$ $u$ $v$ $v$ $u$ $v$ $Ch(v)$ $Low(v)$ $v$ $v$

Nyilvánvaló, hogy az érték rekurzívan, közvetlenül a mélységi bejárás során számítható: ha éppen a csúcsot veszik figyelembe , és nem lehet onnan eljutni egy még meg nem látogatott csúcshoz (pl. vissza kell térni az őshöz , vagy le kell állítani a bejárást, ha a kezdő csúcs ), akkor az összes leszármazottjára már ki van számítva, és ezért lehetséges a megfelelő számítások elvégzése a képlet segítségével $Low(v)$ $v$ $v$ $v$ $Low$

$Low(v)=\min \left\{\min _{x\in Ch(v)}Low(x),\min _{y\in Adj(v)/Ch(v)}n( y)\jobbra\}.$

A gráf összes csúcsának értékének ismeretében lehetőség van az összes csuklópont egyedi meghatározására a következő két szabály szerint: $Low(v)$

A kiinduló csúcs (vagyis az, ahonnan a bejárást elkezdtük) akkor és csak akkor zsanér, ha egynél több gyermeke van.
A kiinduló csúcstól eltérő csúcs akkor és csak akkor csukló, ha olyan u gyermeke van, hogy . $v$ $Low(u)=n(v)$

Példaként tekintsük a leírt algoritmus alkalmazását a jobb oldali ábrán látható grafikonra. A csúcsokat jelölő számok a mélységi keresés egyik lehetséges változatának felelnek meg. Ebben a sorrendben minden csúcsnak pontosan egy gyermeke van, kivéve a 6. csúcsot, amelynek nincs gyermeke. Az 1. kezdőcsúcsnak egyetlen gyermeke van, tehát nem zsanér. A fennmaradó csúcsokhoz kiszámítjuk a számunkra érdekes függvény értékeit:

$Alacsony(6)=5, Alacsony(5)=2, Alacsony(4)=2, Alacsony(3)=2, Alacsony(2)=1$ .

A 2. csúcsnak van egy gyermeke 3, és az 5-nek van egy gyermeke 6 - mindkét esetben teljesül a kívánt reláció . Ezért a 2 és 5 zsanérok. Ezen a grafikonon nincs más zsanér. $Low(u)=n(v)$

Lásd még

Egy gráf összekapcsolhatósági összetevője

Irodalom

V. E. Alekszejev, V. A. Talanov. Grafikonok és algoritmusok. Adatstruktúrák. Számítási modellek. — M. : BINOM. Knowledge Lab, 2006. - ISBN 5-94774-543-7 .