1. Welt
  2. Argumentationen
  3. #1442
Alexander Fufaev

Graph: Maximale / minimale Anzahl der Kanten

aus dem Bereich: Argumentationen
Optionen
Ungerichteter Graph Speichern | Info
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.

Weltkarte
Verwalten
Profil
Die Stimme fragt...
Wie erlange ich den Zugang?

Um das Portal von Ak'tazun betreten zu können, musst Du die rote Pille schlucken. Nachdem Du durch das Portal gegangen bist, gelangst Du in die Matrix, wo Du beispielsweise folgendes tun kannst:

  • Inhalte hinzufügen & verwalten
  • Illustrationen ohne Copyrightzeichen herunterladen
  • Einige Inhalte kommentieren
  • Mittels Kommunikator RT2000 chatten
  • Telegram-Gruppe beitreten
Bist Du dabei?
Ja, bin dabei!
Portale in die anderen Welten

Reise zu den sicheren anderen Welten des Internets, um nach dem Wissen zu suchen. Findest Du eine Welt besonders interessant, dann kannst Du in der Universaldenkerwelt ein Portal zu dieser Welt erbauen, um den anderen Besuchern den schnellen Zugang dazu zu gewährleisten.

Portalraum betreten
Kommunikator
ONLINE 8
Gäste online: 8
Denker online: 0
Der Kommunikator RT2000 funktioniert nur innerhalb der Matrix!
Ich will in die Matrix!Mayday! Kontakt aufnehmen.