Jujur, saya tidak percaya ini belum ditanyakan, tapi ini dia

Latar Belakang

Diberikan grafik planar tidak berarah sederhana (grafik dapat digambar di bidang tanpa persimpangan), ini adalah teorema yang telah terbukti bahwa grafiknya 4-warna, sebuah istilah yang akan kita eksplorasi sedikit. Namun, jauh lebih mudah untuk membuat 5-warna grafik, yang akan menjadi fokus kami pada hari ini.

K-pewarnaan grafik yang valid adalah penugasan "warna" ke node grafik dengan properti berikut

1. Jika dua simpul dihubungkan oleh satu sisi, simpul-simpul itu diwarnai dengan warna yang berbeda.
2. Di seluruh grafik, ada maksimal 5 warna.

Mengingat ini, saya akan menyajikan kepada Anda algoritma yang cukup mendasar untuk 5-warna grafik planar sederhana yang tidak diarahkan. Algoritma ini membutuhkan definisi berikut

Tingkat keterjangkauan : Jika simpul 1 dapat dijangkau dari simpul 2, itu berarti ada urutan simpul, masing-masing terhubung ke tepi berikutnya, sehingga simpul pertama adalah simpul 2 dan yang terakhir adalah simpul 1. Perhatikan bahwa sejak grafik tidak terarah simetris, jika simpul 1 dapat dicapai dari simpul 2, simpul 2 dapat dijangkau dari simpul 1.

Subgraf : grafik dari sekumpulan simpul N yang diberikan adalah grafik di mana simpul-simpul subgraf semuanya dalam N, dan suatu tepi dari grafik asli berada dalam subgraf jika dan hanya jika kedua node dihubungkan oleh tepi berada di N.

Biarkan Warna (N) menjadi fungsi untuk mewarnai grafik planar dengan N node dengan 5 warna. Kami mendefinisikan fungsi di bawah ini

1. Temukan node dengan jumlah node yang terhubung paling sedikit. Node ini akan memiliki paling banyak 5 node yang terhubung.
2. Hapus simpul ini dari grafik.
3. Panggil Warna (N-1) pada grafik baru ini untuk mewarnainya.
4. Tambahkan simpul yang dihapus kembali ke grafik.
5. Jika memungkinkan, warnai simpul yang ditambahkan sebagai warna yang tidak dimiliki oleh simpul yang terhubung.
6. Jika tidak memungkinkan, maka semua 5 node tetangga ke node yang ditambahkan memiliki 5 warna berbeda, jadi kita harus mencoba proses berikut.
7. Beri nomor pada simpul-simpul yang mengelilingi simpul yang ditambahkan n1 ... n5
8. Pertimbangkan subgraf semua simpul dalam grafik asli yang diwarnai dengan warna yang sama dengan n1 atau n3.
9. Jika dalam subgraph ini, n3 tidak dapat dijangkau dari n1, dalam himpunan node yang dapat dicapai dari n1 (termasuk n1), ganti semua kemunculan warna n1 dengan n3's dan sebaliknya. Sekarang warnai warna asli simpul yang ditambahkan n1.
10. Jika n3 dapat dijangkau dari n1 dalam grafik baru ini, lakukan proses dari langkah 9 pada node n2 dan n4, daripada n1 dan n3.

Tantangan

Diberikan input dari seorang edgelist (mewakili grafik), beri warna pada grafik, dengan memberi nilai pada setiap node.

Input : Daftar tepi pada grafik (yaitu, [('a','b'),('b','c')...])

Perhatikan bahwa daftar masuk input akan sedemikian rupa sehingga jika (a, b) ada dalam daftar, (b, a) TIDAK ada dalam daftar.

Output : Objek yang berisi pasangan nilai, di mana elemen pertama dari setiap pasangan adalah sebuah node, dan yang kedua warnanya, yaitu, [('a',1),('b',2)...]atau{'a':1,'b':2,...}

Anda dapat menggunakan apa saja untuk mewakili warna, dari angka, karakter, hingga apa pun.

Input dan output cukup fleksibel, asalkan cukup jelas apa input dan outputnya.

Aturan

• Ini adalah kode-golf tantangan
• Anda tidak harus menggunakan algoritma yang saya jelaskan di atas. Itu hanya ada untuk referensi.
• Untuk grafik apa pun, seringkali ada banyak metode pewarnaan yang valid. Selama pewarnaan yang dihasilkan algoritma Anda valid, itu dapat diterima.
• Ingat bahwa grafik harus berwarna 5.

Uji Kasus

Gunakan kode berikut untuk menguji validitas hasil pewarnaan Anda. Karena ada banyak pewarnaan grafik yang valid per grafik, algoritma ini hanya memeriksa validitas pewarnaan. Lihat docstring untuk melihat bagaimana menggunakan kode.

Beberapa kasus uji acak (dan agak konyol) :

Test Case 2: Grafik Layang-layang Krackhardt [(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)]

Output yang valid: {0: 4, 1: 3, 2: 3, 3: 2, 4: 4, 5: 1, 6: 0, 7: 4, 8: 3, 9: 4}

Catatan : Test case ini terlalu kecil untuk menguji perilaku algoritma pewarnaan yang lebih bernuansa, jadi membuat grafik Anda sendiri mungkin merupakan tes yang bagus untuk validitas pekerjaan Anda.

Catatan 2 : Saya akan menambahkan potongan kode lain yang akan membuat grafik solusi pewarnaan Anda segera.

Catatan 3 : Saya tidak mengabaikan algoritma pewarnaan acak yang telah disajikan, yang merupakan hal yang keren tentang PPCG! Namun, jika ada yang bisa bermain golf dengan algoritma yang lebih deterministik, itu akan sangat keren juga.

Python 2 , 96 byte

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)

Cobalah online!

$g$$i$$c$$c$$c$

Masukannya adalah planar, sehingga menemukan pewarnaan 4 selalu memungkinkan.

(Jadi: ini menemukan pewarnaan paling awal secara leksikografis dalam arti tertentu, dan melakukannya dengan sangat tidak efisien.)

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

JavaScript (ES7), 80 76 74 byte

Disimpan 2 byte berkat @Neil

Pendekatan yang sama seperti Lynn . Menyelesaikan dalam 4 warna, diberi nomor dari 0 hingga 3 .

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

Cobalah online!

Brachylog , 38 byte

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

Cobalah online!

Penjelasan

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 byte

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

Cobalah online!

Deterministik! Mungkin gagal pada kasus uji yang lebih rumit, tapi saya terlalu lelah untuk menemukan grafik yang gagal. Lebih banyak kasus uji dan kritik selamat datang!

Bersih , 139 byte

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]

Cobalah online!

Menghasilkan semua warna dan mengembalikan yang valid pertama.

Jelly , 23 byte

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

Cobalah online!

Paksaan. Asumsikan node diberi label oleh bilangan bulat.