Schnitt (Graphentheorie)

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 

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

Zusammenhang und minimale Schnitte 
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.

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. Es kann gezeigt werden, dass das genau dann der Fall ist, 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 
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 
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 
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 

 Graphpartitionierung – Bedeutung von Schnitten in der Parallelen Programmierung

Grundbegriff (Graphentheorie)