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
BearbeitenEs 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
BearbeitenTeilweise 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
BearbeitenArtikulation
BearbeitenIst 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
BearbeitenIst 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
BearbeitenTrenner 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- Reinhard Diestel: Graphentheorie. 4. Auflage. Springer, Berlin 2010, ISBN 978-3-642-14911-5 (englisch, diestel-graph-theory.com – Erstausgabe: 1996).