Schnitt (Graphentheorie) - LinkFang.de





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 Teilmenge [math]X\subset V[/math] der Knotenmenge eines ungerichteten Graphen [math]G=(V,E)[/math] definiert einen Schnitt [math](X,V\backslash X)[/math] des Graphen.

Davon wird eindeutig die Menge der Schnittkanten

[math]E(X,V\backslash X)=\{(u,v)\in E:u\in X,v\in V\backslash X\}[/math]

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

In gerichteten Graphen [math]D=(V,A)[/math] gibt es unterschiedliche Definitionen der Schnittkanten. Häufig verwendet man

[math]A(X,V\backslash X)=\{(u,v)\in A:u\in X,v\in V\backslash X\}[/math].

Offensichtlich gilt hierbei im Unterschied zu ungerichteten Graphen, dass [math]A(X,V\backslash X)\neq A(V\backslash X,X)[/math] sein kann.

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

Wichtige Sätze und Aussagen

Zusammenhang und minimale Schnitte

Würde man alle Kanten eines Schnitts [math]E(X,V\backslash X)[/math] aus dem Graphen [math]G[/math] entfernen, so würde es keinen Weg mehr zwischen [math]X[/math] und [math]V\backslash X[/math] 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 [math]X[/math] 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 [math]G=(V,E)[/math] mit zwei Teilmengen der Knoten [math]S,T[/math] mit [math]S\subset V[/math] und [math]T=V\setminus S[/math]. Zwischen zwei Knoten [math]u,v[/math] mit [math]u\in S[/math] und [math]v\in T[/math] untersucht man die Anzahl der kantendisjunkten Wege sowie die Kardinalität (also Anzahl der Kanten) eines Schnitts [math]E(S,T)[/math]. Da alle kantendisjunkten Wege von [math]u[/math] nach [math]v[/math] durch den Schnitt müssen (denn das Entfernen der Kanten des Schnitts zerstört ja alle Wege von [math]u[/math] nach [math]v[/math]) 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 [math]u[/math] und [math]v[/math]. 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 [math]u[/math] und [math]v[/math] der Kardinalität einer minimalen trennenden Knotenmenge entspricht.

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

In einem zu [math]G[/math] dualen Graphen [math]G^*[/math] werden Schnitte zu Kreisen und Kreise zu Schnitten.

Starker Zusammenhang

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

Siehe auch


Kategorien: Grundbegriff (Graphentheorie)

Quelle: Wikipedia - http://de.wikipedia.org/wiki/Schnitt (Graphentheorie) (Vollständige Liste der Autoren des Textes [Versionsgeschichte])    Lizenz: CC-by-sa-3.0

Änderungen: Alle Bilder mit den meisten Bildunterschriften wurden entfernt. Ebenso alle zu nicht-existierenden Artikeln/Kategorien gehenden internen Wikipedia-Links (Bsp. Portal-Links, Redlinks, Bearbeiten-Links). Entfernung von Navigationsframes, Geo & Normdaten, Mediadateien, gesprochene Versionen, z.T. ID&Class-Namen, Style von Div-Containern, Metadaten, Vorlagen, wie lesenwerte Artikel. Ansonsten sind keine Inhaltsänderungen vorgenommen worden. Weiterhin kann es durch die maschinelle Bearbeitung des Inhalts zu Fehlern gerade in der Darstellung kommen. Darum würden wir jeden Besucher unserer Seite darum bitten uns diese Fehler über den Support mittels einer Nachricht mit Link zu melden. Vielen Dank!

Stand der Informationen: August 201& - Wichtiger Hinweis: Da die Inhalte maschinell von Wikipedia übernommen wurden, ist eine manuelle Überprüfung nicht möglich. Somit garantiert LinkFang.de nicht die Richtigkeit und Aktualität der übernommenen Inhalte. Sollten die Informationen mittlerweile fehlerhaft sein, bitten wir Sie darum uns per Support oder E-Mail zu kontaktieren. Wir werden uns dann innerhalb von spätestens 10 Tagen um Ihr Anliegen kümmern. Auch ohne Anliegen erfolgt mindestens alle drei Monate ein Update der gesamten Inhalte.