Minimaler Spannbaum

Aus SibiWiki
Version vom 11. November 2015, 09:24 Uhr von Akaibel (Diskussion | Beiträge) (→‎Implementierung)
(Unterschied) ← Nächstältere Version | Aktuelle Version (Unterschied) | Nächstjüngere Version → (Unterschied)
Zur Navigation springen Zur Suche springen


Original-Landkarte
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:

  1. die Kanten der Liste müssen alle Knoten des Graphen miteinander verbinden.
  2. 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.