Minimaler Spannbaum: Unterschied zwischen den Versionen
Zur Navigation springen
Zur Suche springen
(Die Seite wurde neu angelegt: „Kategorie:Informatik Kategorie:Informatik-Abitur Kategorie:Datenstrukturen(IF) thumb|Original-Landkarte |400px [[…“) |
|||
| (4 dazwischenliegende Versionen desselben Benutzers werden nicht angezeigt) | |||
| Zeile 1: | Zeile 1: | ||
[[Kategorie:Informatik]] | [[Kategorie:Informatik]] | ||
[[Kategorie:Informatik- | [[Kategorie:Informatik-Q1]] | ||
[[Kategorie:Datenstrukturen(IF)]] | [[Kategorie:Datenstrukturen(IF)]] | ||
[[File:Landkarte-original.png|thumb|Original-Landkarte |400px]] | [[File:Landkarte-original.png|thumb|Original-Landkarte |400px]] | ||
[[File:Landkarte-minimaler-spannbaum.png|thumb|Minimaler Spannbaum |400px]] | [[File:Landkarte-minimaler-spannbaum.png|thumb|Minimaler Spannbaum |400px]] | ||
Minimale Spannbäume beziehen sich auf [[Graph|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. | |||
Aktuelle Version vom 11. November 2015, 09:24 Uhr
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.