Sebuah Graceful Grafik adalah jenis Grafik Sederhana . Grafik yang anggun adalah istimewa karena ada cara untuk memberi label semua node mereka dengan bilangan bulat positif sehingga ketika ujung-ujungnya juga dilabeli dengan perbedaan node yang mereka sambungkan, tidak ada dua tepi yang memiliki label yang sama dan setiap label hingga jumlah tepi digunakan.

Contoh Berolahraga

Berikut ini adalah grafik Sederhana yang kami curigai adalah grafik Anggun

Mari kita coba pelabelan berikut:

Catatan kami diizinkan untuk melewati bilangan bulat dalam pelabelan simpul kami. Sekarang kami memberi label setiap sisi dengan perbedaan positif antara node yang terhubung. Untuk meningkatkan visibilitas, saya menandainya dengan warna merah.

Setiap tepi memiliki nomor unik dan tidak ada angka antara 1 dan 7 (jumlah tepi yang kita miliki) ditinggalkan. Jadi grafik kita anggun.

Tugas

Diberikan grafik, melalui metode input yang masuk akal, menghasilkan nilai kebenaran jika anggun dan nilai palsu sebaliknya.

Ini adalah kode-golf sehingga tujuannya adalah untuk meminimalkan jumlah byte Anda.

Uji Kasus

Di sini grafik direpresentasikan sebagai larik tepi:

3 nodes:

[(0,1),(0,2),(1,2)]

True

Labeling:

Node 0 -> 0
Node 1 -> 2
Node 2 -> 3

5 nodes:

[(0,1),(0,4),(1,2),(2,3),(3,4)]

False

5 nodes:

[(0,1),(1,2),(2,3),(3,4)]

True

Labeling:

Node 0 -> 0
Node 1 -> 1
Node 2 -> 3
Node 3 -> 6
Node 4 -> 10

9 nodes

[(0,1),(1,2),(1,7),(1,8),(2,3),(2,6),(3,4),(4,5)]

True

Labeling:

Node 0 -> 0
Node 1 -> 1
Node 2 -> 3
Node 3 -> 6
Node 4 -> 10
Node 5 -> 15
Node 6 -> 11
Node 7 -> 7
Node 8 -> 8

5 nodes

[(0,1),(0,2),(1,2),(1,3),(1,4),(3,4)]

False

Jelly , 12 byte

FSŒ!ị@€ḅ-AċJ

Mengambil array tepi sebagai pasangan simpul yang diindeks 1.

Cobalah online! (Sangat tidak efisien. Jangan repot-repot dengan test case yang sebenarnya.)

Bagaimana itu bekerja

FSŒ!ị@€ḅ-AċJ  Main link. Argument: A (array of pairs)

FS            Flatten and sum, yielding s. This is an upper bound for the labels
              a graceful labeling (if one exists) would require.
  Œ!          Take all permutations of [1, ..., s].
      €       For each permutation P:
    ị@          Replace each integer in A with the element of P at that index.
       ḅ-     Convert all pairs from base -1 to integer, mapping (a,b) to b-a.
         A    Take absolute values.
           J  Yield the indices of A, i.e., [1, ..., len(A)].
          ċ   Count the occurrences of [1, ..., len(A)] in the result to the left.

Mathematica, 121 116 byte

Sunting: Disimpan 5 byte berkat JungHwan Min dan Martin Ender

Cases[Range[1+Tr[n=Range@Length[e=EdgeList@#]]]~Tuples~VertexCount@#,w_/;Sort[Abs[#-#2]&@@w[[List@@#]]&/@e]==n]!={}&

Penjelasan

Fungsi murni yang mengambil Graphobjek Mathematica dengan simpul {1, 2, ..., k}untuk beberapa bilangan bulat negatif k. Dalam kasus terburuk, kita hanya perlu label vertex mulai dari 1hingga 1 + (1 + 2 + ... EdgeCount@#). Karena ini akan menyelamatkan kita beberapa byte nanti, kita akan membiarkannya emenjadi daftar tepi dan nmenjadi daftar {1, 2, ..., EdgeCount@#}, sehingga bobot titik akan diambil Range[1+Tr[n=Range@Length[e=EdgeList@#]]]. Kami membuat daftar semua Tuplespanjang VertexCount@#, kemudian kami memilih Casesyang memberi label anggun dan memeriksa untuk melihat bahwa hasilnya adalah Unequaldaftar kosong {}. Keanggunan dari daftar bobot titik wdiperiksa dengan melakukan Mapping fungsi Abs[#-#2]&@@w[[List@@#]]&pada daftar tepi e, Sortmelihat hasilnya, dan memeriksa apakah hasilnyaEqualuntuk n. Berikut ini rincian fungsi itu:

               List@@#     Replace the Head of the edge with List; i.e., UndirectedEdge[a,b] becomes {a,b}.
            w[[       ]]&  Select the corresponding vertex weights from the list w.
          @@               Replace the Head of that expression (List) with the function
Abs[#-#2]&                   which returns the absolute difference between its first two arguments.
                           This effectively passes the vertex weights into the absolute difference function.