Artikulationspunkt

Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 18. juli 2021; verifikation kræver 1 redigering .

Et artikulationspunkt i grafteori er et toppunkt af en graf , ved fjernelse af hvilket antallet af forbundne komponenter stiger. Udtrykkene "adskillende vertex" og "hængsel" bruges også til at betegne dette koncept.

Definitioner

Et toppunkt i en graf kaldes et hængsel , hvis subgrafen opnået fra grafen ved at fjerne toppunktet og alle kanter, der falder ind på den, består af flere forbundne komponenter end den originale graf . $v$ $G$ $G_{1}$ $G$ $v$ $G$

Begrebet biconnectivity er også relateret til begrebet et hængsel. En dobbeltforbundet graf er en forbundet graf , der ikke indeholder hængsler. Den biforbundne komponent er den maksimale (ved inkludering) dobbeltforbundne subgraf af den originale graf. Biforbundne komponenter kaldes nogle gange blokke.

Hængslets kantanalog er broen . En bro er en kant af en graf, hvis fjernelse resulterer i en stigning i antallet af forbundne komponenter i grafen.

Find hængsler

En effektiv løsning på problemet med at finde alle hængslerne i en graf er baseret på dybde-først søgealgoritmen .

Lad en graf gives . Betegn ved sættet af alle grafens hjørnepunkter, der støder op til . Antag, at vi har scannet grafen i dybden, startende fra et eller andet vilkårligt vertex. Vi opregner alle hjørnerne af grafen i den rækkefølge, vi indtastede dem i, og tildeler et tilsvarende nummer til hvert hjørne . Hvis vi først kom til toppunktet fra toppunktet , så vil vi kalde toppunktet for efterkommer af , og forfader til . Mængden af alle efterkommere af et toppunkt er angivet med . Angiv med det mindste antal blandt alle knudepunkter, der støder op til og med de knudepunkter, som vi kom til langs stien, der går igennem . $G$ $Adj(v)$ $v$ $v$ $n(v)$ $u$ $v$ $u$ $v$ $v$ $u$ $v$ $Ch(v)$ $Lav(v)$ $v$ $v$

Det er klart, at værdien kan beregnes rekursivt, direkte i processen med at krydse i dybden: hvis toppunktet i øjeblikket betragtes , og det er umuligt at gå fra det til et toppunkt, der endnu ikke er besøgt (dvs. du skal vende tilbage til forfaderen eller stoppe gennemkørslen, hvis det er startpunktet), så er det allerede beregnet for alle dets efterkommere, og derfor er det muligt at udføre de tilsvarende beregninger ved hjælp af formlen $Lav(v)$ $v$ $v$ $v$ $lav$

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

Ved at kende værdien for alle hjørner af grafen er det muligt entydigt at bestemme alle dens hængsler i henhold til følgende to regler: $Lav(v)$

Startspidsen (det vil sige den, hvorfra vi startede gennemkørslen) er et hængsel , hvis og kun hvis det har mere end et barn.
Et andet toppunkt end startpunktet er et hængsel, hvis og kun hvis det har et barn u sådan, at . $v$ $Low(u)=n(v)$

Som et eksempel kan du overveje anvendelsen af den beskrevne algoritme på grafen vist i figuren til højre. Tallene, der markerer hjørnerne, svarer til en af de mulige varianter af dybde-først-søgningen. I denne rækkefølge har hvert af hjørnerne præcis ét barn, bortset fra toppunkt 6, som ikke har nogen børn. Startspids 1 har et enkelt barn, så det er ikke et hængsel. For de resterende knudepunkter beregner vi værdierne af funktionen af interesse for os:

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

Vertex 2 har et barn 3, og 5 har et barn 6 - i begge tilfælde er den ønskede relation opfyldt . Derfor er 2 og 5 hængsler. Der er ingen andre hængsler i denne graf. $Low(u)=n(v)$

Se også

Forbindelseskomponent af en graf

Litteratur

V. E. Alekseev, V. A. Talanov. Grafer og algoritmer. Datastrukturer. Beregningsmodeller. — M. : BINOM. Knowledge Lab, 2006. - ISBN 5-94774-543-7 .