Trenner (Graphentheorie)

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

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 | Quelltext 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 | Quelltext 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 | Quelltext bearbeiten]

Artikulation[Bearbeiten | Quelltext 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.

Brücke[Bearbeiten | Quelltext bearbeiten]

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 | Quelltext 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 | Quelltext bearbeiten]