Kartenfärben

• Sobald eine Kante vorhanden ist, sind zwei Knoten verbunden. Wenn dies verschiedene Knoten sind (also keine Schleife), dann dürfen diese nicht die selbe Farbe haben und es werden mindestens zwei Farben benötigt.
• Wenn der Graph bipartit ist, dann zerfällt er in zwei Teilmenge der Knoten, die untereinander überhaupt nicht verbunden sind. Damit kann jede Teilmenge in einer einzigen Farbe eingefärbt werden.
• Bei einem vollständigen Graphen ist jeder Knoten mit allen anderen verbunden. Daher muss jeder Knoten eine eigene Farbe haben.
• In einer Clique sind alle Knoten untereinander verbunden. Daher muss jeder Knoten der Clique eine eigene Farbe bekommen.

Algorithmus

Beschreibung

Der hier beschriebene Algorithmus findet nicht die perfekte Lösung, d.h. die minimale Anzahl an Farben, aber eine gute Näherungslösung. Er arbeitet dabei nach dem Greedy-Verfahren, er wählt für ein Land die momentan am besten erscheinende Lösung.

Zunächst wird eine Reihenfolge festgelegt, in der die Farben verwendet werden sollen.

z.B. Rot - Blau - Grün - Gelb - Lila - Orange - Braun (es müssen ausreichend viele Farben sein) Dann betrachtet man der Reihe nach alle Knoten. Für jeden Knoten wird dann Folgendes gemacht: Man schaut jeden der Nachbarknoten an und merkt sich, dass seine Farbe schon verwendet wurde. Dann wählt man aus der Liste der Farben die erste noch nicht benutzte Farbe aus und färbt den Knoten in dieser Farbe.

z.B. Der rot umrandete Knoten ist aktuell an der Reihe. Alle Nachbarknoten werden betrachtet und ihre Farben ermittelt.

Die erste noch nicht benutzte Farbe ist grün. Daher wird der Knoten grün gefärbt.

Pseudocode

List<Knoten> knoten = g.getAlleKnoten();
for (Knoten aktuellerKnoten: knoten) {
  boolean[] farbenliste = new boolean[g.getAnzahlKnoten()+1];
  for (int i=0; i < farbenliste.length; i++){
    farbenliste[i]=false;
  }
 
  List<Knoten> nachbarn = g.getNachbarknoten(aktuellerKnoten);
  for (Knoten k : nachbarn){
    farbenliste[k.getFarbe()]=true;
  }
 
  for (int i=1; i<farbenliste.length; i++){
    if (!farbenliste[i]) {
      aktuellerKnoten.setFarbe(i);
      break;
    }
  }
}