taramath: Graph.bipartite

Beschreibung

Die Funktion besitzt folgende Argumente:

E	Kantenmenge als -Matrix

Es wird geprüft, ob der Graph zur Kantenmenge bipartit ist. Ist dies der Fall, werden zwei Indexmengen ausgegeben, welche eine disjunkte Zerlegung der Knoten bilden und damit den bipartiten Graphen repräsentieren:

L	Knotenmenge L
R	Knotenmenge R

Ist der Graph zur Kantenmenge nicht bipartit, wird ein entsprechender String zurückgegeben.

Beispiel

Im folgenden Beispiel werden ein zufälliger Graph und ein Baum dahingehend geprüft, ob diese bipartit sind. Die Ergebnisse werden entsprechend ausgegeben.

<!DOCTYPE html>
<html>
<head>
  <script src="taramath.js"></script>
</head>
<body>
<textarea id="output"></textarea>
<script>

Print.init("output");
Print.set_digits(0);

var G = Graph.random(12);
var B = Graph.bipartite(G.E);
if (typeof(B) == "string") {
  Print.object(B);
} else {
  Print.object(B.L);
  Print.object(B.R);
};

var T = Graph.spanning_tree(G.E);
var C = Graph.bipartite(T.E);
if (typeof(C) == "string") {
  Print.object(C);
} else {
  Print.object(C.L);
  Print.object(C.R);
};

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

Vorschau aktualisieren

Beispiel

Im folgenden Beispiel wird ein Baum als bipartiter Graph dargestellt.

<!DOCTYPE html>
<html>
<head>
  <script src="taramath.js"></script>
</head>
<body>
<div id="plot1" style="display:inline-block;"></div>
<div id="plot2" style="display:inline-block;"></div>
<script>

var G = Graph.random(12);
var T = Graph.spanning_tree(G.E);
var B = Graph.bipartite(T.E);
var P = new Array(G.L.length);
for (var k = 0; k < B.L.length; k++) P[B.L[k]] = [0,k];
for (var k = 0; k < B.R.length; k++) P[B.R[k]] = [5,k];

Graph.plot("plot1", T.E, G.L, "large", 300);
Graph.plot("plot2", T.E, P, "large", 300);

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

Vorschau aktualisieren

Graph.bipartite

zur Berechnung eines bipartiten Graphen