En la teoría de gráficos, un Cactus es un gráfico conectado de tal manera que dos ciclos simples distintos en el gráfico comparten como máximo un vértice.

Aquí hay un Cactus con 3 ciclos simples delineados con líneas discontinuas.

El siguiente gráfico es similar al que se muestra arriba, pero no es un Cactus porque los dos vértices etiquetados en rojo son compartidos por dos ciclos simples.

Las cosas pueden ponerse un poco más complicadas, por ejemplo, el siguiente gráfico:

Puede parecer un cactus pero no lo es. Esto se puede mostrar resaltando el siguiente ciclo:

Este ciclo comparte más de un punto con muchos de los ciclos más obvios en el gráfico.

Definiciones

Un gráfico conectado es un gráfico tal que existe al menos una ruta entre dos vértices.
Un ciclo simple es una ruta en un gráfico que comienza y termina en el mismo vértice y no visita ningún vértice más de una vez.
Un gráfico simple es un gráfico no dirigido, no ponderado, de modo que no hay vértices conectados entre sí por más de un borde y ningún vértice está conectado a sí mismo. Un gráfico simple es el tipo de gráfico más básico y es lo que la mayoría de la gente quiere decir cuando dice gráfico.

Tarea

Tome un gráfico simple como entrada y decida si es un gráfico Cactus. Debe generar dos valores distintos, uno para True y otro para False. Puede tomar la entrada en cualquier formato que considere conveniente.

Este es el código de golf, por lo que debe intentar minimizar el recuento de bytes de sus respuestas.

Casos de prueba

Casos de prueba como matrices de adyacencia

code-golf decision-problem graph-theory Asistente de trigo
fuente

¿Puede echar un vistazo a mi solución, avíseme si es válida? Me caí como si el patrón obvio fuera demasiado obvio y que me haya perdido algo.

Shaggy

@ Shaggy No puedo leer JavaScript, si lo explicas podría hacerlo.

Wheat Wizard

Puedo probar. Estoy buscando 2 cosas: 1) ¿ eContiene exactamente un elemento Y vcontiene exactamente 2 Y es vigual al primer elemento de e? 2) O ¿Es vigual al conjunto de unión de los primeros elementos de cada elemento en e? El segundo caso de prueba pasa la primera verificación ( v=[1,2]=e[0]=[1,2]) y los otros casos de prueba que deben ser verdadera partido el segundo, por ejemplo el 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 Esto no funciona, por ejemplo, el primer diagrama proporcionado falla.

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]]))

Wheat Wizard

¿Debería eso volver trueo false?

Shaggy

¿Es un cactus?

Definiciones

Tarea

Respuestas:

Mathematica, 62 bytes