Ehrlich gesagt kann ich nicht glauben, dass dies nicht schon gefragt wurde, aber hier ist es

Hintergrund

Bei einem einfachen ungerichteten planaren Graphen (der Graph kann in der Ebene ohne Schnittpunkte gezeichnet werden) ist es ein bewährtes Theorem, dass der Graph 4-farbig ist, ein Begriff, den wir in Kürze untersuchen werden. Es ist jedoch weitaus einfacher, ein Diagramm in 5 Farben darzustellen, worauf wir uns heute konzentrieren werden.

Eine gültige k-Färbung eines Graphen ist eine Zuordnung von "Farben" zu den Knoten des Graphen mit den folgenden Eigenschaften

1. Wenn zwei Knoten durch eine Kante verbunden sind, werden die Knoten mit unterschiedlichen Farben gefärbt.
2. In der Grafik gibt es maximal 5 Farben.

In Anbetracht dessen werde ich Ihnen einen ziemlich grundlegenden Algorithmus vorstellen, um jeden einfachen ungerichteten planaren Graphen in 5 Farben darzustellen. Dieser Algorithmus erfordert die folgenden Definitionen

Erreichbarkeit : Wenn Knoten 1 von Knoten 2 aus erreichbar ist, bedeutet dies, dass es eine Folge von Knoten gibt, die jeweils durch eine Kante mit dem nächsten verbunden sind, sodass der erste Knoten Knoten 2 und der letzte Knoten 1 ist sind symmetrisch, wenn Knoten 1 von Knoten 2 erreichbar ist, ist Knoten 2 von Knoten 1 erreichbar.

Untergraph : Ein Untergraph eines Graphen eines gegebenen Satzes von Knoten N ist ein Graph, bei dem die Knoten des Untergraphs alle in N sind, und eine Kante aus dem Originalgraph ist im Untergraph nur dann, wenn beide Knoten durch die Kante verbunden sind sind in N.

Sei Farbe (N) eine Funktion zum Färben planarer Graphen mit N Knoten mit 5 Farben. Wir definieren die Funktion unten

1. Suchen Sie den Knoten mit der geringsten Anzahl verbundener Knoten. An diesen Knoten sind höchstens 5 Knoten angeschlossen.
2. Entfernen Sie diesen Knoten aus dem Diagramm.
3. Rufen Sie in diesem neuen Diagramm die Farbe (N-1) auf, um es einzufärben.
4. Fügen Sie den gelöschten Knoten wieder zum Diagramm hinzu.
5. Wenn möglich, färben Sie den hinzugefügten Knoten mit einer Farbe, die keiner der verbundenen Knoten hat.
6. Wenn dies nicht möglich ist, haben alle 5 Nachbarknoten des hinzugefügten Knotens 5 verschiedene Farben. Daher müssen wir den folgenden Prozess versuchen.
7. Nummerieren Sie die Knoten, die den hinzugefügten Knoten n1 ... n5 umgeben
8. Betrachten Sie den Untergraphen aller Knoten in der Originalgrafik, die dieselbe Farbe wie n1 oder n3 haben.
9. Wenn in diesem Untergraphen n3 von n1 aus nicht erreichbar ist, ersetzen Sie in der Menge der von n1 aus erreichbaren Knoten (einschließlich n1) alle Vorkommen der Farbe von n1 durch n3 und umgekehrt. Färben Sie nun die ursprüngliche Farbe des hinzugefügten Knotens n1.
10. Wenn n3 in diesem neuen Diagramm von n1 aus erreichbar war, führen Sie den Vorgang ab Schritt 9 auf den Knoten n2 und n4 anstelle von n1 und n3 aus.

Herausforderung

Wenn Sie eine Kantenliste (die ein Diagramm darstellt) eingegeben haben, färben Sie das Diagramm, indem Sie jedem Knoten einen Wert zuweisen.

Eingabe : Eine Liste der Kanten in der Grafik (dh [('a','b'),('b','c')...])

Beachten Sie, dass die Eingabe-Kantenliste so ist, dass (b, a) NICHT in der Liste enthalten ist, wenn (a, b) in der Liste enthalten ist.

Ausgabe : Ein Objekt mit Wertepaaren, wobei das erste Element jedes Paares ein Knoten ist und das zweite seine Farbe, dh [('a',1),('b',2)...]oder{'a':1,'b':2,...}

Sie können alles verwenden, um Farben darzustellen, von Zahlen über Zeichen bis hin zu allem anderen.

Der Ein- und Ausgang ist ziemlich flexibel, solange klar ist, was die Ein- und Ausgänge sind.

Regeln

• Dies ist eine Code-Golf- Herausforderung
• Sie müssen den oben beschriebenen Algorithmus nicht verwenden. Es dient lediglich als Referenz.
• Für jedes Diagramm gibt es oft viele gültige Methoden, um sie einzufärben. Solange die Farbe, die Ihr Algorithmus erzeugt hat, gültig ist, ist das akzeptabel.
• Denken Sie daran, dass das Diagramm 5-farbig sein muss.

Testfälle

