Überraschenderweise hatten wir noch keine Herausforderungen beim Färben von Diagrammen!

Bei einem ungerichteten Diagramm können wir jedem Scheitelpunkt eine Farbe zuweisen, sodass keine zwei benachbarten Scheitelpunkte dieselbe Farbe haben. Die kleinste Zahl χ von unterschiedlichen Farben notwendig , dies zu erreichen , wird die genannte chromatische Zahl des Graphen.

Das folgende Beispiel zeigt eine gültige Färbung unter Verwendung der Mindestanzahl von Farben:

_{(Gefunden bei Wikipedia)}

Die chromatische Zahl dieses Graphen ist also χ = 3 .

Schreiben Sie ein Programm oder eine Funktion, die bei einer gegebenen Anzahl von Eckpunkten N <16 (die von 1 bis N nummeriert sind ) und einer Liste von Kanten die chromatische Zahl eines Graphen bestimmt.

Sie können die Eingabe empfangen und die Ausgabe in einem beliebigen geeigneten Format erstellen, solange die Eingabe nicht vorverarbeitet wird. Das heißt, Sie können eine Zeichenfolge oder ein Array verwenden, der Zeichenfolge bequeme Trennzeichen hinzufügen oder ein verschachteltes Array verwenden. Was auch immer Sie tun, die abgeflachte Struktur sollte dieselben Zahlen enthalten wie die folgenden Beispiele (in derselben Reihenfolge).

Sie dürfen keine integrierten graphentheoretischen Funktionen (wie die von Mathematica ChromaticNumber) verwenden.

Sie können davon ausgehen, dass das Diagramm keine Schleife hat (eine Kante, die einen Scheitelpunkt mit sich selbst verbindet), da dies das Diagramm unfarbig machen würde.

Dies ist Codegolf, die kürzeste Antwort (in Bytes) gewinnt.

Beispiele

Ihr Programm muss mindestens alle diese Probleme in angemessener Zeit lösen. (Alle Eingaben müssen korrekt aufgelöst werden, bei größeren Eingaben kann dies jedoch länger dauern.)

Um den Beitrag zu verkürzen, stelle ich in den folgenden Beispielen die Kanten in einer einzelnen durch Kommas getrennten Liste dar. Sie können stattdessen Zeilenumbrüche verwenden oder die Eingabe in einem geeigneten Array-Format erwarten, wenn Sie dies vorziehen.

Dreieck (χ = 3)

3
1 2, 2 3, 1 3

"Ring" von 6 Eckpunkten (χ = 2)

6
1 2, 2 3, 3 4, 4 5, 5 6, 6 1

"Ring" von 5 Eckpunkten (χ = 3)

5
1 2, 2 3, 3 4, 4 5, 5 1

Beispielbild oben (χ = 3)

6
1 2, 2 3, 3 4, 4 5, 5 6, 6 1, 1 3, 2 4, 3 5, 4 6, 5 1, 6 2

Verallgemeinerung des Obigen für 7 Eckpunkte (χ = 4)

7
1 2, 2 3, 3 4, 4 5, 5 6, 6 7, 7 1, 1 3, 2 4, 3 5, 4 6, 5 7, 6 1, 7 2

Petersen-Graph (χ = 3)

10
1 2, 2 3, 3 4, 4 5, 5 1, 1 6, 2 7, 3 8, 4 9, 5 10, 6 8, 7 9, 8 10, 9 6, 10 7

Vollständiger Graph von 5 Scheitelpunkten plus nicht verbundenem Scheitelpunkt () = 5)

6
1 2, 1 3, 1 4, 1 5, 2 3, 2 4, 2 5, 3 4, 3 5, 4 5

Vollständiger Graph von 8 Eckpunkten (χ = 8)

8
1 2, 1 3, 1 4, 1 5, 1 6, 1 7, 1 8, 2 3, 2 4, 2 5, 2 6, 2 7, 2 8, 3 4, 3 5, 3 6, 3 7, 3 8, 4 5, 4 6, 4 7, 4 8, 5 6, 5 7, 5 8, 6 7, 6 8, 7 8

Dreiecksgitter mit 15 Eckpunkten (χ = 3)

15
1 2, 1 3, 2 3, 2 4, 2 5, 3 5, 3 6, 4 5, 5 6, 4 7, 4 8, 5 8, 5 9, 6 9, 6 10, 7 8, 8 9, 9 10, 7 11, 7 12, 8 12, 8 13, 9 13, 9 14, 10 14, 10 15, 11 12, 12 13, 13 14, 14 15

Python 2.7 - 122 109 111 109 108 103

