learngraphtheory.org

Interaktives Graphentheorie-Lernen

Guest User

Using app without sign in

Lernpfad

Meistern Sie die Graphentheorie durch interaktive Lektionen

0 von 8 abgeschlossen0%

Graphentheorie-Kurse

Mehrere umfassende PDF-Kurse zu verschiedenen Aspekten der Graphentheorie

PDF-Kurse kommen bald

Mehrere umfassende Graphentheorie-Kurse werden hier verfügbar sein

📚 Kursmaterialien werden vorbereitet und bald hinzugefügt

Verfügbare Lektionen

Minimale Spannbäume

Fortgeschritten
Schlüsselkonzepte:
MSTKruskalPrim+4 more
Bereit zum Lernen?

Klicken Sie, um die vollständige interaktive Lektionserfahrung zu öffnen.

Minimale Spannbäume

Lernen Sie die Algorithmen zur Konstruktion minimaler Spannbäume kennen, einschließlich Kruskal, Prim und Borůvka, sowie ihre Anwendungen in der Netzwerkoptimierung.

35 Minuten
Fortgeschritten
0/8 Abschnitte
MSTKruskalPrimBorůvkaUnion-FindGieriger AlgorithmusNetzwerkdesign

# Minimale Spannbäume

Überblick

Ein minimaler Spannbaum (MST) ist ein fundamentales Konzept in der Graphentheorie und ein mächtiges Werkzeug für Netzwerkoptimierung. Gegeben sei ein zusammenhängender, ungerichteter, gewichteter Graph - ein MST ist ein Teilgraph, der alle Knoten mit der minimalen Gesamtsumme der Kantengewichte verbindet, während er azyklisch bleibt (ein Baum).

Was ist ein Spannbaum?

Definition

Ein Spannbaum eines zusammenhängenden Graphen G ist ein Teilgraph, der:

  • Alle Knoten von G enthält
  • Zusammenhängend ist (es gibt einen Pfad zwischen allen Knotenpaaren)
  • Azyklisch ist (enthält keine Zyklen)
  • Genau n-1 Kanten hat (wobei n die Anzahl der Knoten ist)

Eigenschaften von Spannbäumen

  • Eindeutige Pfade: Zwischen beliebigen zwei Knoten gibt es genau einen Pfad
  • Minimale Konnektivität: Entfernung einer beliebigen Kante trennt den Baum
  • Maximale Azyklizität: Hinzufügung einer beliebigen Kante erzeugt genau einen Zyklus

Was ist ein minimaler Spannbaum?

Definition

Ein minimaler Spannbaum (MST) ist ein Spannbaum mit dem kleinstmöglichen Gesamtgewicht aller Kanten.

Wichtige Eigenschaften

  • Optimalität: Keine andere Knotenmenge kann mit geringerem Gesamtgewicht verbunden werden
  • Eindeutigkeit: Wenn alle Kantengewichte verschieden sind, ist der MST eindeutig
  • Mehrfachheit: Bei gleichen Kantengewichten können mehrere MSTs existieren

Mathematische Formulierung

Gegeben sei ein Graph G = (V, E) mit Gewichtsfunktion w: E → ℝ. Ein MST T ist ein Spannbaum, der minimiert: ∑(e∈T) w(e)

Abschnitt 1 von 8