Minimaler Spannbaum
Minimale Spannbäume beziehen sich auf Graphen.
Sie sind nur für den LK relevant!
Definition
Ein Minimaler Spannbaum besteht aus einer Liste von Kanten des Graphen, die folgenden Bedingungen genügen muss:
- die Kanten der Liste müssen alle Knoten des Graphen miteinander verbinden.
- die Gesamtlänge der Kanten in der Liste muss (im Hinblick auf die Erfüllung der 1. Bedingung) minimal sein.
Beispiel aus der Praxis
Eine Stromfirma will ein Leitungsnetz aufbauen, das alle Städte verbindet. Keine Stadt darf ausgelassen werden. Das Stromnetz soll aber möglichst kurz sein.