taralino

.bipartite

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

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

Es wird geprüft, ob der Graph zur Kantenmenge E bipartit ist. Ist dies der Fall, wird ein Objekt mit den beiden Indexmengen zurückgegeben, welche eine (disjunkte) Zerlegung der Knoten bilden und damit:

Variable	Datentyp	Hinweis
L	Datenfeld	Liste der Knoten-Indize aus Knotenmenge L
R	Datenfeld	Liste der Knoten-Indize aus Knotenmenge R

Hinweis: Falls der Graph zur Kantenmenge E nicht bipartit ist, wird eine entsprechende Zeichenkette zurückgegeben.

Beispiel

Es wird eine bipartite Zerlegung der Knoten eines minimal spannenden Baumes bestimmt und ausgegeben.

<!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);
var T = Graph.spanning_tree(G.E);
var B = Graph.bipartite(T.E);

Console.digits(0);
Console.print(B.L);
Console.print(B.R);

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

Vorschau Download Kopie speichern

Beispiel

Es wird eine bipartite Zerlegung der Knoten eines minimal spannenden Baumes bestimmt und farblich 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 n = 64;
var G = Graph.random(n);
var T = Graph.spanning_tree(G.E);
var B = Graph.bipartite(T.E);

var C = [];
for (var i = 0; i < n; i++) C.push(0);
for (var k = 0; k < B.L.length; k++) C[B.L[k]] = 1;

Graph.plot(T.E, {locations:G.L, style:"small", coloring:C});

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

Vorschau Download Kopie speichern