Eulersche Polyederformel - Induktionsbeweis

Neue Frage »

Apollo518 Auf diesen Beitrag antworten »
Eulersche Polyederformel - Induktionsbeweis
Meine Frage:
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 :-)
HAL 9000 Auf diesen Beitrag antworten »

Zitat:
Original von Apollo518
Warum kann ich aber folgern, dass n-(m-1)+g=n-m+(g+1) ?

geschockt
Das ist eine einfache Umformung! Die Klammer bei auflösen, und dann die 1 dem zuordnen:

.
 
 
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »