Quelltext der Seite Gelenkpunkt (Graphentheorie)

[[Datei:Undirected chain articulation points.svg|mini|hochkant=0.5|Ein ungerichteter Graph mit ''n''=5 Knoten und 3 Gelenkpunkten (rot markiert)]]

[[Datei:Undirected.svg|mini|hochkant=0.5|Ein ungerichteter Graph ohne Gelenkpunkte]]
In der [[Graphentheorie]] bezeichnet ein '''Gelenkpunkt''', '''Artikulationspunkt''', '''Artikulation''' oder '''Schnittknoten''' einen Knoten eines [[Graph (Graphentheorie)|Graphen]], dessen Entfernen die Anzahl der [[Zusammenhang von Graphen|zusammenhängenden Teilgraphen]] erhöhen würde. Wenn der Graph vor dem Entfernen des Knotens zusammenhängend war, ist er danach unzusammenhängend. Ein Gelenkpunkt ist ein Spezialfall eines [[Trenner (Graphentheorie)|Trenners]].

Der Begriff des '''Gelenkpunkts''' ist auch für gerichtete Graphen wohldefiniert<ref>Rao, S.B.; Ramachandra Rao, A. ''The number of cut vertices and cut arcs in a strong directed graph.'' Acta Math. Acad. Sci. Hung. 22, 411–421 (1972)</ref>, wird aber hauptsächlich für ungerichtete Graphen verwendet. Grundsätzlich kann ein zusammenhängender ungerichteter Graph mit n Knoten nicht mehr als n-2 Gelenkpunkte besitzen.

Eine [[Trenner (Graphentheorie)|Brücke]] ist eine Kante analog zu einem Gelenkpunkt; das heißt, das Entfernen der Brücke erhöht die Anzahl der zusammenhängenden Teilgraphen.

== Finden von Gelenkpunkten ==

Ein trivialer <math>O(nm)</math> Algorithmus:
 C = leere Menge (nach Beenden des Algorithmus wird sie die Gelenkpunkte enthalten)
 a = Anzahl der zusammenhängenden Teilgraphen (gefunden mit [[Tiefensuche]]/[[Breitensuche]])
 for alle Knoten i in V auf den Kanten zeigen
     b = Anzahl der zusammenhängenden Teilgraphen, wenn i entfernt wird
     if b > a
         i ist ein Gelenkpunkt
         C = C + {i}
     endif
 endfor

Es gibt einen Algorithmus, der mittels [[Tiefensuche]] eine wesentlich bessere Laufzeit von <math>O(n+m)</math> erreicht<ref>[http://www.eecs.wsu.edu/~holder/courses/CptS223/spr08/slides/graphapps.pdf Präsentation des  ''O''(''n''+''m'') Algorithmus] (auf Englisch; PDF; 447&nbsp;kB)</ref>.

== Gelenkpunkte in Bäumen ==
Ein Knoten eines [[Baum (Graphentheorie)|Baums]] G ist genau dann ein Gelenkpunkt, wenn der [[Grad (Graphentheorie)|Grad]] des Knotens größer als 1 ist.

== Literatur ==
* Nirmala, K.; Ramachandra Rao, A. ''The number of cut vertices in a regular graph.''  Cah. Cent. Étud. Rech. Opér. 17, 295–299 (1975).

== Weblinks ==
* [http://mathworld.wolfram.com/ArticulationVertex.html Wolfram Mathworld: "Cut-Vertex"] (auf Englisch)

== Einzelnachweise ==
<references />

[[Kategorie:Grundbegriff (Graphentheorie)]]