Schnitte in der Graphentheorie

Ein Schnitt bezeichnet in der Graphentheorie eine Menge von Kanten eines Graphen G=(V,E)G=(V,E), die zwischen zwei Mengen von Knoten bzw. zwischen einer Menge XVX\subset V und der Restmenge V\XV\backslash X liegt.
Eine besondere Bedeutung kommt Schnitten im Zusammenhang mit Netzwerken zu, welche im Artikel Flüsse und Schnitte in Netzwerken erläutert wird. Schnitte können aber auch unabhängig von Netzwerken definiert und untersucht werden.

Definition

Graph-schnitt.png
Knotenmenge W (rot) und Restmenge (schwarz) und die dadurch erzeugten Schnittkanten (blau)
Für einen ungerichteten Graphen G=(V,E)G=(V,E) mit einer Menge XVX\subset V wird der Schnitt E(X,V\X)E(X,V\backslash X) definiert als: E(X,V\X)={(u,v)E:uX,vV\X}E(X,V\backslash X)=\{(u,v)\in E:u\in X,v\in V\backslash X\}. Er umfasst also alle Kanten aus EE für die gilt, dass ein Endknoten in der Teilmenge XX liegt und der andere in der Menge der übrigen Knoten. Diese Kanten liegen also sozusagen "zwischen" den beiden Teilmengen der Knoten.
In einem gerichteten Graphen D=(V,A)D=(V,A) können Schnitte unterschiedlich definiert sein. In der Regel kann folgender Definition verwendet werden: A(X,V\X)={(u,v)A:uX,vV\X}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 A(X,V\X)A(V\X,X)A(X,V\backslash X)\neq A(V\backslash X,X).
Eine andere Möglichkeit ist es, die Kanten in A(X,V\X)A(X,V\backslash X) zunächst unabhängig von ihrer Orientierung aufzunehmen, so dass wiederum A(X,V\X)=A(V\X,X)A(X,V\backslash X)=A(V\backslash X,X) gelten würde. In diesem Fall würde AA in die beiden Teilmengen A+A^+ und AA^- zerfallen. Gilt dann, dass entweder A+=A^+=\emptyset oder A=A^-=\emptyset, so spricht man von einem gerichteten Schnitt, d.h. es zeigen entweder alle gerichteten Kanten in die Menge XX hinein oder aus ihr hinaus.

Wichtige Sätze und Aussagen

Zusammenhang und minimale Schnitte

Würde man alle Kanten eines Schnitts E(X,V\X)E(X,V\backslash X) aus dem Graphen GG entfernen, so würde es keinen Weg mehr zwischen XX und V\XV\backslash X geben und der so entstandene Graph hätte damit mindestens eine Zusammenhangskomponente mehr. War der Graph vor dem Entfernen der Kanten des Schnitts zusammenhängend, ist er es nachher also nicht mehr.
Minimaler_schnitt.png
Der linke Schnitt ist nicht minimal, da die beiden rechten Schnitte in ihm enthalten sind
In diesem Zusammenhang 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 XX 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 eines 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 (siehe Flüsse und Schnitte in Netzwerken).
Man betrachtet einen zusammenhängenden Graphen G=(V,E)G=(V,E) mit zwei Teilmengen der Knoten S,TS,T mit SVS\subset V und T=V\ST=V\backslash S. Zwischen zwei Knoten u,vu,v mit uSu\in S und vTv\in T untersucht man die Anzahl der kantendisjunkten Wege sowie die Kardinalität (also Anzahl der Kanten) eines Schnitts E(S,T)E(S,T). Da alle kantendisjunkten Wege von uu nach vv durch den Schnitt müssen (denn das Entfernen der Kanten des Schnitts zerstört ja alle Wege von uu nach vv) 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 uu und vv. 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 uu und vv einer minimalen trennenden Knotenmenge entspricht.
Damit besagt dann der k-Zusammenhang eines Graphen nicht nur, dass man mindestens kk Knoten entfernen muss, um den Zusammenhang zu zerstören, sondern auch, dass es zwischen zwei beliebigen Knoten eines Graphen auch immer mindestens kk knotendisjunkte Wege geben muss.

Schnitte und Kreise

Auch zwischen Schnitten und Kreisen gibt einige Beziehungen. So muss die Kardinalität der Schnittmenge der Kanten eines Schnitts E(S,T)E(S,T) und eines Kreises CC, also E(S,T)C|E(S,T)\cap C| gerade sein. Man stelle sich eine Kreiskante e=(u,v)Ce=(u,v)\in C vor, für die gilt, dass sie zusätzlich auch auf dem Schnitt liegt, also muss o.B.d.A. uSu\in S und vTv\in T sein. Wenn der Kreis nun in uu beginnen und dann ee nutzen würde, so kann die betrachtete Kante nicht die einzige Schnittkante von Kreis und Schnitt sein, da man nun in der Teilmenge TT ist und noch eine ungerade Anzahl von Schnittkanten zwischen Kreis und Schnitt benutzen muss, um wieder in die Teilmenge SS zurückzuwechseln, in welcher uu liegt. Insgesamt muss es also eine gerade Anzahl an Schnittkanten geben.
In einem zu GG dualen Graphen GG^* werden Schnitte zu Kreisen und Kreise zu Schnitten.

Starker Zusammenhang

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

Eine mathematische Wahrheit ist an sich weder einfach noch kompliziert, sie ist.

Émile Lemoine

Copyright- und Lizenzinformationen: Diese Seite basiert dem Artikel Schnitte (Graphentheorie) aus der frеiеn Enzyklοpädιe Wιkιpеdιa und stеht unter der Dοppellizеnz GNU-Lιzenz für freie Dokumentation und Crеative Commons CC-BY-SA 3.0 Unportеd (Kurzfassung). In der Wιkιpеdιa ist eine Listе dеr Autorеn des Originalartikels verfügbar. Da der Artikel geändert wurde, reicht die Angabe dieser Liste für eine lizenzkonforme Weiternutzung nicht aus!
Anbieterkеnnzeichnung: Mathеpеdιa von Тhοmas Stеιnfеld  • Dοrfplatz 25  •  17237 Blankеnsее  • Tel.: 01734332309 (Vodafone/D2)  •  Email: cο@maτhepedιa.dе