Artikulationspunkt

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 18 juli 2021; verifiering kräver 1 redigering .

En artikulationspunkt i grafteorin är en vertex av en graf , vid borttagning av vilken antalet anslutna komponenter ökar. Termerna "separerande vertex" och "gångjärn" används också för att beteckna detta koncept.

Definitioner

En vertex i en graf kallas ett gångjärn om subgrafen som erhålls från grafen genom att ta bort vertexen och alla kanter som faller in på den består av fler sammankopplade komponenter än den ursprungliga grafen . $v$ $G$ $G_{1}$ $G$ $v$ $G$

Begreppet biconnectivity är också relaterat till begreppet ett gångjärn. En dubbelkopplad graf är en sammankopplad graf som inte innehåller gångjärn. Den dubbelanslutna komponenten är den maximala (genom inkludering) dubbelt anslutna subgrafen av den ursprungliga grafen. Bikopplade komponenter kallas ibland block.

Gångjärnets kantanalog är bron . En bro är en kant av en graf vars borttagning resulterar i en ökning av antalet anslutna komponenter i grafen.

Hitta gångjärn

En effektiv lösning på problemet med att hitta alla gångjärn i en graf är baserad på djupet-först-sökalgoritmen .

Låt en graf ges . Beteckna med uppsättningen av alla grafens hörn intill . Anta att vi har skannat grafen på djupet, utgående från någon godtycklig vertex. Vi räknar upp alla hörn i grafen i den ordning som vi skrev in dem och tilldelar ett motsvarande nummer till varje hörn . Om vi först kom till spetsen från spetsen , då kallar vi spetsen för ättling till och förfader till . Uppsättningen av alla avkomlingar av en vertex betecknas med . Beteckna med minimitalet bland alla hörn som gränsar till och med de hörn som vi kom till längs vägen som går igenom . $G$ $Adj(v)$ $v$ $v$ $n(v)$ $u$ $v$ $u$ $v$ $v$ $u$ $v$ $Ch(v)$ $Low(v)$ $v$ $v$

Det är uppenbart att värdet kan beräknas rekursivt, direkt i processen med att korsa på djupet: om hörn för tillfället övervägs och det är omöjligt att gå från det till ett hörn som ännu inte har besökts (dvs. du måste återvända till förfadern , eller stoppa genomgången, om det är startpunkten ), då har det redan beräknats för alla dess ättlingar, och därför är det möjligt att utföra motsvarande beräkningar med formeln $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)\right\}.$

Genom att känna till värdet för alla hörn i grafen är det möjligt att unikt bestämma alla dess gångjärn enligt följande två regler: $Low(v)$

Startpunkten (det vill säga den från vilken vi startade traverseringen) är ett gångjärn om och bara om det har mer än ett barn.
En annan vertex än startpunkten är ett gångjärn om och endast om den har ett barn u sådan att . $v$ $Low(u)=n(v)$

Som ett exempel, överväg tillämpningen av den beskrivna algoritmen på grafen som visas i figuren till höger. Siffrorna som markerar hörnen motsvarar en av de möjliga varianterna av djup-först-sökningen. I denna ordning har vart och ett av hörnen exakt ett barn, förutom vertex 6, som inte har några barn. Startpunkt 1 har ett enda barn, så det är inte ett gångjärn. För de återstående hörnen beräknar vi värdena för funktionen av intresse för oss:

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

Vertex 2 har ett barn 3 och 5 har ett barn 6 - i båda fallen är den önskade relationen uppfylld . Därför är 2 och 5 gångjärn. Det finns inga andra gångjärn i denna graf. $Low(u)=n(v)$

Se även

Anslutningskomponent i en graf

Litteratur

V. E. Alekseev, V. A. Talanov. Grafer och algoritmer. Data struktur. Beräkningsmodeller. — M. : BINOM. Knowledge Lab, 2006. - ISBN 5-94774-543-7 .