Gibt es einen minimum-spanning-tree -, die nicht enthalten die min/max-gewichtete Kante?

Wenn wir einen (beliebigen) verbunden ungerichtete graph G, dessen Kanten haben verschiedene GEWICHTE,

  1. hat jeder MST von G enthält die minimal gewichtete Kante?
  2. ist es ein MST von G, die nicht enthalten die maximal gewichtete Kante?

Auch, ich bin eher dankbar, wenn jemand kann einen Tipp geben für die wichtigsten Dinge muss man im Hinterkopf behalten, beim Umgang mit solchen MST Fragen.

Dies ist ein Hausaufgaben problem. Danke.

InformationsquelleAutor Martin08 | 2010-04-11
Schreibe einen Kommentar