Na teoria dos grafos, um Cactus é um gráfico conectado, de modo que quaisquer dois ciclos simples distintos no gráfico compartilhem no máximo um vértice.

Aqui está um cacto com 3 ciclos simples, delineados com linhas tracejadas.

O gráfico a seguir é semelhante ao da foto acima, mas não é um cacto porque os dois vértices marcados em vermelho são compartilhados por dois ciclos simples.

As coisas podem ficar um pouco mais complicadas, por exemplo, o seguinte gráfico:

Pode parecer um cacto, mas não é. Isso pode ser mostrado destacando o seguinte ciclo:

Esse ciclo compartilha mais de um ponto com muitos dos ciclos mais óbvios do gráfico.

Definições

Um gráfico conectado é um gráfico que existe pelo menos um caminho entre dois vértices.
Um ciclo simples é um caminho em um gráfico que inicia e termina no mesmo vértice e não o visita mais de uma vez.
Um gráfico simples é um gráfico não direcionado e não ponderado, de modo que nenhum vértice é conectado um ao outro por mais de uma aresta e nenhum vértice é conectado a si mesmo. Um gráfico simples é o tipo mais básico de gráfico e é o que a maioria das pessoas quer dizer quando diz gráfico.

Tarefa

Pegue um gráfico simples como entrada e decida se é um gráfico Cactus. Você deve gerar dois valores distintos, um para True e outro para False. Você pode receber informações em qualquer formato que desejar.

Isso é código-golfe, então você deve tentar minimizar a contagem de bytes de suas respostas.

Casos de teste

Casos de Teste como Matrizes de Adjacência

code-golf decision-problem graph-theory Assistente de Trigo
fonte

Você pode dar uma olhada na minha solução, deixe-me saber se é válida? Eu caí como se o padrão óbvio fosse óbvio demais e que eu perdi alguma coisa.

Shaggy

@ Shaggy Não consigo ler JavaScript, se você explicar, eu posso.

Assistente de trigo

Eu posso tentar. Estou verificando duas coisas: 1) eContém exatamente um elemento E vcontém exatamente 2 AND é vigual ao primeiro elemento de e? 2) OR É vigual ao conjunto de união dos primeiros elementos de cada elemento em e? O segundo caso de teste passa a primeira verificação ( v=[1,2]=e[0]=[1,2]) e os outros casos de teste que devem ser verdadeiro jogo da segunda, por exemplo, o caso # 4: v=[1,2,3,4,5,6]=[e[0][0],e[1][0],e[2][0],e[4][0]]=[1,2,3,4,5,6].

Shaggy

@ Shaggy Isso não funciona, por exemplo, o primeiro diagrama fornecido falha.

console.log(f([1,2,3,4,5,6,7,8,9,10,11,12,13])([[1,2],[1,3],[3,4],[2,4],[3,5],[5,6],[6,7],[7,8],[8,5],[7,9],[9,10],[10,11],[11,7],[8,12],[8,13]]))

Assistente de trigo

Isso deveria retornar trueou false?

Shaggy

É um cacto?

Definições

Tarefa

Respostas:

Mathematica, 62 bytes