Direkt zum Inhalt
  1. Startort
  2. Argumente
  3. 📖
Level 3
Level 3 setzt die Grundlagen der Vektorrechnung, Differential- und Integralrechnung voraus. Geeignet für Studenten und zum Teil Abiturienten.

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 .