Direkt zum Inhalt
  1. Startseite
  2. Argumentationen
  3. #332

Herleitung Graph: Maximale / minimale Anzahl der Kanten

Beispiel: Ungerichteter Graph
Aussage #1
Ein ungerichteter Graph (ohne Schlingen) mit \(n\) Knoten hat höchstens \(\frac{n(n-1)}{2}\) Kanten.

Die Aussage #1 wird mithilfe der vollständigen Induktion bewiesen. Sei \(N_n\) die Anzahl der Kanten bei \(n\) Knoten.

Induktionsanfang: Bei zwei Knoten \(n=2\) hat ein Graph höchstens \(N_n = 1 \) Kante. Das wird erfüllt:1\[ N_2 ~=~ \frac{2 \cdot (2-1)}{2} ~=~ 1 \]

Induktionsannahme: Sei nun die Aussage #1 wahr, dann gilt:2\[ N_n ~=~ \frac{n(n-1)}{2} \]

Induktionsschritt: Beim Einfügen des \((n+1)\)-ten Knotens kommen höchstens \(n\) Knoten hinzu. Die zu beweisende Rekursionsformel ist also:3\[ N_{n+1} = N_n + n \]

Betrachte dafür \((n+1)\) Knoten in 2:4\[ N_{n+1} = \frac{(n+1) \, (n+1-1)}{2} ~~~\Leftrightarrow\] 5\[ N_{n+1} = \frac{(n+1)\,n}{2} ~~~\Leftrightarrow \] 6\[ N_{n+1} = \frac{(n-1+2)\,n}{2} ~~~\Leftrightarrow \]7\[ N_{n+1} = \frac{(n-1)\,n}{2} + \frac{2n}{2} ~~~\Leftrightarrow \]8\[ N_{n+1} = \frac{(n-1)\,n}{2} + n \]

Setze nur noch die Induktionsannahme 2 in 8 ein:9\[ N_{n+1} = N_n + n \]

Damit ist der Induktionsschritt 3 erfüllt und die Aussage #1 ist wahr.Aussage #2
Ein zusammenhängender Graph mit \(n\) Knoten hat mindestens \((n-1)\) Kanten.

Induktionsanfang: Ein Graph mit \(n=2\) Knoten muss \(N_2 = 1\) Kante besitzen, damit der Graph zusammenhängend ist. Das ist durch die Aussage #2 erfüllt:10\[ N_{2} = 2-1 = 1 \]

Induktionsannahme: Sei nun die Aussage #2 wahr, dann gilt:11\[ N_n ~=~ (n-1) \]

Induktionsschritt: Wenn zu einem zusammenhängenden Graphen mit \(n\) Knoten ein weiterer Knoten dazu kommt (\(n+1\)), muss der neue Knoten mindestens eine Kante zu einem der \(n\) Knoten bilden, damit der Graph zusammenhängend bleibt. Es muss also die folgende rekursive Bedingung erfüllt sein:12\[ N_{n+1} ~=~ N_n + 1 \]

Betrachte dafür \((n+1)\) Knoten in 11:13\[ N_{n+1} ~=~ (n+1-1) = (n-1) + 1 \]

Setze nur noch die Induktionsannahme 11 in 13 ein:14\[ N_{n+1} ~=~ N_n + 1 \]

Damit ist der Induktionsschritt 12 erfüllt und die Aussage #2 ist wahr.

Details zum Inhalt
  • Copyright: ©2020
  • Lizenz: CC BY 4.0Dieser Inhalt darf mit der Angabe des Copyrights weiterverwendet werden!
  • Dieser Inhalt wurde hinzugefügt von FufaeV am .
  • Dieser Inhalt wurde aktualisiert von FufaeV am .

Feedback geben

Hey! Ich bin Alexander FufaeV, der Physiker und Autor hier. Es ist mir wichtig, dass du stets sehr zufrieden bist, wenn du hierher kommst, um deine Fragen und Probleme zu klären. Da ich aber keine Glaskugel besitze, bin ich auf dein Feedback angewiesen. So kann ich Fehler beseitigen und diesen Inhalt verbessern, damit auch andere Besucher von deinem Feedback profitieren können.

Wie zufrieden bist Du?