Gruppenwertige Flüsse
Von: Fabi
Datum: So. 29. August 2004 22:14:12
Thema: Mathematik


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:

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:



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
 

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.



 

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
 


Dieser Artikel kommt von Matroids Matheplanet
https://matheplanet.de

Die Url für diesen Artikel ist:
https://matheplanet.de/default3.html?article=660