Temukan Nomor Chromatic

13

Anehnya, kami belum memiliki tantangan pada pewarnaan grafik!

Diberikan grafik yang tidak terarah, kita dapat memberikan setiap simpul warna sehingga tidak ada dua simpul yang berdekatan memiliki warna yang sama. Angka terkecil χ dari warna berbeda yang diperlukan untuk mencapai hal ini disebut angka kromatik dari grafik.

Misalnya, berikut ini menunjukkan pewarnaan yang valid menggunakan jumlah warna minimum:

(Ditemukan di Wikipedia)

Jadi angka berwarna grafik ini adalah χ = 3 .

Tulis program atau fungsi yang, diberi sejumlah simpul N <16 (yang diberi nomor dari 1 hingga N ) dan daftar tepi, menentukan angka kromatik grafik.

Anda dapat menerima input dan menghasilkan output dalam format apa pun yang nyaman, selama input tersebut tidak diproses sebelumnya. Artinya, Anda dapat menggunakan string atau array, menambahkan pembatas yang nyaman ke string atau menggunakan array bersarang, tetapi apa pun yang Anda lakukan, struktur yang diratakan harus berisi angka yang sama seperti contoh di bawah ini (dalam urutan yang sama).

Anda tidak boleh menggunakan fungsi terkait teori grafik bawaan (seperti Mathematica ChromaticNumber).

Anda dapat mengasumsikan bahwa grafik tidak memiliki loop (tepi yang menghubungkan simpul dengan dirinya sendiri) karena itu akan membuat grafik menjadi tidak berwarna.

Ini kode golf, jawaban terpendek (dalam byte) menang.

Contohnya

Program Anda setidaknya harus menyelesaikan semua ini dalam jumlah waktu yang wajar. (Ini harus menyelesaikan semua input dengan benar, tetapi mungkin butuh waktu lebih lama untuk input yang lebih besar.)

Untuk mempersingkat posting, dalam contoh berikut ini, saya menyajikan tepi dalam satu daftar yang dipisahkan koma. Anda bisa menggunakan jeda baris atau mengharapkan input dalam beberapa format array yang nyaman, jika Anda mau.

Segitiga (χ = 3)

3
1 2, 2 3, 1 3

"Dering" dari 6 simpul (χ = 2)

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

"Dering" dari 5 simpul (χ = 3)

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

