Apakah ini bipartit?

13

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 , jadi program terpendek (dalam byte) pada akhir bulan ini menang!

Colera Su
sumber
Terkait , dan sebenarnya dupe garis batas, karena menjadi bipartit sama dengan tidak memiliki siklus aneh, dan sebagian besar jawaban untuk pertanyaan itu bekerja dengan menghitung semua siklus dan memeriksa panjangnya.
Peter Taylor
@PeterTaylor Ya, tapi ada cara sederhana untuk menyelesaikan masalah ini.
Colera Su
@ ColeraSu Alih-alih truey / falsy, dapatkah kita kembali -1untuk falsy dan bilangan bulat non-negatif untuk truthy?
Tn. Xcoder
@MishaLavrov 0-> Falsy, >0-> Truthy pada umumnya diizinkan oleh aturan kebenaran / kepalsuan standar. -1dan ≥ 0tidak umum, itu sebabnya saya bertanya.
Tn. Xcoder
@ Mr.Xcoder Tidak apa-apa.
Colera Su

Jawaban:

4

Sekam , 17 byte

§V¤=ṁΣṠMSȯDfm¬ṀfΠ

Mencetak bilangan bulat positif jika grafiknya bipartit, 0jika 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.

§V¤=ṁΣṠMSȯDfm¬ṀfΠ  Implicit input: binary matrix M.
                Π  Cartesian product; result is X.
                   Elements of X are binary lists representing subsets of vertices.
                   If M contains an all-0 row, the corresponding vertex is never chosen,
                   but it is irrelevant anyway, since it has no neighbors.
                   All-1 rows do not occur, as the graph is simple.
      ṠM           For each list S in X:
              Ṁf   Filter each row of M by S, keeping the bits at the truthy indices of S,
        S  fm¬     then filter the result by the element-wise negation of S,
         ȯD        and concatenate the resulting matrix to itself.
                   Now we have, for each subset S, a matrix containing the edges
                   from S to its complement, twice.
§V                 1-based index of the first matrix
  ¤=               that equals M
    ṁΣ             by the sum of all rows, i.e. total number of 1s.
                   Implicitly print.
Zgarb
sumber
@ Mr.Xcoder Yah, anggaplah M = [[1,2,3],[4,5,6],[7,8,9]]dan S = [1,0,1]( Mselalu merupakan matriks biner dalam program, tetapi lebih mudah untuk menjelaskan cara ini). Memfilter setiap baris Mdengan Smemberikan [[1,3],[4,6],[7,9]]: untuk setiap baris, saya menghapus elemen pada indeks yang Smemiliki 0. Lalu saya meniadakan Selemen-bijaksana untuk mendapatkan [0,1,0], dan memfilter Mdengan itu untuk mendapatkan [[4,6]]: baris pertama dan terakhir memiliki 0 di indeks yang sesuai , jadi mereka dihapus.
Zgarb
17

Bahasa Wolfram (Mathematica) , 26 25 byte

Tr[#//.x_:>#.#.Clip@x]<1&

Cobalah 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 Clipuntuk 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

N@Tr[#.MatrixExp[#.#]]==0&

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

Tr[#.##&@@#~Table~Tr[2#!]]<1&

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}membongkar a.a.b.c.d, mengalikan 2n + 1 salinan dari matriks sebagai hasilnya.

53 bytes: Matriks Laplacian

(e=Eigenvalues)[(d=DiagonalMatrix[Tr/@#])+#]==e[d-#]&

Menggunakan hasil yang tidak jelas dalam teori grafik spektral ( Proposisi 1.3.10 dalam pdf ini ).

Misha Lavrov
sumber
Saya pikir Anda dapat mencukur beberapa byte dari metode Anda yang lebih efisien Tr[#.Nest[#.#&,#,Tr[#!]]]<1&. (Ini adalah jawaban luar biasa yang terus membaik setiap kali saya melihatnya!)
Bukan sebatang pohon
1
Ini memiliki lebih sedikit byte yang semi-built-in (membutuhkan dua fungsi)BipartiteGraphQ@AdjacencyGraph@#&
Kelly Lowder
2
@KellyLowder: untuk matriks besar MatrixExpmengembalikan hasil dalam hal Rootobjek yang tidak dievaluasi , yang tidak secara otomatis disederhanakan ketika ditambahkan. The N@kekuatan ini Roots harus dihitung secara numerik sehingga truthiness kemudian dapat dievaluasi.
Michael Seifert
1
@Natatree Pendekatan Anda memang mengurangi beberapa byte, tetapi biayanya; untuk matriks 18x18, 1000 kali lebih lambat, dan semakin buruk dari sana. Saya pikir jika saya melakukan perubahan itu, saya kehilangan hak untuk memanggil metode efisien "efisien".
Misha Lavrov
1
@KellyLowder Anda bisa mempersingkat itu BipartiteGraphQ@*AdjacencyGraph, tapi masih lebih lama.
Martin Ender
3

JavaScript, 78 byte

m=>!m.some((l,i)=>m.some((_,s)=>(l=m.map(t=>t.some((c,o)=>c&&l[o])))[i]&&s%2))

Input array array 0/1, output benar / salah.

tsh
sumber
2

Pyth , 25 byte

xmyss.D.DRx0dQx1d.nM*FQss

Cobalah online!

Ini mengembalikan -1untuk falsy, dan bilangan bulat non-negatif untuk kebenaran.

Bagaimana itu bekerja

xmyss.D.DRx0dQx1d.nM * FQss ~ Program lengkap, menerima matriks adjacency dari STDIN.

                    * FQ ~ Reduce (fold) dengan produk cartesian.
                 .nM ~ Ratakan masing-masing.
 m ~ Peta dengan variabel d.
         RQ ~ Untuk setiap elemen dalam input,
       .D ~ Hapus elemen pada indeks ...
          x0d ~ Semua indeks 0 dalam d.
     .D ~ Dan dari daftar ini, hapus elemen pada indeks ...
              x1d ~ Semua indeks 1 dalam d.
    s ~ Ratakan.
   s ~ Jumlah. Saya bisa menggunakan s jika [] tidak muncul.
  y ~ Ganda.
x ~ Dalam pemetaan di atas, dapatkan indeks pertama ...
                       ss ~ Jumlah total 1 dalam matriks input.

Ini berfungsi di commit d315e19 , versi TiO versi Pyth miliki.

Tuan Xcoder
sumber