\(\begingroup\)Gruppenwertige Flüsse
Eines der großen Ziele der Gruppentheorie war immer, alle endlichen Gruppen vollständig zu klassifizieren. Zumindest bei den abelschen Gruppen ist dies auch gelungen - zu jeder natürlichen Zahl n kann man angeben, welche und wieviele Isomorphietypen von abelschen Gruppen der Ordnung n existieren, denn jede abelsche Gruppe ist zu einem direkten Produkt zyklischer Gruppen von Primzahlpotenzordnung isomorph.
Hier will ich jetzt aber nicht über die Struktur abelscher Gruppen schreiben, sondern eher im Gegenteil: Ich will ein meiner Meinung nach sehr schönes Stück Mathematik vorstellen, in dem abelsche Gruppen eine Hauptrolle spielen - aber, sobald man etwas tiefer eintaucht, stellt man fest, dass überaschenderweise die konkrete Struktur der Gruppe nichts zur Sache tut, sondern nur die Mächtigkeit der Gruppe wichtig ist.
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:
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:
1. Die Kirchhoff-Regel: Wenn für jede Ecke x die Bezeichnung Z(x) für die zu x führenden orientierten Kanten steht und W(x) für die von x wegführenden, so gilt
sum(f(e),e \el Z(x)) = sum(f(e), e \el W(x))
Links wird also alles aufsummiert, was zu x hinfliesst, und rechts das von x Wegfliessende.
2. f(e) != 0 für alle e
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:
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:
Und noch eines:
Der Beweis erfolgt nun durch Induktion nach der Anzahl Kanten, die keine Schleifen sind:
Behauptung: Zu jedem Graphen gibt es ein Polynom p, so dass die Anzahl der H-Flüsse auf G für jede Gruppe H gleich p(|H|-1) ist.
Beweis:
Sind alle k Kanten eines Graphen G Schleifen, so kann man jeder Kante jeden Wert von H außer der 0 zuordnen, da jede Schleife an der Ecke x einmal aus x heraus - und einmal in x hereinfließt, die Kirchhoff-Regel also automatisch erfüllt ist.
Insgesamt gibt es also abs(H)-1 Möglichkeiten, jede der k Kanten mit einem Flusswert zu versehen, und daher insgesamt (abs(H)-1)^k Flüsse auf G. G hat also tatsächlich ein Flusspolynom, nämlich x^k.
Nun sei die Behauptung richtig für alle Graphen mit höchstens k echten (d.h. Nicht-Schleifen) Kanten, sei G ein Graph mit k+1 echten Kanten und sei H eine beliebige abelsche Gruppe.
Sei e eine echte Kante von G. Der Graph G_1 = G-e (man löscht also e) hat k echte Kanten und daher ein Flusspolynom p_1, der Graph G_2 = G\\e hat ebenfalls höchstens k echte Kanten und daher auch ein Flusspolynom p_2.
Versieht man G_1 nun mit einem H-Fluss, so kann man daraus einen
Beinahe-H-Fluss auf G gewinnen: Man überträgt alle Werte von den Kanten von G_1 auf die entsprechenden Kanten von G und versieht die Kante e mit dem Wert 0 - jeder andere Wert von e würde die Kirchhoff-Regel in x und y verletzen. Es gibt also auf G genausoviele Beinahe-H-Flüsse, die nur auf e 0 sind und die Kirchhoff-Regel erfüllen, wie es H-Flüsse auf G_1 gibt - also p_1(abs(H)-1) Stück.
Auch aus einem H-Fluss von G_2 kann man einen Beinahe-H-Fluss von G konstruieren: Man macht die Kontraktion an der Kante e wieder rückgängig und lässt die Flusswerte, wie sie sind. Dadurch trennt man die kontrahierte Ecke xy wieder in die Ursprungsecken x und y auf.
Jetzt hat man aber wieder die vorher kontrahierte Kante e, die noch mit einem Flusswert versehen werden muss, um einen H-Fluss auf G zu bekommen und zwar am besten so, dass die Kirchhoff-Regel sowohl in x als auch in y eingehalten wird. Ist das möglich?
Nehmen wir mal an, e ist von x nach y orientiert, gehört also zu W(x) und Z(y).
Es muss für die Kirchoff-Regel gelten
sum(f(k),k \el W(x)) = sum(f(k),k \el Z(x))
f(e) = sum(f(k), k \el Z(x))-sum(f(k),k \el W(x)\\e)
Andererseits aber auch:
sum(f(k),k \el W(y)) = sum(f(k),k \el Z(y))
f(e) = sum(f(k), k \el W(y))-sum(f(k),k \el Z(y)\\e)
Man kann f(e) also nur dann sinnvoll wählen, wenn gilt:
sum(f(k), k \el W(y))-sum(f(k),k \el Z(y)\\e) = sum(f(k),k \el Z(x))-sum(f(k),k \el W(y)\\e)
Oder anders:
sum(f(k), k \el W(y))+sum(f(k),k \el W(x)\\e) = sum(f(k),k \el Z(x))+sum(f(k),k \el Z(y)\\e)
Überlegt man sich jetzt aber, dass die Kanten, die nach der Kontraktion zu xy hinführten, genau die zu x oder zu y hinführenden außer der Kante e sind und für die von xy wegführenden Kanten dasselbe gilt, so sieht man, dass die obige Gleichung auch anders ausgedrückt werden kann:
sum(f(k), k \el W(xy)) = sum(f(k), k \el Z(xy))
Und das ist nun nichts anderes als die Kirchhoff-Regel für den H-Fluss auf G_2|!
Man kann also tatsächlich e so mit einem Wert versehen, dass man einen gültigen Fluss auf G bekommt - mit dem kleinen Makel, dass man nicht ausschließen kann, dass f(e) 0 ist.
Aber wir halten einmal folgendes fest:
Die H-Flüsse auf G_2 entsprechen genau den Flüssen auf G, die überall außer vielleicht auf e nicht 0 sind.
Es gibt also genausoviele H-Flüsse auf G, die überall außer vielleicht auf e nicht 0 sind, wie es H-Flüsse auf G_2 gibt - und das sind p_2(abs(H)-1) Stück.
Jetzt müsste man irgendwie diejenigen Flüsse auf G zählen, die überall nicht null sind, außer genau auf e - dann könnte man diese Anzahl von der gerade gefundenen Anzahl abziehen und hat alle gültigen echten H-Flüsse von G. Aber auch die Anzahl der H-Flüsse, die nur genau auf e 0 sind, haben wir schon gezählt: Das waren ja genausoviele wie die H-Flüsse auf G_1, also p_1(abs(H)-1) Stück!
Also hat G p_2(abs(H)-1)-p_1(abs(H)-1) = (p_2-p_1)(abs(H)-1) H-Flüsse für jede Gruppe H, auch G hat also ein Flußpolynom, nämlich p_2-p_1. q.e.d.
Es ist also tatsächlich so: Die Struktur der Gruppe spielt überhaupt keine Rolle!
Den hier vorgestellten Satz finde ich sowohl vom algebraischem als auch vom kombinatorischen Standpunkt aus sehr interessant, aber die Flusstheorie hat natürlich auch noch mehr schöne Sätze und Anwendungen in anderen Gebieten zu bieten: Viele Färbungsprobleme von Graphen in der Ebene lassen sich auch als Flussprobleme darstellen und so leichter lösen, außerdem gibt es dann noch einen Satz, der in Kombination mit dem eben bewiesenen besagt, dass, wenn ein Graph einen
H-Fluss hat, er auch für jede Gruppe, die mindestens so mächtig ist wie H, einen Fluss hat...und vieles mehr.
Auch das Flusspolynom selbst kann man noch erheblich verallgemeinern und so sogar Zusammenhänge zu auf den ersten Blick völlig fremden Gebieten herstellen, dazu schreibe ich aber vielleicht auch mal einen eigenen Artikel.
Vielleicht bis dann,
Fabi
\(\begingroup\)Hi Fabi,
ein Thema wie aus dem Versuchslabor. Man müßte noch einige Übungsaufgaben dazu stellen, mit denen der Leser sich klar machen kann, daß es nicht trivial ist, daß es für einen Graphen einen H-Fluß gibt. Auch bei der Frage nach dem Polynom stellt sich mir die Frage, ob es nicht trivial ist, daß man ein Polynom finden kann, das für ein bestimmtes x einen vorbestimmten Wert y annimmt.
Ich würde ja erstmal H=IZ setzen und herumprobieren, aber das hast Du ja sicher auch getan. Verfügst Du noch über einige Beispiele, mit denen man solchen Einwänden begegnen kann?
Gruß
Matroid \(\endgroup\)
\(\begingroup\)Hi matroid,
Ja, der Einwand mit der Nichttrivialität, dass ein Graph einen H-FLuss hat, ist wohl berechtigt.
Ich wähle mal ein paar Beispiele:
1. Ein Graph hat nur dann einen Z_2-Fluß, wenn alle Eckengerade gerade sind: Der Fluss muss überall 1 sein, und damit sich die Flusswerte dann an jeder Kante entsprechend gegenseitig aufheben, muuss der Grad der Ecke gerade sein.
2. Es ist eine sehr schwierige Frage, zu entscheiden, ob jeder ebene Graph einen Z_4 Fluss hat. Diese Frage ist erstaunlicherweise äquivalent zum Vierfarbensatz, und das der recht widerstandsfähig in Sachen beweisen ist, ist ja bekannt.
3. Der doch noch sehr übersichtliche vollständige Graph K_4 hat keinen Z_3-Flsus, alle anderen vollständigen Graphen jedoch schon, egal, wie groß sie auch sein mögen.
Zur zweiten Frage: Ich finde es nicht so selbstverständlich, dass es dieses Polynom gibt. Schließlich ist die Anzahl der Flüsse für ejdes n vorgegeben, man sucht also ein Polynom p, bei dem p(1),p(2),...p(n),... alle vorgegeben sind. Dass es das gibt, finde ich durchaus nicht so selbstverständlich.
Gruß
Fabi\(\endgroup\)
\(\begingroup\)Hallo
Interessanter Artikel.
Ich habe eine klitzekleine Anmerkung:
Du schreibst von "der Kirchhoff-Regel"
Das ist, wenn mans ganz genau nimmt, nicht richtig, da es nicht "die" Kirchhoff-Regel gibt. Kirchhoff war deutscher Physiker aus dem 19. Jhrd. und hat seine regeln für elektrische Netzwerke aufgestellt.
Das was für die graphentheorie interessant ist, ist die Knotenregel.
Die Maschenregel gibts aber auch noch aber durch diese Formulierung wird irgendwie suggeriert, es gäbe nur eine Kirchhoff-Regel...
Naja eigentlich eher unwichtig. Ich würde das trotzdem Kirchhoffsche Knotenregel nennen..
Grüße
Jana\(\endgroup\)
Home / Seite ohne Frame
Wie unterstütze ich den Matheplaneten mit Geld?
Printer-friendly version
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:
1. Die Kirchhoff-Regel: Wenn für jede Ecke x die Bezeichnung Z(x) für die zu x führenden orientierten Kanten steht und W(x) für die von x wegführenden, so gilt
sum(f(e),e \el Z(x)) = sum(f(e), e \el W(x))
Links wird also alles aufsummiert, was zu x hinfliesst, und rechts das von x Wegfliessende.
2. f(e) != 0 für alle e
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:
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:
Und noch eines:
Get link to this article
Comments
Für diesen Artikel gibt es keine pdf-Datei
Dieser Artikel ist im Verzeichnis der 
