taralino

.spanning_tree

Die Funktion Graph.spanning_tree(E) erwartet folgende (verpflichtende) Argumente:

Argument	Datentyp	Hinweis
E	Datenfeld	Kantenmenge als (m x 2)-Matrix

Es wird ein minimal spannender Baum des Graphens zur Kantenmenge E bestimmt. Zurückgegeben wird ein Objekt bestehend aus folgenden Daten:

Variable	Datentyp	Hinweis
E	Datenfeld	Kantenmenge des Baumes als Matrix
w	Datenfeld	Gewichte der Kanten des Baumes als Vektor

Zudem können folgende Optionen verwendet werden:

Variable	Datentyp	Hinweis	Default-Wert
weights	Datenfeld	Gewichte der Kanten als m-Vektor	alle Gewichte gleich 1

Unter Verwendung der Option weights kann eine Gewichtung der Kanten spezifiziert werden.

Hinweis: Falls der Graph nicht zusammenhängend ist, wird ein Wald statt einem Baum zurückgegeben.

Beispiel

Es wird ein zufälliger Graph erzeugt. Anschließend wird ein minimal spannender Baum berechnet. Die Ergebnisse werden grafisch dargestellt.

<!DOCTYPE html>
<html>
<head>
  <meta charset="utf-8">
  <meta name="viewport" content="width=device-width, initial-scale=1.0">
  <script src="taralino.js"></script>
</head>
<body>
<script>

var G = Graph.random(16);
Graph.plot(G.E, {width:240, locations:G.L, style:"small"});

var T = Graph.spanning_tree(G.E, {weights:G.w});
Graph.plot(T.E, {width:240, locations:G.L, style:"small"});

</script>
</body>
</html>

Vorschau Download Kopie speichern