Trenner (Graphentheorie)

Begriff aus der Graphentheorie

Trenner sind in der Graphentheorie besondere Teilmengen von Knoten und Kanten eines Graphen, bei deren Entfernen aus dem Graphen bestimmte Wege im Graphen unmöglich werden.

Definition

Bearbeiten
 
Die Menge   ist ein  - -Trenner
 
Der Knoten   ist ein Gelenkpunkt, die Kante   ist eine Brücke.

Es seien   ein einfacher Graph und   Teilmengen der Knotenmenge  .

Ein Paar  , bestehend aus einer Knotenmenge   und einer Kantenmenge  , heißt  - -Trenner oder  - -Separator des Graphen, wenn jeder  - -Weg wenigstens einen Knoten aus   oder eine Kante aus   enthält. Man sagt dann auch, dass   die Knotenmengen   und   trennt.

Sind   und   einelementig, so spricht man auch von der Trennung der Knoten   und  .

Ein Paar   trennt den Graphen   genau dann, wenn   mindestens zwei Knoten aus   trennt.

Äquivalente Definition

Bearbeiten

Teilweise wird in der Literatur ein  - -Trenner für einen Graphen   auch als eine Menge   von Knoten und Kanten definiert, so dass jeder  - -Weg mindestens ein Element aus   enthält. Die weitergehenden Definitionen erfolgen analog zu den oberen.

Spezialfälle

Bearbeiten

Artikulation

Bearbeiten

Ist   ein Knoten, der zwei Knoten trennt, die zur selben Zusammenhangskomponente des Graphen gehören, so nennt man   eine Artikulation, einen Gelenkpunkt oder einen Schnittknoten des Graphen. Einem Gelenkpunkt entspricht also ein Trenner   mit   und  .

Besitzt ein zusammenhängender Graph einen Gelenkpunkt, so ist seine Knotenzusammenhangszahl gleich 1 und er wird als separabel bezeichnet.

Ist   eine Kante, die ihre beiden Endknoten trennt, so nennt man   eine Brücke. Einer Brücke entspricht also ein Trenner   mit   und  . Äquivalent dazu ist, dass   in keinem Kreis des Graphen liegt.

Besitzt ein zusammenhängender Graph eine Brücke, so ist seine Kantenzusammenhangszahl gleich 1.

Verwendung

Bearbeiten

Trenner gehören zu den Grundbegriffen der Graphentheorie. Sie werden beispielsweise verwendet, um die Grapheigenschaften k-Zusammenhang und Kantenzusammenhang zu definieren. In diesen beiden Fällen interessieren Trenner, die nur aus Knoten bzw. nur aus Kanten bestehen.

Literatur

Bearbeiten