Trenner (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

Die Menge ${\displaystyle S}$ ist ein ${\displaystyle A}$-${\displaystyle B}$-Trenner

Der Knoten ${\displaystyle a}$ ist ein Gelenkpunkt, die Kante ${\displaystyle e}$ ist eine Brücke.

Es seien ${\displaystyle G=(V,E)}$ ein einfacher Graph und ${\displaystyle A,B\subset V}$ Teilmengen der Knotenmenge ${\displaystyle V}$.

Ein Paar ${\displaystyle Z=(X,Y)}$, bestehend aus einer Knotenmenge ${\displaystyle X\subseteq V}$ und einer Kantenmenge ${\displaystyle Y\subseteq E}$, heißt ${\displaystyle A}$-${\displaystyle B}$-Trenner oder ${\displaystyle A}$-${\displaystyle B}$-Separator des Graphen, wenn jeder ${\displaystyle A}$-${\displaystyle B}$-Weg wenigstens einen Knoten aus ${\displaystyle X}$ oder eine Kante aus ${\displaystyle Y}$ enthält. Man sagt dann auch, dass ${\displaystyle Z}$ die Knotenmengen ${\displaystyle A}$ und ${\displaystyle B}$ trennt.

Sind ${\displaystyle A=\{a\}}$ und ${\displaystyle B=\{b\}}$ einelementig, so spricht man auch von der Trennung der Knoten ${\displaystyle a}$ und ${\displaystyle b}$.

Ein Paar ${\displaystyle Z=(X,Y)}$ trennt den Graphen ${\displaystyle G}$ genau dann, wenn ${\displaystyle Z}$ mindestens zwei Knoten aus ${\displaystyle G}$ trennt.

Äquivalente Definition

Teilweise wird in der Literatur ein ${\displaystyle A}$-${\displaystyle B}$-Trenner für einen Graphen ${\displaystyle G=(V,E)}$ auch als eine Menge ${\displaystyle X\subseteq V\cup E}$ von Knoten und Kanten definiert, so dass jeder ${\displaystyle A}$-${\displaystyle B}$-Weg mindestens ein Element aus ${\displaystyle X}$ enthält. Die weitergehenden Definitionen erfolgen analog zu den oberen.

Spezialfälle

Artikulation

Ist ${\displaystyle v\in V}$ ein Knoten, der zwei Knoten trennt, die zur selben Zusammenhangskomponente des Graphen gehören, so nennt man ${\displaystyle v}$ eine Artikulation, einen Gelenkpunkt oder einen Schnittknoten des Graphen. Einem Gelenkpunkt entspricht also ein Trenner ${\displaystyle Z=(X,Y)}$ mit ${\displaystyle X=\{v\}}$ und ${\displaystyle Y=\emptyset }$.

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

Brücke

Ist ${\displaystyle e\in E}$ eine Kante, die ihre beiden Endknoten trennt, so nennt man ${\displaystyle e}$ eine Brücke. Einer Brücke entspricht also ein Trenner ${\displaystyle Z=(X,Y)}$ mit ${\displaystyle X=\emptyset }$ und ${\displaystyle Y=\{e\}}$. Äquivalent dazu ist, dass ${\displaystyle e}$ in keinem Kreis des Graphen liegt.

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

Verwendung

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

• Reinhard Diestel: Graphentheorie. 4. Auflage. Springer, Berlin 2010, ISBN 978-3-642-14911-5 (englisch, diestel-graph-theory.com – Erstausgabe: 1996).