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

Knotenmenge ${\displaystyle X}$ (rot) und Restmenge ${\displaystyle V\setminus X}$ (schwarz) eines Schnittes und die kreuzenden Schnittkanten ${\displaystyle E(X,V\setminus X)}$ (blau)

Jede nichtleere Teilmenge ${\displaystyle X\subset V}$ der Knotenmenge eines ungerichteten Graphen ${\displaystyle G=(V,E)}$ definiert einen Schnitt ${\displaystyle (X,V\backslash X)}$ des Graphen.

Davon w​ird eindeutig d​ie Menge d​er Schnittkanten

${\displaystyle E(X,V\backslash X)=\{(u,v)\in E:u\in X,v\in V\backslash X\}}$

induziert. Sie umfasst alle Kanten des Graphen, von denen ein Endknoten in der Teilmenge ${\displaystyle X}$ liegt und der andere in der Menge der übrigen Knoten.

In gerichteten Graphen ${\displaystyle D=(V,A)}$ gibt es unterschiedliche Definitionen der Schnittkanten. Häufig verwendet man

${\displaystyle A(X,V\backslash X)=\{(u,v)\in A:u\in X,v\in V\backslash X\}}$.

Offensichtlich gilt hierbei im Unterschied zu ungerichteten Graphen, dass ${\displaystyle A(X,V\backslash X)\neq A(V\backslash X,X)}$ sein kann.

Eine andere Möglichkeit, Schnittkanten in gerichteten Graphen zu definieren, ist es, die Kanten in ${\displaystyle A(X,V\backslash X)}$ zunächst unabhängig von ihrer Orientierung aufzunehmen, so dass wiederum ${\displaystyle A(X,V\backslash X)=A(V\backslash X,X)}$ gelten würde. In diesem Fall würde ${\displaystyle A}$ in die beiden Teilmengen ${\displaystyle A^{+}}$ und ${\displaystyle A^{-}}$ zerfallen. Gilt dann, dass entweder ${\displaystyle A^{+}=\emptyset }$ oder ${\displaystyle A^{-}=\emptyset }$, so spricht man von einem gerichteten Schnitt, d. h., es zeigen entweder alle gerichteten Kanten in die Menge ${\displaystyle X}$ hinein oder aus ihr hinaus.

Wichtige Sätze und Aussagen

Zusammenhang und minimale Schnitte

Würde man alle Kanten eines Schnitts ${\displaystyle E(X,V\backslash X)}$ aus dem Graphen ${\displaystyle G}$ entfernen, so würde es keinen Weg mehr zwischen ${\displaystyle X}$ und ${\displaystyle V\backslash X}$ 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. Es kann gezeigt werden, dass das genau dann der Fall ist, wenn eine Knotenmenge ${\displaystyle X}$ 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 e​inen Zusammenhang zwischen knoten- u​nd kantendisjunkten Wegen u​nd Schnitten fest. Dieser Satz v​on Menger w​urde später z​um Max-Flow-Min-Cut-Theorem verallgemeinert.

Man betrachtet einen zusammenhängenden Graphen ${\displaystyle G=(V,E)}$ mit zwei Teilmengen der Knoten ${\displaystyle S,T}$ mit ${\displaystyle S\subset V}$ und ${\displaystyle T=V\setminus S}$. Zwischen zwei Knoten ${\displaystyle u,v}$ mit ${\displaystyle u\in S}$ und ${\displaystyle v\in T}$ untersucht man die Anzahl der kantendisjunkten Wege sowie die Kardinalität (also Anzahl der Kanten) eines Schnitts ${\displaystyle E(S,T)}$. Da alle kantendisjunkten Wege von ${\displaystyle u}$ nach ${\displaystyle v}$ durch den Schnitt müssen (denn das Entfernen der Kanten des Schnitts zerstört ja alle Wege von ${\displaystyle u}$ nach ${\displaystyle v}$) 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 ${\displaystyle u}$ und ${\displaystyle v}$. 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 ${\displaystyle u}$ und ${\displaystyle v}$ der Kardinalität einer minimalen trennenden Knotenmenge entspricht.

Damit besagt dann der k-Zusammenhang eines Graphen nicht nur, dass man mindestens ${\displaystyle k}$ Knoten entfernen muss, um den Zusammenhang zu zerstören, sondern auch, dass es zwischen zwei beliebigen Knoten eines Graphen auch immer mindestens ${\displaystyle k}$ 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 ${\displaystyle E(S,T)}$ und eines Kreises ${\displaystyle C}$, also ${\displaystyle |E(S,T)\cap C|}$ gerade sein. Man stelle sich eine Kreiskante ${\displaystyle e=(u,v)\in C}$ vor, für die gilt, dass sie zusätzlich auch auf dem Schnitt liegt, also muss o. B. d. A. ${\displaystyle u\in S}$ und ${\displaystyle v\in T}$ sein. Wenn der Kreis nun in ${\displaystyle u}$ beginnen und dann ${\displaystyle e}$ nutzen würde, so kann die betrachtete Kante nicht die einzige Schnittkante von Kreis und Schnitt sein, da man nun in der Teilmenge ${\displaystyle T}$ ist und noch eine ungerade Anzahl von Schnittkanten zwischen Kreis und Schnitt benutzen muss, um wieder in die Teilmenge ${\displaystyle S}$ zurückzuwechseln, in welcher ${\displaystyle u}$ liegt. Insgesamt muss es also eine gerade Anzahl an Schnittkanten geben.

In einem zu ${\displaystyle G}$ dualen Graphen ${\displaystyle G^{*}}$ werden Schnitte zu Kreisen und Kreise zu Schnitten.

Starker Zusammenhang

Wenn ein gerichteter Graph ${\displaystyle D=(V,A)}$ stark zusammenhängend ist, kann man wiederum Knotenmengen ${\displaystyle S\subset V}$ betrachteten. Dann muss für alle möglichen Mengen ${\displaystyle S}$ gelten, dass der Schnitt ${\displaystyle A^{+}(S,V\backslash S)\neq \emptyset }$ 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 ${\displaystyle S}$ könnte es dann einen gerichteten Schnitt ${\displaystyle A^{-}(S,V\backslash S)}$ geben, was nach Definition heißen muss, dass ${\displaystyle A^{+}(S,V\backslash S)=\emptyset }$ ist, was aber der vorigen Aussage widersprechen würde.

Siehe auch

• Graphpartitionierung – Bedeutung von Schnitten in der Parallelen Programmierung