0 Daumen
52 Aufrufe

Aufgabe:

Ungerichteter Graph mit n≥2 Knoten; jeder Knoten mit jedem anderen durch eine Kante verbunden → vollständiger Graph, daher n*(n-1)/2 Kanten → vollständige Induktion


Problem/Ansatz:

n*(n-1)/2 = K, wobei K die Anzahl der Kanten ist. Bei so ziemlich jedem anderen Induktionsbeispiel könnte ich nun auch die rechte Seite anpassen, wenn ich links statt n -> n+1 einsetze.

Wenn man zum Beispiel nur beweisen müsste, dass es auch bei Erhöhung von n noch immer durch eine bestimmte Zahl teilbar sein sollte, wüsste man mit der rechten Seite etwas anzufangen. In diesem Beispiel kann ich jedoch nur durch Einsetzen in die ursprüngliche Formel herausfinden, ob das Ergebnis stimmt. Dadurch hätte ich aber vor und nach dem "=" schon im ersten Schritt dasselbe stehen, was ja nicht Zweck der Induktion ist.

(n+1)*n /2 = (n+1)*n /2


Wie beweist man Formeln, deren Ergebnis man einzig und allein durch die Formel selbst bestätigen kann?

von

1 Antwort

0 Daumen
 
Beste Antwort

Hallo

 du weisst ja, dass  mit einem neuen Knoten n neue Kanten dazukommen aus K wird also K+n,oder (n-1)*n/2+n+1= (n+1)*n/2

Gruß lul

von 27 k

Stimmt. Dass es dann um genau n Kanten mehr gibt, habe ich übersehen. Danke.

Deine Gleichung stimmt aber nicht, oder? n+1 zum Nenner zu addieren ergibt meiner Meinung nach keinen Sinn.

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Mathelounge! Stell deine Frage sofort und kostenfrei

x
Made by a lovely community
...