Un gráfico bipartito es un gráfico cuyos vértices se pueden dividir en dos conjuntos disjuntos, de modo que ningún borde conecte dos vértices en el mismo conjunto. Un gráfico es bipartito si y solo si tiene 2 colores.

Desafío

Su tarea es, dada la matriz de adyacencia de un gráfico simple no dirigido, determinar si es un gráfico bipartito. Es decir, si un borde conecta los vértices i y j, tanto (i, j) como (j, i) la entrada de la matriz son 1.

Como el gráfico no está dirigido y es simple, su matriz de adyacencia es simétrica y contiene solo 0 y 1.

Detalles específicos

Debe tomar una matriz N-por-N como entrada (en cualquier forma, por ejemplo, lista de listas, lista de cadenas, tipo C int**y tamaño, matriz aplanada, entrada sin formato, etc.).

La función / programa debería devolver / generar un valor verdadero si el gráfico es bipartito, y falso de lo contrario.

Casos de prueba

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

Puntuación

Las construcciones que calculan la respuesta directamente están prohibidas.

Este es el código de golf , por lo que gana el programa más corto (en bytes) para finales de este mes.

Casco , 17 bytes

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

Imprime un entero positivo si el gráfico es bipartito, 0si no. Pruébalo en línea!

Explicación

Este es un enfoque de fuerza bruta: recorra todos los subconjuntos S de vértices y vea si todos los bordes en el gráfico están entre S y su complemento.

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

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

Pruébalo en línea!

Cómo funciona

Dada una matriz de adyacencia A, encontramos el punto fijo de comenzar con B = A y luego reemplazar B por A ² B, ocasionalmente recortando valores mayores de 1 a 1. El ^késimo paso de este proceso es equivalente hasta Clipencontrar poderes A ^{2k + 1} , en el que la entrada (i, j) cuenta el número de rutas de longitud 2k + 1 desde el vértice i hasta j; por lo tanto, el punto fijo termina teniendo una entrada distinta de cero (i, j) si podemos ir de i a j en un número impar de pasos.

En particular, la diagonal del punto fijo tiene entradas distintas de cero solo cuando un vértice puede alcanzarse en un número impar de pasos: si hay un ciclo impar. Por lo tanto, la traza del punto fijo es 0 si y solo si el gráfico es bipartito.

Otra solución de 25 bytes de este formulario es Tr[#O@n//.x_:>#.#.x]===0&, en caso de que esto le dé a alguien ideas sobre cómo llevar el recuento de bytes aún más bajo.

Esfuerzos previos

He intentado varios enfoques para esta respuesta antes de decidirme por esta.

26 bytes: exponenciales de matriz

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

También se basa en poderes extraños de la matriz de adyacencia. ¡Dado que x * exp (x ² ) es x + x ³ + x ^5/2 ! + x ^7/4 ! + ..., cuando x es una matriz A, tiene un término positivo para cada potencia impar de A, por lo que también tendrá un rastro cero si A tiene un ciclo impar. Esta solución es muy lenta para matrices grandes.

29 bytes: gran potencia impar

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

Para una matriz n por n A, encuentra A ^{2n + 1} y luego realiza la verificación diagonal. Aquí, #~Table~Tr[2#!]genera 2n copias de la matriz de entrada n por n, y se #.##& @@ {a,b,c,d}descomprime en a.a.b.c.d, multiplicando juntas 2n + 1 copias de la matriz como resultado.

53 bytes: matriz laplaciana

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

Utiliza un resultado oscuro en la teoría de grafos espectrales ( Proposición 1.3.10 en este pdf ).

JavaScript, 78 bytes

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

Matriz de entrada de matriz de 0/1, salida verdadero / falso.

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 bytes

xmyss.D.DRx0dQx1d.nM*FQss

Pruébalo en línea!

Esto devuelve -1falso, y cualquier número entero no negativo para verdad.

Cómo funciona

xmyss.D.DRx0dQx1d.nM * FQss ~ Programa completo, recibe una matriz de adyacencia de STDIN.

                    * FQ ~ Reducir (doblar) por producto cartesiano.
                 .nM ~ Acoplar cada uno.
 m ~ Mapa con una variable d.
         RQ ~ Para cada elemento en la entrada,
       .D ~ Eliminar los elementos en los índices ...
          x0d ~ Todos los índices de 0 en d.
     .D ~ Y de esta lista, elimine los elementos en los índices ...
              x1d ~ Todos los índices de 1 en d.
    s ~ Acoplar.
   s ~ Suma. Podría haber usado s si [] no apareciera.
  y ~ Doble.
x ~ En el mapeo anterior, obtenga el primer índice de ...
                       ss ~ El número total de 1 en la matriz de entrada.

Esto funciona en commit d315e19 , la versión actual de Pyth que tiene TiO.

APL (Dyalog Extended) , ¹⁶ 13 bytes

⍱1 1⍉∨.∧⍣2⍣≡⍨

Pruébalo en línea!

^{-3 bytes gracias a @ H.PWiz.}

Utiliza el algoritmo de la respuesta superior de Mathematica de Misha Lavrov : inicialice A = B = M, multiplique Ba la izquierda dos veces Ay sujételo hasta que llegue al punto fijo, y pruebe si las entradas diagonales son todas cero.

El producto de matriz regular A+.×Bcuenta el número de rutas de dos pasos de nodo ma nodo que ppasan a través de cualquier nodo intermedio n. Si cambiamos el código a A∨.∧B, en su lugar obtenemos una matriz booleana que indica si existe una ruta de dos pasos de nodo ma nodo p. No necesitamos una operación adicional de "sujeción" de esa manera.

Cómo funciona

⍱1 1⍉∨.∧⍣2⍣≡⍨  ⍝ Input: adjacency matrix M
          ⍣≡⍨  ⍝ Find the fixed point, with
               ⍝     Starting point A = Left arg B = M...
     ∨.∧⍣2     ⍝   Left-multiply (matmul) B twice to A
               ⍝   indicating existence of paths (boolean)
 1 1⍉          ⍝ Extract the main diagonal
⍱              ⍝ Test if all elements are zero