 |
 |
 |
 |
 |
 |
Startseite » Forum » Beweis Eulerscher Polyedersatz
Beweis Eulerscher Polyedersatz
Universität / Fachhochschule
Graphentheorie
Tags: Beweis durch vollständig Induktion, euler, Euler`sche Formel, Graph, Graphentheorie, Induktion, Induktionsschritt, planar, Polyeder
 
|
  |
|---|
|
Hallo zusammen, ich versuche gerade einen Beweis aus einer Literatur der eulerschen Polyederformel zu verstehen. Dieser beweist die Formel für planare Graphen: Anzahl der Ecken, Anzahl der Kanten, Anzahl der Gebiete Ich verstehe eigentlich den ganzen Beweis, nur der letzte Schritt, die Anwendung der Induktionsvoraussetzung nicht so ganz ein. Ich zeig euch mal den Beweis. Induktionsanfang: Sei zunächst . Da es immer ein äußeres Gebiet gibt, hat keine Kreise. Deshalb ist dieser Graph ein Baum. Für Bäume gilt: . Deshalb können wir folgern: Induktionsschritt: Sei nun und die Aussage richtig für . Wir wollen nun zeigen, dass sie auch für gilt. Induktionsvoraussetzung: gilt für alle Sei ein zusammenhängender, planarer Graph mit Gebieten. Da aus der Definition gilt, ist kein Baum, sondern es gibt einen Kreis in G. Nun entfernen wir eine Kante k´ dieses Kreises. Da k´ an zwei Gebiete von angrenzt und so zwei Gebiete vereinigt werden, hat der neue Graph G´ ein Gebiet weniger. Deshalb hat G´ nur noch g´=(g+1)-1=g Gebiete. G´ hat also Ecken, Kanten und Gebiete. Nun können wir auf G´ die Induktionsvoraussetzung anwenden: Meine Ideen: Warum ich folgern kann, dass ist, ist mir noch völlig klar. Warum kann ich aber folgern, dass ? Wäre echt toll, wenn irgendjemand eine Idee dazu hätte :-) Für alle, die mir helfen möchten (automatisch von OnlineMathe generiert): "Ich möchte die Lösung in Zusammenarbeit mit anderen erstellen." |
|
 |
|
Hallo, ich verstehe gerade dein Problem nicht: und sind doch dasselbe ... Gruß ermanus |
 |
|
Eben das leuchtet mir irgendwie nicht ein, wahrscheinlich habe ich gerade nur einen Denkfehler, stehe völlig auf dem Schlauch.. die erste Formel Bedeutet ja Ecken Kanten Gebiete und die zweite: Ecken Kanten Gebiete, also habe ich ja sowohl eine Kante, als auch ein Gebiet mehr, dann kann es ja nicht mehr das selbe sein. Wäre es dasselbe müsste es doch sein oder nicht |
|
|
|
Wenn du in einen solchen Graphen eine Kante einfügst, die ein Gebiet in zwei Gebiete teilt, dann hast eine Gebiet und eine Kante mehr (wenn du die Anzahl der Ecken nicht veränderst). In deiner Eulerformel treten die Kanten als (negativ) in die Summe ein und die Gebiete als (positiv). Wenn ich und beide um 1 erhöhe oder vermindere, bleibt die Zahl doch dieselbe. |
 |
|
Ah, jetzt leuchtet es mir ein. Vielen Dank! :-) LG Apollo518 |
1425912
1425864