Hallo, ich denke schon länger über den Beweis einer notwendigen Planaritätsbedingung für Graphen nach, welche besagt, dass mit e=Kantenanzahl, v=Knotenanzahl und f=Gebietsanzahl gelten muss e<=3v-6.
Mir leuchtet einfach ein Schritt im Beweis nicht ein und zwar warum 3f<=2e gelten muss. Inwiefern folgt das aus der Tatsache, dass jede Kante genau 2 Gebiete begrenzt und jedes Gebiet von mindestens 3 Kanten begrenzt wird?
Man kann diese Aussage umformulieren in eine etwas allgemeinere:
Man Konstruiert sich zu dem planaren Graphen G einen neuen
Graphen G', dessen Knotenmenge die Menge der Gebiete von G ist
und dessen Kantenmenge die Menge der Kanten in G ist. Dabei
sind in G' zwei Knoten durch zwei Kanten verbunden gdw. die
entsprechenden Gebiete in G durch diese Kante getrennt werden.
Die Bedingung, dass jedes Gebiet von mindestens 3 Kanten begrenzt
wird, bedeutet dann, dass der Minimalgrad von G' mindestens 3 ist.
Die Abschätzung 3f<=2e ist also bewiesen, wenn man allgemein für
Graphen G zeigen kann, dass
[img]
http://mokrates.de/cgi-bin/texstring?%7CV%7C%5Cle%20%5Cfrac%7B2%7D%7B%5Cdelta(G)%7D%7CE%7C[/img]
wobei [img]
http://mokrates.de/cgi-bin/texstring?%5Cdelta(G)[/img] den Minimalgrad von G bezeichnet.
Wendet man dies nämlich auf G' an, erhält man 3f<=2e.
Und diese allgemeine Aussage sieht mir danach aus, als könnte
man sie in der Vorlesung behandeln. Wenn nicht, sag bescheid,
dann poste ich dafür auch noch nen Beweis.
Die Grafik wird irgendwie nicht von mokrates.de geladen, aber ich denke mal du meinst die Formel, dass die Summe der Knotengrade gleich dem zweifachen der Kantenanzahl entspricht oder?
Danke, aber dort ist doch der gleiche Beweis, den Georg gebracht hat, zu finden. Der gefällt mir auch sehr gut, mich wundert dennoch, dass das z. B. im Steger einfach so drin steht, als ob es vollkommen trivial wäre und nicht erläutert werden müsse.
Das Skript von Diestel sieht aber sehr interessant aus, werd mir das mal genauer angucken. Reichen für die zugehörige Vorlesung am FB Mathe eigentlich die Grundkenntnisse aus M1 bis 4 aus?
Die Grafik wird irgendwie nicht von mokrates.de geladen, aber ich denke mal du meinst die Formel, dass die Summe der Knotengrade gleich dem zweifachen der Kantenanzahl entspricht oder?
Fast, aber das reicht auch. Ich meinte eigentlich
delta(G)*|V|<=2*|E| (wobei delta(G) der Minimalgrad
ist), aber die linke Seite ist ja kleiner oder
gleich der Summe der Knotengrade, insofern genügt das
auch [img]
http://www.fb18.de/gfx/23.gif[/img]
Man kann sich das ganze auch anders klarmachen: Eine
untere Schranke für die Zahl der Kanten erhält man, indem
man die Zahl der Gebiete mal 3 nimmt (es gibt mindestens
3 Kanten pro Gebiet), und dann aber nochmal durch 2 teilt,
weil man im ersten Schritt jede Kante doppelt gezählt hat
(jede Kante taucht bei zwei Gebieten auf).
Danke, aber dort ist doch der gleiche Beweis, den Georg gebracht hat, zu finden. Der gefällt mir auch sehr gut, mich wundert dennoch, dass das z. B. im Steger einfach so drin steht, als ob es vollkommen trivial wäre und nicht erläutert werden müsse.
Den hatte ich mir gar nicht angeguckt, da die Latex-Formel gerade nicht laden wollte [img]
http://www.fb18.de/gfx/25.gif[/img]
Das Skript von Diestel sieht aber sehr interessant aus, werd mir das mal genauer angucken. Reichen für die zugehörige Vorlesung am FB Mathe eigentlich die Grundkenntnisse aus M1 bis 4 aus?
Das Buch ist wirklich sehr zu empfehlen [img]
http://www.fb18.de/gfx/14.gif[/img][img]
http://www.fb18.de/gfx/23.gif[/img]
Mit der zugehörigen VL meinst du sicherlich "Graphentheorie 1". Dafür reichen die Grundkenntnisse aus M1-M4 aus. Da Zufallsgraphen sehr kurz gehalten werden, sogar die Kenntnisse aus M1 (und ein kleines bisschen Algebra (weiß nicht, welches von M2 und M3 Algebra bzw. Analysis ist)).
Und kannst du auch was über die VL Graphentheorie IIa und IIb sagen? Sind die (natürlich mit den Kenntnissen aus GrphTh I) auch was für Informatiker/Wirtschatfsinformatiker?
Die hab ich selbst nicht gehört, daher kann ich dazu nicht allzuviel sagen.
Meines Wissens wird GT2 immer von R. Diestel gehalten, von dem auch das angesprochene Buch ist. Wenn du damit gut zurecht kommst, wirst du mit der VL und den Übungen auch nicht allzu große Schwierigkeiten bekommen.
Ich finde Graphentheorie sehr interessant und gerade als Informatiker wirst du damit viel anfangen können. Und auch wenn wir natürlich gerne über die Wirtschaftsinformatiker (Huhuu *übernkopfwuschel* [img]
http://www.fb18.de/gfx/7.gif[/img]) lästern… die meisten abstrakten Sachen, die für uns geeignet sind, sind das auch für sie.
Kann ich also allen nur empfehlen.
