Zaskakujące, że nie mieliśmy jeszcze żadnych wyzwań dotyczących kolorowania grafów!

Biorąc pod uwagę niekierowany wykres, możemy nadać każdemu wierzchołkowi taki kolor, aby żadne dwa sąsiednie wierzchołki nie miały tego samego koloru. Najmniejsza liczba χ z różnych kolorów, niezbędnych do osiągnięcia tego celu zwany jest liczba chromatyczna wykresu.

Na przykład poniżej pokazano prawidłowe kolorowanie przy użyciu minimalnej liczby kolorów:

_{(Znaleziono na Wikipedii)}

Zatem liczba chromatyczna tego wykresu wynosi χ = 3 .

Napisz program lub funkcję, która przy liczbie wierzchołków N <16 (ponumerowanych od 1 do N ) i liście krawędzi określa liczbę chromatyczną wykresu.

Możesz otrzymać dane wejściowe i wygenerować dane wyjściowe w dowolnym dogodnym formacie, o ile dane wejściowe nie zostaną wstępnie przetworzone. Oznacza to, że możesz użyć łańcucha lub tablicy, dodać do łańcucha wygodne separatory lub użyć zagnieżdżonej tablicy, ale cokolwiek zrobisz, spłaszczona struktura powinna zawierać te same liczby, co w poniższych przykładach (w tej samej kolejności).

Nie możesz używać wbudowanych funkcji związanych z teorią grafów (takich jak Mathematica ChromaticNumber).

Możesz założyć, że wykres nie ma pętli (krawędzi łączącej wierzchołek ze sobą), ponieważ spowodowałoby to, że wykres nie byłby kolorowy.

To jest kod golfowy, wygrywa najkrótsza odpowiedź (w bajtach).

Przykłady

Twój program musi rozwiązać wszystkie z nich w rozsądnym czasie. (Musi poprawnie rozwiązać wszystkie dane wejściowe, ale w przypadku większych danych może to potrwać dłużej).

Aby skrócić post, w poniższych przykładach przedstawiam krawędzie na pojedynczej liście oddzielonej przecinkami. Zamiast tego możesz użyć podziałów linii lub oczekiwać danych wejściowych w wygodnym formacie tablicowym, jeśli wolisz.

Trójkąt (χ = 3)

3
1 2, 2 3, 1 3

„Pierścień” złożony z 6 wierzchołków (χ = 2)

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

„Pierścień” z 5 wierzchołków (χ = 3)

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

Przykładowy obrazek powyżej (χ = 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

Uogólnienie powyższego dla 7 wierzchołków (χ = 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

Wykres Petersena (χ = 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

Pełny wykres 5 wierzchołków plus odłączony wierzchołek (χ = 5)

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

Pełny wykres 8 wierzchołków (χ = 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

Trójkątna sieć z 15 wierzchołkami (χ = 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)

Stosowanie:

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

Brutalna siła poprzez zwiększenie liczby chromatycznej (m) i sprawdzenie wszystkich możliwych kolorów. Jedno zabarwienie można opisać jako liczbę w podstawie m. Możliwe kolory to 0, 1, ..., m ^ n-1.

edycja: Pełny wykres 8 wierzchołków trwa dość długo. Ale mój laptop rozwiązuje to w około 10 minut. Inne przypadki testowe zajmują tylko kilka sekund.

edycja 2: Przeczytaj, że przetwarzanie wstępne jest dozwolone, więc pozwalam, aby indeks wierzchołków zaczynał się od 0: skraca t * m // m ** x% m do t // m ** a% m (-2). Rozpuść lambda i umieść m w parametrach funkcji (-11)

Edycja 3: przerób jest nie wolno -> powrót t * M (+ 4), aby uprościć // / (-2).

edycja 4: usuń nawiasy kwadratowe w dowolnym (-2), dzięki xnor.

edycja 5: zamiast brać modulo m dwa razy, po prostu odejmij je, a następnie użyj modulo (-1). Jest to również znaczna poprawa wydajności. Wszystkie testy trwają razem na moim laptopie około 25 sekund.

edycja 6: wywołanie rekurencyjne zamiast while 1: i m + = 1 (-5). Jeszcze raz dziękuję, 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);}

Najbardziej oczywistym sposobem na to, biorąc pod uwagę ograniczenia, jest brutalna siła. Wystarczy przejść przez każdą liczbę chromatyczną ki przypisać każdy kolor do każdego wierzchołka. Jeśli żaden sąsiad nie ma tego samego koloru, masz swój numer. Jeśli nie, idź dalej.

To trwa najdłużej w przypadku testowym dla χ = 8(pełne wykresy są tutaj do bani), ale wciąż trwa mniej niż 15 sekund (ok, około 100s z najnowszą edycją).

Dane wejściowe to liczba wierzchołków ni tablica wierzchołków krawędzi e[]podana w tej samej kolejności, co wartości oddzielone przecinkami PO.

Z podziałami linii:

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);}

Aha, i to zakłada, że ​​wejście jest rodzajem kolorowego wykresu. Jeśli krawędź zapętla się od v1 do v1 lub nie ma wierzchołków, nie będzie mogła być pokolorowana i wyświetli 0. Wciąż będzie działać na wykresach bez krawędzi χ=1itp.

Python 3 - 162

Używa tego samego podejścia brutalnej siły, ale wykorzystuje bibliotekę itertools do, miejmy nadzieję, szybszego generowania kombinacji. Rozwiązuje pełny 8-wykres w <1 min na mojej dość zwyczajnej maszynie.

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

Przykładowe użycie pełnego przypadku 8-graficznego:

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

Haskell, 163 bajty

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)

Użycie byłoby takie:

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

Podstawowe podejście z użyciem siły brutalnej. Sprawdź wszystkie możliwe kombinacje kolorystyczne, jeśli są prawidłowe. Nie ma tu nic więcej do powiedzenia poza tym, że cieszę się z wszelkich wskazówek, jak jeszcze bardziej to skrócić;)