Verwenden Sie den folgenden Code , um die Gültigkeit Ihrer Färbeergebnisse zu testen. Da es viele gültige Grafikfarben pro Grafik gibt, überprüft dieser Algorithmus einfach die Gültigkeit der Farbe. Informationen zur Verwendung des Codes finden Sie in der Dokumentation.

Einige zufällige (und ziemlich dumme) Testfälle :

Testfall 2: Krackhardt Kite Graph [(0, 1), (0, 2), (0, 3), (0, 5), (1, 3), (1, 4), (1, 6), (2, 3), (2, 5), (3, 4), (3, 5), (3, 6), (4, 6), (5, 6), (5, 7), (6, 7), (7, 8), (8, 9)]

Eine gültige Ausgabe: {0: 4, 1: 3, 2: 3, 3: 2, 4: 4, 5: 1, 6: 0, 7: 4, 8: 3, 9: 4}

Hinweis : Diese Testfälle sind zu klein, um das differenziertere Verhalten des Farbalgorithmus zu testen. Die Erstellung eigener Diagramme ist daher wahrscheinlich ein guter Test für die Gültigkeit Ihrer Arbeit.

Hinweis 2 : Ich werde einen weiteren Code hinzufügen, der Ihre Farblösung in Kürze grafisch darstellt.

Anmerkung 3 : Ich habe die vorgestellten zufälligen Farbalgorithmen nicht übersehen, was an PPCG so cool ist! Wenn jedoch jemand einen deterministischeren Algorithmus spielen könnte, wäre das auch sehr cool.

Python 2 , 96 Bytes

i=0
g=input()
while 1:i+=1;c={k:i/4**k%4for k in sum(g,())};all(c[s]^c[t]for s,t in g)>0<exit(c)

Probieren Sie es online!

$g$$i$$c$$c$$c$ ist eine gültige Färbung.

Die Eingabe ist planar, daher ist es immer möglich, eine 4-Farben-Eingabe zu finden.

(Also: dies findet die lexikographisch früheste Färbung in gewissem Sinne und tut dies sehr ineffizient.)

$k$$\Big\lfloor \frac{i}{4^k} \Big\rfloor \bmod 4$$k$$i$

JavaScript (ES7), 80 76 74 Bytes

2 Bytes dank @Neil gespeichert

Gleicher Ansatz wie Lynn . Löst sich in 4 Farben, nummeriert von 0 bis 3 .

a=>{for(x=0;a.some(a=>a.map(n=>z=c[n]=x>>n*2&3)[0]==z,c={});x++);return c}

Probieren Sie es online!

Brachylog , 38 Bytes

cd{∧4>ℕ}ᶻ.g;?z{tT&h⊇ĊzZhpT∧Zt≠}ᵐ∧.tᵐ≜∧

Probieren Sie es online!

Erläuterung

Example input: [["a","b"],["c","b"]]

cd                                       Concatenate and remove duplicates: ["a","b","c"]
  {∧4>ℕ}ᶻ.                               The output is this list zipped zith integers that
                                           are in [0..4]: [["a",I],["b",J],["c",K]]
         .g;?z                           Zip the output with the input:
                                           [[[["a",I],["b",J],["c",K]],["a","b"]],[["a",I],["b",J],["c",K]],["c","b"]]
              {               }ᵐ∧        Map for each element
               tT                        Call T the couple of nodes denoting an edge
                 &h⊇Ċ                    Take a subset of 2 elements in the head
                     zZ                  Zip and call it Z
                      ZhpT               The nodes in Z are T up to a permutation
                          ∧Zt≠           The integers in Z are all different color
                                 .tᵐ≜∧   Label the integers (i.e. colors) in the output so that
                                           it matches the set constraints

Python 2 , 211 Bytes

def f(g):
 g={k:[(a,b)[a==k]for a,b in g if k in(a,b)]for k in sum(g,())};c={k:0 for k in g}
 for a,b in sorted(g.iteritems(),key=lambda a:len(a[1])):c={k:(c[k],c[k]+1)[c[a]==c[k]and k in b]for k in c}
 return c

Probieren Sie es online!

Deterministisch! Wäre wahrscheinlich bei komplizierteren Testfällen fehlgeschlagen, aber ich bin zu ausgebrannt, um ein Diagramm zu finden, bei dem dies fehlschlägt. Weitere Testfälle und.oder Kritik erwünscht!

Sauber , 139 Bytes

import StdEnv,Data.List
$l#(a,b)=unzip l
#e=nub(a++b)
=hd[zip2 e c\\c<- ?e|all(\(a,b)=c!!a<>c!!b)l]
?[h:t]=[[n:m]\\n<-[0..4],m<- ?t]
?e=[e]

Probieren Sie es online!

Erzeugt alle Färbungen und gibt die erste gültige zurück.

Jelly , 23 Bytes

®iⱮⱮ³¤ịE€S
FQ©L4ṗÇÐḟḢ®ż

Probieren Sie es online!

Rohe Gewalt. Angenommen, die Knoten sind durch ganze Zahlen gekennzeichnet.