Dwudzielny wykres przedstawia wykres, którego wierzchołki mogą być podzielone na dwa zestawy rozłącznego, tak że nie ma krawędź łączy dwa wierzchołki w jednym zestawie. Wykres jest dwustronny wtedy i tylko wtedy, gdy jest dwukolorowy.

Wyzwanie

Twoim zadaniem jest, biorąc pod uwagę macierz przylegania niekierowanego prostego wykresu, ustalenie, czy jest to wykres dwustronny. To znaczy, jeśli krawędź łączy wierzchołki i i j, zarówno (i, j), jak i (j, i) wejście macierzy to 1.

Ponieważ wykres jest bezkierunkowy i prosty, jego macierz przylegania jest symetryczna i zawiera tylko 0 i 1.

Specyfika

Powinieneś wziąć macierz N-na-N jako dane wejściowe (w dowolnej formie, np. Lista list, lista ciągów, typ C int**i rozmiar, spłaszczona tablica, surowe dane wejściowe itp.).

Funkcja / program powinien zwrócić / wyprowadzić prawdziwą wartość, jeśli wykres jest dwustronny, a fałsz w przeciwnym razie.

Przypadki testowe

['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

Punktacja

Wbudowane, które obliczają odpowiedź bezpośrednio, są zbanowane.

To jest golf golfowy , więc wygrywa najkrótszy program (w bajtach) do końca tego miesiąca!

Łuska , 17 bajtów

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

Wyświetla dodatnią liczbę całkowitą, jeśli wykres jest dwustronny, 0jeśli nie. Wypróbuj online!

Wyjaśnienie

Jest to podejście z użyciem siły brutalnej: iteruj przez wszystkie podzbiory S wierzchołków i sprawdź, czy wszystkie krawędzie na wykresie znajdują się między S a jego dopełnieniem.

§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.

Wolfram Language (Mathematica) , 26 25 bajtów

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

Wypróbuj online!

Jak to działa

Biorąc pod uwagę macierz przylegania A, znajdujemy stały punkt rozpoczynający się od B = A, a następnie zastępujący B przez A ² B, czasami obcinający wartości większe niż 1 do 1. K- ^ty etap tego procesu jest równoważny Clipdo znalezienia mocy ^{2k + 1} , w którym (i, j) wejścia zlicza liczbę ścieżek długości 2k + 1 z wierzchołka i do j; dlatego punkt stały ma niezerową (i, j) pozycję, jeśli możemy przejść od i do j w nieparzystej liczbie kroków.

W szczególności przekątna punktu stałego ma niezerowe wpisy tylko wtedy, gdy wierzchołek może dotrzeć do siebie w nieparzystej liczbie kroków: jeśli występuje nieparzysty cykl. Tak więc ślad punktu stałego wynosi 0 wtedy i tylko wtedy, gdy wykres jest dwustronny.

Innym 25-bajtowym rozwiązaniem tego formularza jest Tr[#O@n//.x_:>#.#.x]===0&, na wypadek, gdyby ktokolwiek dał pomysł, jak jeszcze bardziej obniżyć liczbę bajtów.

Poprzednie wysiłki

Próbowałem wielu podejść do tej odpowiedzi, zanim zdecydowałem się na tę.

26 bajtów: wykładnicze macierze

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

Opiera się również na nieparzystych mocach macierzy przylegania. Ponieważ x * exp (x ² ), to x + x ³ + X ⁵ /2! + x ^7/4 ! + ..., gdy x jest macierzą A, ma to dodatni wyraz na każdą nieparzystą moc A, więc będzie miał również zerowy ślad, jeśli A ma nieparzysty cykl. To rozwiązanie jest bardzo wolne w przypadku dużych matryc.

29 bajtów: duża nieparzysta moc

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

Dla macierzy n na n A znajduje A ^{2n + 1,} a następnie sprawdza przekątną. Tutaj #~Table~Tr[2#!]generuje 2n kopii macierzy wejściowej n na n i #.##& @@ {a,b,c,d}rozpakowuje do a.a.b.c.d, mnożąc razem 2n + 1 kopii macierzy.

53 bajty: macierz Laplaciana

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

Wykorzystuje niejasny wynik w teorii grafów spektralnych ( Twierdzenie 1.3.10 w tym pliku pdf ).

JavaScript, 78 bajtów

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

Tablica wejściowa tablicy 0/1, wyjście prawda / fałsz.

f = 

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

run = () => o.value=f(i.value.trim().split('\n').map(v=>v.trim().split('').map(t=>+t)))

<textarea id=i oninput="o.value=''" style="width:100%;display:block;">010100
100011
000100
101000
010000
010000
</textarea>
<button type=button onclick="run()">Run</button>
<div>Result = <output id=o></output></div>

Pyth , 25 bajtów

xmyss.D.DRx0dQx1d.nM*FQss

Wypróbuj online!

To zwraca -1falsy i każdą nieujemną liczbę całkowitą dla prawdy.

Jak to działa

xmyss.D.DRx0dQx1d.nM * FQss ~ Pełny program, otrzymuje macierz przylegania od STDIN.

                    * FQ ~ Zmniejsz (złóż) według produktu kartezjańskiego.
                 .nM ~ Spłaszcz każdy.
 m ~ Mapa ze zmienną d.
         RQ ~ Dla każdego elementu na wejściu
       .D ~ Usuń elementy z indeksów ...
          x0d ~ Wszystkie indeksy 0 w d.
     .D ~ I z tej listy usuń elementy w indeksach ...
              x1d ~ Wszystkie indeksy 1 in d.
    s ~ Spłaszcz.
   s ~ Sum. Mógłbym użyć s, gdyby [] się nie pojawił.
  y ~ Double.
x ~ W powyższym odwzorowaniu uzyskaj pierwszy indeks ...
                       ss ~ Całkowita liczba 1 w matrycy wejściowej.

Działa to w zatwierdzeniu d315e19 , obecna wersja PytO TiO.