Schnitt (Graphentheorie)

Partition der Knotenmenge eines Graphen

Ein Schnitt bezeichnet in der Graphentheorie eine Partition der Knotenmenge eines Graphen. Eine besondere Bedeutung kommt Schnitten im Zusammenhang mit Netzwerken zu. Schnitte können aber auch unabhängig von Netzwerken definiert und untersucht werden.

Definition

Bearbeiten
 
Knotenmenge   (rot) und Restmenge   (schwarz) eines Schnittes und die kreuzenden Schnittkanten   (blau)

Jede nichtleere Teilmenge   der Knotenmenge eines ungerichteten Graphen   definiert einen Schnitt   des Graphen.

Davon wird eindeutig die Menge der Schnittkanten

 

induziert. Sie umfasst alle Kanten des Graphen, von denen ein Endknoten in der Teilmenge   liegt und der andere in der Menge der übrigen Knoten.

In gerichteten Graphen   gibt es unterschiedliche Definitionen der Schnittkanten. Häufig verwendet man

 .

Offensichtlich gilt hierbei im Unterschied zu ungerichteten Graphen, dass   sein kann.

Eine andere Möglichkeit, Schnittkanten in gerichteten Graphen zu definieren, ist es, die Kanten in   zunächst unabhängig von ihrer Orientierung aufzunehmen, so dass wiederum   gelten würde. In diesem Fall würde   in die beiden Teilmengen   und   zerfallen. Gilt dann, dass entweder   oder  , so spricht man von einem gerichteten Schnitt, d. h., es zeigen entweder alle gerichteten Kanten in die Menge   hinein oder aus ihr hinaus.

Wichtige Sätze und Aussagen

Bearbeiten

Zusammenhang und minimale Schnitte

Bearbeiten

Würde man alle Kanten eines Schnitts   aus dem Graphen   entfernen, so würde es keinen Weg mehr zwischen   und   geben. War der Graph vor dem Entfernen der Kanten des Schnitts zusammenhängend, ist er es nachher also nicht mehr.

 
Der linke Schnitt ist nicht minimal, da die beiden rechten Schnitte in ihm enthalten sind

In diesem Kontext wird ein Schnitt auch als minimaler Schnitt bezeichnet, wenn nach dem Entfernen der Kanten des Schnitts aus dem Graph genau zwei Zusammenhangskomponenten entstehen. Das ist genau dann der Fall, wenn eine Knotenmenge   so gewählt werden kann, dass der von ihr induzierte Schnitt keine Teilmengen an Kanten enthält, die einen von einer anderen Knotenmenge induzierten Schnitt bilden. Kurz gesagt: Ein Schnitt ist dann minimal, wenn nicht bereits eine Teilmenge des Schnitts einen Schnitt bildet.

Disjunkte Wege und Schnitte

Bearbeiten

Der Mathematiker Karl Menger stellte einen Zusammenhang zwischen knoten- und kantendisjunkten Wegen und Schnitten fest. Dieser Satz von Menger wurde später zum Max-Flow-Min-Cut-Theorem verallgemeinert.

Man betrachtet einen zusammenhängenden Graphen   mit zwei Teilmengen der Knoten   mit   und  . Zwischen zwei Knoten   mit   und   untersucht man die Anzahl der kantendisjunkten Wege sowie die Kardinalität (also Anzahl der Kanten) eines Schnitts  . Da alle kantendisjunkten Wege von   nach   durch den Schnitt müssen (denn das Entfernen der Kanten des Schnitts zerstört ja alle Wege von   nach  ) und, da die Wege kantendisjunkt sein müssen, jedes Mal eine andere Kante des Schnitts benutzt werden muss, gilt offensichtlich, dass die Kardinalität des Schnitts mindestens so groß sein muss wie die Anzahl kantendisjunkter Wege zwischen   und  . Menger zeigte schließlich, dass die maximale Anzahl kantendisjunkter Wege einer minimalen trennenden Kantenmenge genau entspricht.

Diese Erkenntnis gilt sowohl in gerichteten wie auch in ungerichteten Graphen. Sie lässt sich ferner von kantendisjunkten auf knotendisjunkte Wege übertragen und besagt dann, dass die maximale Anzahl knotendisjunkter Wege zwischen zwei Knoten   und   der Kardinalität einer minimalen trennenden Knotenmenge entspricht.

Damit besagt dann der k-Zusammenhang eines Graphen nicht nur, dass man mindestens   Knoten entfernen muss, um den Zusammenhang zu zerstören, sondern auch, dass es zwischen zwei beliebigen Knoten eines Graphen auch immer mindestens   knotendisjunkte Wege geben muss.

Schnitte und Kreise

Bearbeiten

Auch zwischen Schnitten und Kreisen gibt es einige Beziehungen. So muss die Kardinalität der Schnittmenge der Kanten eines Schnitts   und eines Kreises  , also   gerade sein. Man stelle sich eine Kreiskante   vor, für die gilt, dass sie zusätzlich auch auf dem Schnitt liegt, also muss o. B. d. A.   und   sein. Wenn der Kreis nun in   beginnen und dann   nutzen würde, so kann die betrachtete Kante nicht die einzige Schnittkante von Kreis und Schnitt sein, da man nun in der Teilmenge   ist und noch eine ungerade Anzahl von Schnittkanten zwischen Kreis und Schnitt benutzen muss, um wieder in die Teilmenge   zurückzuwechseln, in welcher   liegt. Insgesamt muss es also eine gerade Anzahl an Schnittkanten geben.

In einem zu   dualen Graphen   werden Schnitte zu Kreisen und Kreise zu Schnitten.

Starker Zusammenhang

Bearbeiten

Wenn ein gerichteter Graph   stark zusammenhängend ist, kann man wiederum Knotenmengen   betrachteten. Dann muss für alle möglichen Mengen   gelten, dass der Schnitt   ist. Nach der Definition von gerichteten Schnitten ist das gleichbedeutend mit der Aussage, dass es keinen gerichteten Schnitt geben darf. Denn bei "richtiger" Wahl von   könnte es dann einen gerichteten Schnitt   geben, was nach Definition heißen muss, dass   ist, was aber der vorigen Aussage widersprechen würde.

Siehe auch

Bearbeiten