taramath
Knotenfärbung
eines chordalen Graphen
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 1
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). Vorschau aktualisieren