É bipartido?

13

Um gráfico bipartido é um gráfico cujos vértices podem ser divididos em dois conjuntos disjuntos, de modo que nenhuma aresta conecta dois vértices no mesmo conjunto. Um gráfico é bipartido se e somente se for de duas cores.

Desafio

Sua tarefa é, dada a matriz de adjacência de um gráfico simples não direcionado, determinar se é um gráfico bipartido. Ou seja, se uma aresta conecta os vértices iej, as entradas (i, j) e (j, i) da matriz são 1.

Como o gráfico não é direcionado e é simples, sua matriz de adjacência é simétrica e contém apenas 0 e 1.

Específicos

Você deve usar uma matriz N por N como entrada (de qualquer forma, por exemplo, lista de listas, lista de cadeias, int**tamanho e tipo C , matriz achatada, entrada bruta, etc.).

A função / programa deve retornar / gerar um valor verdadeiro se o gráfico for bipartido e, caso contrário, falsificar.

Casos de teste

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

Pontuação

Os componentes internos que calculam a resposta diretamente são banidos.

Isso é código-golfe , então o programa mais curto (em bytes) até o final deste mês vence!

code-golf decision-problem graph-theory binary-matrix Colera Su
fonte
Relacionado e, na verdade, tolo, porque ser bipartido é equivalente a não ter ciclos ímpares, e a maioria das respostas para essa pergunta funciona enumerando todos os ciclos e examinando seus comprimentos.
Peter Taylor
@ PeterTaylor Sim, mas existem maneiras mais simples de resolver esse problema.
Colera Su
@ColeraSu Em vez de verdade / falsidade, podemos retornar -1por falsidade e qualquer número inteiro não negativo para verdade?
Mr. Xcoder
@MishaLavrov 0-> Falsy, >0-> Truthy é geralmente permitido pelas regras padrão de truthy / falsy. -1e ≥ 0não é tão comum, é por isso que perguntei.
Mr. Xcoder
@ Mr.Xcoder Está tudo bem.
Colera Su

Respostas:

4

Casca , 17 bytes

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

Imprime um número inteiro positivo se o gráfico for bipartido, 0se não. Experimente online!

Explicação

Essa é uma abordagem de força bruta: itere em todos os subconjuntos S dos vértices e verifique se todas as arestas no gráfico estão entre S e seu 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.
Zgarb
fonte
@ Mr.Xcoder Bem, suponha M = [[1,2,3],[4,5,6],[7,8,9]]e S = [1,0,1]( Mé sempre uma matriz binária no programa, mas é mais fácil explicar dessa maneira). Filtrar cada linha de Mpor Sdá [[1,3],[4,6],[7,9]]: para cada linha, removo os elementos nos índices em que Shá um 0. Em seguida, nego o Selemento para obter [0,1,0]e filtre Mpor esse para obter [[4,6]]: a primeira e a última linha têm 0 nos índices correspondentes , para que eles sejam removidos.
Zgarb 17/11/19
17

Wolfram Language (Mathematica) , 26 25 bytes

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

Experimente online!

Como funciona

Dada uma matriz de adjacência A, encontramos o ponto fixo de começar com B = A e substituir B por A 2 B, ocasionalmente cortando valores maiores que 1 a 1. A k- ésima etapa desse processo é equivalente à capacidade Clipde encontrar Um 2k + 1 , no qual a entrada (i, j) conta o número de caminhos de comprimento 2k + 1 do vértice i até j; portanto, o ponto fixo acaba tendo uma entrada diferente de zero (i, j) se pudermos ir de i a j em um número ímpar de etapas.

Em particular, a diagonal do ponto fixo possui entradas diferentes de zero somente quando um vértice pode alcançar a si mesmo em um número ímpar de etapas: se houver um ciclo ímpar. Portanto, o traço do ponto fixo é 0 se e somente se o gráfico for bipartido.

Outra solução de 25 bytes deste formulário é Tr[#O@n//.x_:>#.#.x]===0&, caso isso dê a alguém idéias sobre como aumentar ainda mais a contagem de bytes.

Esforços anteriores

Eu tentei várias abordagens para essa resposta antes de decidir sobre essa.

26 bytes: exponenciais da matriz

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

Também conta com poderes ímpares da matriz de adjacência. Desde x * exp (x 2 ) é x + x 3 + x 5 /2! + x 7/4 ! + ..., quando x é uma matriz A, esse termo é positivo para todas as potências ímpares de A; portanto, também terá zero traço se A tiver um ciclo ímpar. Essa solução é muito lenta para matrizes grandes.

29 bytes: grande potência ímpar

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

Para uma matriz n por n A, localiza A 2n + 1 e depois faz a verificação diagonal. Aqui, #~Table~Tr[2#!]gera 2n cópias da matriz de entrada n por n e #.##& @@ {a,b,c,d}descompacta para a.a.b.c.d, multiplicando 2n + 1 cópias da matriz como resultado.

53 bytes: matriz da Lapônia

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

Usa um resultado obscuro na teoria dos grafos espectrais ( Proposição 1.3.10 neste pdf ).

Misha Lavrov
fonte
Eu acho que você pode raspar alguns bytes do seu método mais eficiente com Tr[#.Nest[#.#&,#,Tr[#!]]]<1&. (Esta é uma resposta incrível que está cada vez melhor a cada vez que olho para ela!)
Não é uma árvore
1
Isto tem menos bytes que as semi-encastrado (necessidades duas funções)BipartiteGraphQ@AdjacencyGraph@#&
Kelly Lowder
2
@KellyLowder: para matrizes grandes MatrixExpretorna resultados em termos de Rootobjetos não avaliados , que não são automaticamente simplificados quando adicionados. As N@forças Rootsão calculadas numericamente para que a veracidade possa ser avaliada.
Michael Seifert
1
@ Notatree Sua abordagem realmente reduz alguns bytes, mas eles custam; para matrizes 18x18, é 1000 vezes mais lento e piora a partir daí. Acho que, se fizer essa alteração, perco o direito de chamar o método eficiente de "eficiente".
Misha Lavrov #
1
@KellyLowder Você pode encurtar isso BipartiteGraphQ@*AdjacencyGraph, mas ainda é mais longo.
Martin Ender
3

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 da matriz de 0/1, saída verdadeira / falsa.

Mostrar snippet de código

tsh
fonte
2

Pitão , 25 bytes

xmyss.D.DRx0dQx1d.nM*FQss

Experimente online!

Isso retorna -1para falso e qualquer número inteiro não negativo para verdade.

Como funciona

xmyss.D.DRx0dQx1d.nM * FQss ~ Programa completo, recebe uma matriz de adjacência de STDIN.

                    * FQ ~ Reduzir (dobra) por produto cartesiano.
                 .nM ~ Achate cada um.
 m ~ Mapa com uma variável d.
         RQ ~ Para cada elemento na entrada,
       .D ~ Exclua os elementos nos índices ...
          x0d ~ Todos os índices de 0 em d.
     .D ~ E nessa lista, exclua os elementos nos índices ...
              x1d ~ Todos os índices de 1 em d.
    s ~ Achatar.
   s ~ Sum. Eu poderia ter usado s se [] não aparecesse.
  y ~ Duplo.
x ~ No mapeamento acima, obtenha o primeiro índice de ...
                       ss ~ O número total de 1s na matriz de entrada.

Isso funciona no commit d315e19 , a versão atual do Pyth TiO.

Mr. Xcoder
fonte