Mathematik: Gruppenwertige Flüsse
Released by matroid on So. 29. August 2004 22:14:12 [Statistics]
Written by Fabi - 3348 x read [Outline] Printable version Printer-friendly version -  Choose language   
Mathematik

\(\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:

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

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.

fed-Code einblenden
fed-Code einblenden

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
\(\endgroup\)
Get link to this article Get link to this article  Printable version Printer-friendly version -  Choose language     Kommentare zeigen Comments  
pdfFür diesen Artikel gibt es keine pdf-Datei


Arbeitsgruppe Alexandria Dieser Artikel ist im Verzeichnis der Arbeitsgruppe Alexandria eingetragen:
: Graphentheorie :: Gruppentheorie :: Interessierte Studenten :: Reine Mathematik :: Mathematik :
Gruppenwertige Flüsse [von Fabi]  
Einführung in diese Interessante Verbindung von Gruppen- und Graphentheorie.
[Die Arbeitsgruppe Alexandria katalogisiert die Artikel auf dem Matheplaneten]

 
 
Aufrufzähler 3348
 
Aufrufstatistik des Artikels
Insgesamt 105 externe Seitenaufrufe zwischen 2012.01 und 2021.03 [Anzeigen]
DomainAnzahlProz
http://google.de8379%79 %
http://google.com1817.1%17.1 %
https://google.com21.9%1.9 %
http://www.holasearch.com11%1 %
https://duckduckgo.com11%1 %

Häufige Aufrufer in früheren Monaten
Insgesamt 67 häufige Aufrufer [Anzeigen]
DatumAufrufer-URL
2013-2016 (37x)http://google.de/url?sa=t&rct=j&q=
201405-11 (12x)http://google.com/url?sa=t&rct=j&q=
201306-07 (11x)http://google.de/url?sa=t&rct=j&q=gruppenwertige flüsse
201511-11 (7x)http://google.de/url?sa=t&source=web&cd=2&rct=j&q=wenn g ein g wertiger fluss...

[Top of page]

"Mathematik: Gruppenwertige Flüsse" | 3 Comments
The authors of the comments are responsible for the content.

Re: Gruppenwertige Flüsse
von: matroid am: Di. 31. August 2004 20:35:33
\(\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\)
 

Re: Gruppenwertige Flüsse
von: Fabi am: Di. 31. August 2004 22:55:50
\(\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:

fed-Code einblenden

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\)
 

Re: Gruppenwertige Flüsse
von: jannna am: Di. 22. November 2005 13:56:15
\(\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\)
 

 
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]