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:
Beweis
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.
 
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]