taramath: Knotenfärbung

Beschreibung

Gegeben sei ein ungerichteter und einfacher Graph . Eine Knotenfärbung besteht darin, alle Knoten derart einzufärben, sodass eine minimale Anzahl an Farben verwendet wird und keine zwei benachbarten Knoten durch dieselbe Farbe eingefärbt werden.

Dieses Problem ist allgemein äußerst schwer zu lösen. Falls der Graph jedoch chordal ist, so kann ein perfektes Eliminationschema effizient berechnet werden, welches zu einer Lösung des Knotenfärbungsproblems führt. Da Intervallgraphen stets chordal sind, demonstrieren wir die Knotenfärbung anhand zufälliger Intervallgraphen.

Beispiel

Es wird ein zufälliger Intervallgraph erzeugt und eine zugehörige Knotenfärbung berechnet. Das Ergebnis wird graphisch dargestellt, wobei bis zu fünf unterschiedliche Farben möglich sind (alle Knoten mit einer möglicherweise weiteren Farbe werden in Weiß angezeigt).

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

var n = 8 + Math.floor(Math.random()*32);
var G = Graph.interval(n);
var C = Graph.coloring(G.E);

Svg.init("plot", 20*(n+2), 200);
Svg.clear("#f8f8f8");
Svg.resize(-2, n+1, -2, 8);

// Kanten zeichnen
for (var k = 0; k < G.E.length; k++) {
  Svg.line(G.L[G.E[k][0]][0], G.L[G.E[k][0]][1], G.L[G.E[k][1]][0], G.L[G.E[k][1]][1]);
};

// Knoten zeichnen
for (var k = 0; k < G.L.length; k++) {
  var c = ["#0059c5","#de102d","#359f2f","#fec806","#ff7f2a"];
  var t = (C[k] >= c.length ? "#ffffff" : c[C[k]]);
  Svg.disc(G.L[k][0], G.L[k][1], 0.4, t, "#f8f8f8");
};

Svg.draw();

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

Vorschau aktualisieren

Knotenfärbung

eines chordalen Graphen