f=lambda n,e,m=1:any(all(t*m//m**a%m!=t*m//m**b%m for(a,b)in e)for t in range(m**n))and m or f(n,e,m+1)

Verwendung:

print f(5, [(1, 2), (2, 3), (3, 4), (4, 5), (5, 1)])

Brute Force durch Erhöhen der chromatischen Zahl (m) und Überprüfung aller möglichen Färbungen. Eine Färbung kann als Zahl in Basis m beschrieben werden. Die möglichen Farbtöne sind also 0, 1, ..., m ^ n-1.

Bearbeiten: Das vollständige Diagramm von 8 Scheitelpunkten dauert ziemlich lange. Aber mein Laptop löst es in ca. 10 Minuten. Die anderen Testfälle dauern nur wenige Sekunden.

edit 2: Lies, dass Vorverarbeitung erlaubt ist, also lasse ich den Index der Eckpunkte mit 0 beginnen: verkürzt t * m // m ** x% m auf t // m ** a% m (-2). Lambda auflösen und m in Funktionsparameter (-11) setzen

edit 3: vorverarbeitung nicht erlaubt -> zurück zu t * m (+4), vereinfachtes // zu / (-2).

edit 4: entferne eckige Klammern in einem (-2), danke xnor.

edit 5: anstatt zweimal modulo m zu nehmen, subtrahiere sie einfach und verwende danach modulo (-1). Dies ist auch eine ziemliche Leistungsverbesserung. Alle Testfälle zusammen dauern auf meinem Laptop ungefähr 25 Sekunden.

edit 6: rekursiver Aufruf anstelle von while 1: und m + = 1 (-5). Nochmals vielen Dank, xnor.

Java - 241 218

int k,j,c;int f(int n,int[]e){for(k=1;k<=n;k++)for(long p=0;p<x(n);p++){for(j=0,c=0;j<e.length;c=p%x(e[j])/x(e[j]-1)==p%x(e[j+1])/x(e[j+1]-1)?1:c,j+=2);if(c<1)return k;}return 0;}int x(int a){return(int)Math.pow(k,a);}

Der naheliegendste Weg, dies angesichts der Zwänge zu tun, ist rohe Gewalt. Gehen Sie einfach jede chromatische Zahl kdurch und weisen Sie jedem Scheitelpunkt jede Farbe zu. Wenn keine Nachbarn die gleiche Farbe haben, haben Sie Ihre Nummer. Wenn nicht, mach weiter.

Dies dauert für den Testfall am längsten χ = 8(vollständige Grafiken saugen hier), aber es ist immer noch unter 15 Sekunden (ok, ungefähr 100s mit der letzten Bearbeitung).

Die Eingabe ist die Anzahl der Eckpunkte nund ein Array von Eckpunkten, e[]die in derselben Reihenfolge wie die durch Kommas getrennten OP-Werte angegeben werden.

Mit Zeilenumbrüchen:

int k,j,c;
int f(int n,int[]e){
    for(k=1;k<=n;k++)
        for(long p=0;p<x(n);p++){
            for(j=0,c=0;
                j<e.length;
                c=p%x(e[j])/x(e[j]-1)==p%x(e[j+1])/x(e[j+1]-1)?1:c,
                j+=2);
            if(c<1)return k;
        }
    return 0;
}
int x(int a){return(int)Math.pow(k,a);}

Oh, und dies setzt voraus, dass es sich bei der Eingabe um eine Art färbbares Diagramm handelt. Wenn eine Kante eine Schleife von v1 nach v1 durchläuft oder keine Scheitelpunkte vorhanden sind, kann sie nicht gefärbt werden und gibt 0 aus. Sie funktioniert weiterhin für Diagramme ohne Kanten χ=1usw.

Python 3 - 162

Verwendet den gleichen Brute-Force-Ansatz, verwendet jedoch die itertools-Bibliothek für eine hoffentlich schnellere Kombinationsgenerierung. Löst den kompletten 8-Graphen in <1 min auf meiner normalen Maschine.

import itertools as I
def c(n,v):
 for i in range(1,n+1):
  for p in I.product(range(i),repeat=n):
   if(0==len([x for x in v if(p[x[0]]==p[x[1]])])):return i

Anwendungsbeispiel für den vollständigen Fall mit 8 Diagrammen:

print(c(8,[x for x in I.combinations(range(8), 2)]))

Haskell, 163 Bytes

p x=f(length x)(transpose x)1
f a[b,c]d|or$map(\x->and$g x(h b)(h c))(sequence$replicate a[1..d])=d|0<1=f a b c(d+1)
g a=zipWith(\x y->a!!x/=a!!y)
h=map(flip(-)1)

Die Verwendung wäre wie folgt:

p [[1, 2],[2, 3],[3, 1]]

Grundlegender Brute-Force-Ansatz. Überprüfen Sie alle möglichen Farbkombinationen auf ihre Gültigkeit. Hier gibt es nicht viel anderes zu sagen, außer dass ich froh bin, irgendwelche Tipps zu hören, um dies noch weiter zu verkürzen;)