Minimale Spannbäume

Sei G=(V,E) ungerichteter einfacher Graph gegeben mit folgenden Eigenschaften:

• $w:E\rightarrow \mathbbm{R}$ eine Gewichtsfunktion,
• $E' \subseteq E$: $w(E')=\sum_{e\in E'}w(e)$,
• T=(V',E') ein Teilgraph von G mit w(T)=w(E'),
• sei o.B.d.A. G zusammenhängend, dann definiere:

Definition: T heißt minimaler Spannbaum (MSB) von G, falls T Spannbaum von G ist und gilt:

$w(T)\leq w(T')$

Beispiel:

Anwendungen:

• Telekom: Telefonvermittlungen
• Leiterplatinen