Tugas Anda adalah menentukan apakah grafik planar.

Grafik planar jika dapat tertanam di dalam pesawat, atau dengan kata lain jika dapat digambar tanpa melewati tepi.

Input: Anda akan diberikan grafik tanpa arah dalam pilihan Anda dari format berikut:

• Daftar tepi, mis [(0, 1), (0, 2), (0, 3)]

• Peta adjuster, misalnya {0: [1, 2, 3], 1:[0], 2:[0], 3:[0]}

• Matriks yang berdekatan, misalnya [[0, 1, 1, 1], [1, 0, 0, 0], [1, 0, 0, 0], [1, 0, 0, 0]]

Nama simpul bisa berupa angka, string atau sejenisnya, tetapi format yang Anda pilih harus dapat mendukung grafik yang berubah-ubah. Tidak ada memasukkan kode dalam nama node. Tidak akan ada loop sendiri.

Pilihan input standar, termasuk STDIN, argumen baris perintah, dan argumen fungsi.

Output: Anda harus mengembalikan output spesifik untuk semua grafik planar, dan output spesifik yang berbeda untuk semua grafik nonplanar.

Pilihan standar output, termasuk STDOUT, nilai pengembalian fungsi.

Contoh:

Planar:

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

Nonplanar:

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

Fungsi apa pun yang secara eksplisit melakukan pengujian planaritas atau sebaliknya secara khusus mereferensikan pernikahan planar dilarang.

Ini kode golf. Semoga kode terpendek menang.

Mathematica, 201 byte

f@g_:=EdgeCount@g<9||!(h=g~IsomorphicGraphQ~CompleteGraph@#&)@5&&!h@{3,3}&&And@@(f@EdgeDelete[g,#]&&f@EdgeContract[g,#]&/@EdgeList@g);And@@(f@Subgraph[g,#]&/@ConnectedComponents[g=Graph[#<->#2&@@@#]])&

Ini mengevaluasi ke fungsi yang tidak disebutkan namanya, yang mengambil daftar tepi seperti

{{0, 3}, {0, 4}, {0, 5}, {1, 3}, {1, 4}, {1, 5}, {2, 3}, {2, 4}, {2, 5}}

Ini adalah pendekatan rekursif yang sangat tidak efisien berdasarkan pada teorema Wagner :

Sebuah grafik yang terbatas adalah planar jika dan hanya jika tidak memiliki K ₅ atau K _3,3 sebagai umur.

Di sini, K ₅ adalah grafik lengkap dengan 5 simpul, dan K _3,3 adalah grafik bipartit lengkap dengan 3 simpul di setiap kelompok. Grafik A adalah minor dari grafik B jika dapat diperoleh dari B dengan urutan penghapusan tepi dan kontraksi tepi.

Jadi kode ini hanya memeriksa apakah grafik isomorfik untuk K ₅ atau K _3,3 dan jika tidak maka secara rekursif akan memanggil dirinya sendiri sekali untuk setiap kemungkinan penghapusan atau kontraksi tepi.

Tangkapannya adalah bahwa menghapus atau mengontrak tepi dalam satu komponen dari grafik yang tidak terhubung tidak akan pernah menghilangkan semua simpul di sana, jadi kita tidak akan pernah menemukan isomorfisma yang diinginkan. Karenanya, kami menerapkan pencarian ini untuk setiap komponen terhubung dari grafik input secara terpisah.

Ini bekerja sangat cepat untuk input yang diberikan, tetapi jika Anda menambahkan beberapa tepi lagi itu akan cepat memakan waktu yang sangat lama (dan mengambil banyak memori juga).

Ini adalah versi indentasi f(fungsi yang tidak disebutkan namanya setelah itu hanya menghasilkan objek grafik dari input:

f@g_ := 
  EdgeCount@g < 9 || 
  ! (h = g~IsomorphicGraphQ~CompleteGraph@# &)@5 && 
  ! h@{3, 3} &&
  And @@ (f@EdgeDelete[g, #] && f@EdgeContract[g, #] & /@ EdgeList@g)

Dan ini adalah fungsi yang tidak disebutkan namanya yang mengubah input ke grafik dan panggilan funtuk setiap komponen yang terhubung:

And @@ (
  f @ Subgraph[g, #] & /@ ConnectedComponents[
    g=Graph[# <-> #2 & @@@ #]
  ]
)&

Saya dapat menyimpan beberapa byte dengan mengubah kondisi termination dari EdgeCount@g<9menjadi g==Graph@{}, tetapi itu akan meledakkan runtime secara signifikan. Kasing uji kedua membutuhkan waktu 30 detik, dan yang terakhir belum selesai.