Trenner (Graphentheorie)

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.

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.

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