Sebuah graf bipartit adalah grafik yang simpul dapat dibagi menjadi dua menguraikan set, sehingga tidak ada tepi menghubungkan dua simpul di set yang sama. Grafik adalah bipartit jika dan hanya jika 2-warna.
Tantangan
Tugas Anda adalah, mengingat matriks adjacency dari grafik sederhana yang tidak terarah, menentukan apakah itu adalah grafik bipartit. Yaitu, jika suatu sisi menghubungkan simpul i dan j, keduanya (i, j) dan (j, i) entri dari matriks adalah 1.
Karena grafik tidak terarah dan sederhana, matriks adjacency-nya simetris dan hanya berisi 0 dan 1.
Spesifik
Anda harus mengambil matriks N-by-N sebagai input (dalam bentuk apa pun, misalnya daftar daftar, daftar string, int**
ukuran dan ukuran C , susunan rata, input mentah, dll.).
Fungsi / program harus mengembalikan / menampilkan nilai kebenaran jika grafiknya bipartit, dan sebaliknya palsu.
Uji Kasus
['00101',
'00010',
'10001',
'01000',
'10100'] : False
['010100',
'100011',
'000100',
'101000',
'010000',
'010000'] : True (divide into {0, 2, 4, 5} and {1, 3})
['00',
'00'] : True
Mencetak gol
Bawaan yang menghitung jawaban secara langsung dilarang.
Ini adalah kode-golf , jadi program terpendek (dalam byte) pada akhir bulan ini menang!
sumber
-1
untuk falsy dan bilangan bulat non-negatif untuk truthy?0
-> Falsy,>0
-> Truthy pada umumnya diizinkan oleh aturan kebenaran / kepalsuan standar.-1
dan≥ 0
tidak umum, itu sebabnya saya bertanya.Jawaban:
Sekam , 17 byte
Mencetak bilangan bulat positif jika grafiknya bipartit,
0
jika tidak. Cobalah online!Penjelasan
Ini adalah pendekatan brute force: iterate melalui semua subset S dari simpul, dan lihat apakah semua tepi dalam grafik berada di antara S dan komplemennya.
sumber
M = [[1,2,3],[4,5,6],[7,8,9]]
danS = [1,0,1]
(M
selalu merupakan matriks biner dalam program, tetapi lebih mudah untuk menjelaskan cara ini). Memfilter setiap barisM
denganS
memberikan[[1,3],[4,6],[7,9]]
: untuk setiap baris, saya menghapus elemen pada indeks yangS
memiliki 0. Lalu saya meniadakanS
elemen-bijaksana untuk mendapatkan[0,1,0]
, dan memfilterM
dengan itu untuk mendapatkan[[4,6]]
: baris pertama dan terakhir memiliki 0 di indeks yang sesuai , jadi mereka dihapus.Bahasa Wolfram (Mathematica) ,
2625 byteCobalah online!
Bagaimana itu bekerja
Diberikan matriks adjacency A, kami menemukan titik tetap dimulai dengan B = A dan kemudian mengganti B dengan A 2 B, kadang-kadang memotong nilai lebih besar dari 1 ke 1. Langkah ke- k dari proses ini setara sampai dengan
Clip
untuk menemukan kekuatan A 2k + 1 , di mana entri (i, j) menghitung jumlah lintasan dengan panjang 2k + 1 dari simpul i ke j; oleh karena itu titik tetap akhirnya memiliki entri bukan nol (i, j) jika kita bisa beralih dari saya ke j dalam jumlah langkah ganjil.Secara khusus, diagonal titik tetap memiliki entri bukan nol hanya ketika sebuah titik dapat mencapai dirinya sendiri dalam sejumlah langkah ganjil: jika ada siklus aneh. Jadi jejak titik tetap adalah 0 jika dan hanya jika grafiknya adalah bipartit.
Solusi 25-byte lain dari formulir ini adalah
Tr[#O@n//.x_:>#.#.x]===0&
, jika ini memberikan ide kepada siapa pun tentang cara menekan jumlah byte lebih rendah.Upaya sebelumnya
Saya sudah mencoba sejumlah pendekatan untuk jawaban ini sebelum memutuskan yang ini.
26 byte: eksponensial matriks
Juga mengandalkan kekuatan ganjil dari matriks kedekatan. Sejak x * exp (x 2 ) adalah x + x 3 + x 5 /2! + x 7/4 ! + ..., ketika x adalah matriks A ini memiliki istilah positif untuk setiap kekuatan ganjil dari A, sehingga juga akan memiliki jejak nol jika A memiliki siklus ganjil. Solusi ini sangat lambat untuk matriks besar.
29 byte: daya ganjil yang besar
Untuk matriks n oleh n, temukan A 2n + 1 dan kemudian lakukan pemeriksaan diagonal. Di sini,
#~Table~Tr[2#!]
menghasilkan 2n salinan dari matriks input n oleh n, dan#.##& @@ {a,b,c,d}
membongkara.a.b.c.d
, mengalikan 2n + 1 salinan dari matriks sebagai hasilnya.53 bytes: Matriks Laplacian
Menggunakan hasil yang tidak jelas dalam teori grafik spektral ( Proposisi 1.3.10 dalam pdf ini ).
sumber
Tr[#.Nest[#.#&,#,Tr[#!]]]<1&
. (Ini adalah jawaban luar biasa yang terus membaik setiap kali saya melihatnya!)BipartiteGraphQ@AdjacencyGraph@#&
MatrixExp
mengembalikan hasil dalam halRoot
objek yang tidak dievaluasi , yang tidak secara otomatis disederhanakan ketika ditambahkan. TheN@
kekuatan iniRoot
s harus dihitung secara numerik sehingga truthiness kemudian dapat dievaluasi.BipartiteGraphQ@*AdjacencyGraph
, tapi masih lebih lama.JavaScript, 78 byte
Input array array 0/1, output benar / salah.
Tampilkan cuplikan kode
sumber
Pyth , 25 byte
Cobalah online!
Ini mengembalikan
-1
untuk falsy, dan bilangan bulat non-negatif untuk kebenaran.Bagaimana itu bekerja
Ini berfungsi di commit d315e19 , versi TiO versi Pyth miliki.
sumber