Bearbeiten von: Abschnitt [Änderungshistorie]
  Zeilenumbrüche automatisch mache ich selbst mit HTML    

Ich möchte eine Mail an , nachdem mein Vorschlag bearbeitet ist.
  Nachricht zur Änderung:

Input assistance tools (JavaScript): [Link extern intern] [MathML?] [$$?]
[fed-area] [LaTeX-inline] [LaTeX-display] [Tikz] [hide-area][show-area] [Source code [num.]][?]
[Link zurück zum Artikelabschnitt]

Vorschau:
Flüsse auf Graphen

Stellen wir uns einmal vor, durch ein Netzwerk, z.B. ein Straßennetz oder ein Computernetzwerk, fließt etwas - Wasser, Strom, Daten, Verkehr, ...

Wie könnte man das abstrakt modellieren?
Erstmal wird man das entsprechende Netzwerk mit einem abstrakten Graphen identifizieren: Im Straßennetz werden die Kreuzungen zu Ecken und die Straßen zu Kanten, im Computernetz die Computer zu Ecken und die Vernetzungen zu Kanten etc.

Man wird nun versuchen, jeder Kante einen bestimmten Wert, soviel eben fließt, zuzuordnen - aber wenn z.B. Wasser auf einer Kante fließt, dann hat es zusätzlich noch eine festgelegte Richtung. Man wird also zusätzlich noch eine Richtung angeben, in der der (Daten-,Strom-,Wasser-)Fluss fließen soll.
Desweiteren wird man fordern wollen, dass die meisten Ecken von G der Kirchhoff-Regel gehorchen: Es sollte genausoviel herein- wie herausfließen. Ich werde mich hier sogar auf Flüsse beschränken, bei denen die Kirchhoff-Regel überall gilt.
Außerdem sind hier nur solche Flüsse interessant, bei denen wirklich alle Kanten durchflossen werden - der Fluss darf also nirgendwo null werden.

Jetzt können wir eine Definition versuchen:

Sei G ein Graph mit Eckenmenge V und Kantenmenge E und (H,+) eine abelsche Gruppe, aus der später die Flusswerte stammen sollen.

Zuerst orientieren wir den Graphen, indem wir jeder Kante e mit Endecken x und y entweder die Richtung x -> y oder die Richtung y -> x zuordnen - wie wir das konkret machen, ist für unsere Zwecke egal. In einer Zeichnung des Graphen macht man die Richtung deutlich, indem man Pfeilspitzen in die entsprechende Richtung auf die Kanten malt.

Das sieht dann so aus:

Bild


Die Menge der jetzt orientierten Kanten bezeichnen wir der Einfachheit halber immer noch mit E.

Eine Abbildung f: E -> H heißt nun Fluss (oder, wenn man nochmal herausstellen möchte, dass die Flusswerte aus H stammen, H-Fluss), wenn die folgenden Bedingungen erfüllt sind:

fed-Code einblenden

Diese Definition hängt im Wesentlichem nur vom unorientierten Graphen G ab. Hat G für irgendeine Orientierung einen H-Fluss, so auch für jede andere Orientierung: Dazu muss man nur auf den Kanten, auf denen sich die Orientierung ändert, die ursprünglichen Flusswerte zu ihren Inversen abändern, und schon erfüllt der Fluss wieder die Kirchhoff-Regel an allen Ecken. Es ist nunmal dasselbe, ob 10 Euro von mir zu jemand anderen "fließen" oder ob -10€ von diesem anderen zu mir "fließen" - auch wenn man es außerhalb der Mathematik kaum so ausdrücken würde.

Zum Abschluss der Definiton noch ein Graph mit einem Z4-Fluss:

Bild

Jetzt kann man danach fragen, für welche Gruppen ein vorgegebener Graph einen Fluss hat und für welche nicht. Hier würde man jetzt erwarten, dass es sehr konkret auf die Struktur der Gruppe ankommt, ob ein Graph einen entsprechenden Fluss hat oder nicht. Tatsächlich ist aber das Gegenteil der Fall:

Sind H und H' Gruppen mit |H| = |H'|, so hat ein Graph G genau dann einen H-Fluss, wenn er einen H'-Fluss hat.

Das bedeutet zum Beispiel: Hat G einen Z4-Fluss, so hat G auch einen Z2 x Z2 - Fluss und umgekehrt. Es kommt also tatsächlich nur auf die Mächtigkeit der Gruppe H an, damit G einen H-Fluss hat oder nicht.

Im Beweis zeigt man sogar noch eine stärkere Aussage: Man versucht, die Anzahl der verschiedenen H-Flüsse eines Graphen G zu zählen, und kommt zu dem Resultat, dass diese Anzahl nur von der Mächtigkeit von H abhängt und in |H| polynomiell wächst:

Zu jedem Graphen G gibt es ein Polynom p, so dass G für jede Gruppe H p(|H|-1) H-Flüsse hat. Dieses Polynom nennt man das Flusspolynom von G.

Man rechnet hier mit |H|-1, weil es nur |H|-1 Werte aus H gibt, die als Flusswerte in Frage kommen, da die 0 nicht vorkommen darf.

Aus diesem Satz folgt unsere Behauptung natürlich sofort: Hat G einen H-Fluss, so ist p(|H|-1) nicht 0, und für eine Gruppe H' mit |H'| = |H| ist natürlich auch p(|H'|-1) nicht 0, d.h. G hat auch einen H'-Fluss.

Bevor wir jedoch den Beweis anfangen können, brauchen wir nun noch die Technik der Kantenkontraktion.

Ist e eine Kante in G mit den Endecken x und y, so kann man daraus einen neuen Graphen G/e konstruieren, indem man e, x und y löscht und durch eine neue Ecke xy ersetzt, die mit all den Ecken durch eine Kante verbunden ist, mit denen vorher x oder y verbunden war. Dabei können Mehrfachkanten entstehen: Ist eine Ecke in G mit x und mit y mit jeweils einer Kante verbunden, so ist sie in G/e durch zwei Kanten mit xy verbunden. Und wenn x und y noch durch eine andere Kante als e verbunden sind, dann überlebt auch diese die Kontraktion als Schleife in xy (also als Kante, die xy mit sich selbst verbindet).

Am besten macht man sich das an Beispielen klar:

Bild

Und noch eines:

Bild
 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2021 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]