Contoh gambar di atas (χ = 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

Generalisasi di atas untuk 7 simpul (χ = 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

Grafik Petersen (χ = 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

Grafik lengkap 5 simpul, ditambah simpul terputus (χ = 5)

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

Grafik lengkap 8 simpul (χ = 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

Kisi segitiga dengan 15 simpul (χ = 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
Martin Ender
sumber
Bisakah Anda mendefinisikan wajar? 1 menit? 10?
ThreeFx
@ThreeFx ya, 10 menit masuk akal. setengah hari bukan. Saya tidak ingin terlalu ketat pada batas, karena dengan begitu saya perlu menguji semuanya pada mesin yang sama (saya) lagi. tetapi katakanlah jika itu selesai dalam satu jam pada mesin Anda itu baik-baik saja.
Martin Ender

Jawaban:

4

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)

Pemakaian:

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

Brute force dengan menambah bilangan kromatis (m) dan periksa semua kemungkinan pewarnaan. Satu pewarnaan dapat digambarkan sebagai angka dalam basis m. Jadi pewarnaan yang mungkin adalah 0, 1, ..., m ^ n-1.

sunting: Grafik lengkap 8 simpul membutuhkan waktu cukup lama. Tapi laptop saya menyelesaikannya dalam waktu sekitar 10 menit. Kasing uji lainnya hanya butuh beberapa detik.


sunting 2: Baca bahwa preprocessing diperbolehkan, jadi saya membiarkan indeks simpul dimulai dengan 0: lebih pendek t * m // m ** x% m ke t // m ** a% m (-2). Larutkan lambda dan masukkan m ke fungsi params (-11)


edit 3: preprocessing tidak diizinkan -> kembali ke t * m (+4), disederhanakan // ke / (-2).


sunting 4: hapus tanda kurung siku di (-2), terima kasih xnor.


sunting 5: alih-alih mengambil modulo m dua kali, cukup kurangi dan kemudian gunakan modulo (-1). Ini juga merupakan peningkatan kinerja. Semua testcas bersama memakan waktu sekitar 25 detik di laptop saya.


sunting 6: panggilan rekursif alih-alih sementara 1: dan m + = 1 (-5). Terima kasih lagi, xnor.

Jakube
sumber
Metode yang bagus. Golf sederhana: Anda dapat menghapus tanda kurung di dalam all([...])jika Anda membungkus tanda kurung di a,bparens (yang tidak dikenakan biaya karakter di sini karena jarak) sehingga alltidak salah mengira mereka untuk argumen tambahan. Juga, saya menduga Anda dapat menyimpan karakter jika Anda berulang dengan panggilan fungsi ke tertinggi berikutnya mdaripada menggunakan loop sementara.
xnor
Terima kasih, pendekatan rekursif membutuhkan +2 karakter. Pendekatan A untuk m dalam rentang (n +1) juga.
Jakube
Saya dioptimalkan pendekatan rekursif sedikit dengan anydan and/ortrik, dan kemudian menghemat beberapa karakter: 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).
xnor
2

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

Cara yang paling jelas untuk melakukan ini mengingat kendala adalah kekerasan. Hanya melangkah melalui setiap nomor kromatik k, dan menetapkan setiap warna untuk setiap titik. Jika tidak ada tetangga dengan warna yang sama, Anda memiliki nomor Anda. Jika tidak, ikutilah.

Ini membutuhkan waktu paling lama untuk test case untuk χ = 8(grafik lengkap menyedot di sini), tetapi masih di bawah 15 detik (ok, sekitar 100-an dengan suntingan terbaru).

Input adalah jumlah simpul n, dan larik simpul tepi yang e[]diberikan dalam urutan yang sama dengan nilai-nilai yang dipisahkan koma OP.

Dengan jeda baris:

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, dan ini mengasumsikan inputnya adalah semacam grafik yang dapat berwarna. Jika suatu sisi meliuk dari v1 ke v1, atau tidak ada simpul, itu tidak dapat diwarnai dan akan menghasilkan 0. Itu akan tetap bekerja untuk grafik tanpa tepi χ=1, dll.

Geobit
sumber
2

Python 3 - 162

Menggunakan pendekatan brute-force yang sama, tetapi menggunakan perpustakaan itertools untuk menghasilkan kombinasi yang lebih cepat. Memecahkan 8-grafik lengkap dalam <1 mnt pada mesin saya yang cukup biasa.

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

Contoh penggunaan untuk kasing 8-grafik lengkap:

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

Haskell, 163 byte

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)

Penggunaan akan seperti ini:

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

Pendekatan brute force dasar. Periksa semua kombinasi pewarnaan yang mungkin jika valid. Tidak banyak lagi yang bisa dikatakan di sini kecuali bahwa saya senang mendengar tips untuk memperpendek ini lebih jauh;)

ThreeFx
sumber
Saya akan mengatakan bahwa decrementing simpul dan transposing mereka dianggap sebagai "preprocessing". Apa yang ada dalam pikiran saya dengan "format apa pun yang nyaman" adalah Anda tidak dapat memilih dari daftar datar, daftar bersarang, string, string dengan pembatas yang mudah digunakan, dll ... tetapi struktur yang diratakan harus sama seperti yang ditentukan dalam tantangan.
Martin Ender
@ MartinBüttner Baiklah, saya akan mengubahnya
ThreeFx
@ThreeFx all idsama dengan and, any idsama dengan ordan any id$map f listsama dengan adil any f list. juga, Anda dapat melakukan beberapa hal dengan g: Anda dapat mendefinisikan kembali sebagai g a=(and.).zipWith(\x y->a!!x/=a!!y), membuatnya infix, mengubah urutan input untuk mengganti (\x->g x b c)dengan g b catau bahkan membuatnya benar-benar bebas poin dan sebaris itu. beberapa di antaranya tidak bekerja bersama, jadi cobalah semuanya dan pilih yang terbaik :)
bangga haskeller
1
@ MartinBüttner Saya pikir sudah diperbaiki, dengan biaya maaaaany byte. : D
ThreeFx
1
Bagaimana Anda memecahkan contoh ke-7 tanpa jumlah simpul dalam input?
Martin Ender