Eulersche Polyederformel - Induktionsbeweis |
| 10.05.2018, 11:42 | Apollo518 | Auf diesen Beitrag antworten » | ||
| Eulersche Polyederformel - Induktionsbeweis Hallo zusammen, ich versuche gerade einen Beweis aus einer Literatur der eulerschen Polyederformel zu verstehen. Dieser beweist die Formel für planare Graphen: n Anzahl der Ecken, m Anzahl der Kanten, g Anzahl der Gebiete n-m+g=1 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 g=1. Da es immer ein äußeres Gebiet gibt, hat G keine Kreise. Deshalb ist dieser Graph ein Baum. Für Bäume gilt: n=m+1. Deshalb können wir folgern: n-m+g ? [m+1]-m+1=2 Induktionsschritt: Sei nun g?1 und die Aussage richtig für g. Wir wollen nun zeigen, dass sie auch für g+1 gilt. Induktionsvoraussetzung: n-m+g=2 gilt für alle g=1 Sei G ein zusammenhängender, planarer Graph mit g+1 Gebieten. Da aus der Definition g?1 gilt, ist G kein Baum, sondern es gibt einen Kreis in G. Nun entfernen wir eine Kante k´ dieses Kreises. Da k´ an zwei Gebiete von G 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 n Ecken, m-1 Kanten und g Gebiete. Nun können wir auf G´ die Induktionsvoraussetzung anwenden: n-(m-1)+g=2 ? n-m+(g+1)=2 Meine Ideen: Warum ich folgern kann, dass n-(m-1)+g=2 ist, ist mir noch völlig klar. Warum kann ich aber folgern, dass n-(m-1)+g=n-m+(g+1) ? Wäre echt toll, wenn irgendjemand eine Idee dazu hätte :-) |
||||
| 10.05.2018, 17:27 | HAL 9000 | Auf diesen Beitrag antworten » | ||
Das ist eine einfache Umformung! Die Klammer bei auflösen, und dann die 1 dem zuordnen: . |
||||
|
|
Verwandte Themen
| Die Beliebtesten » |
|
| Die Größten » |
|
| Die Neuesten » |
