¿Es un cactus?

23

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.

Gráfico de cactus

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.

No gráfico de cactus

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

Tampoco es un gráfico de cactus

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

Ciclo destacado

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 por lo que debe intentar minimizar el recuento de bytes de sus respuestas.

Casos de prueba

Casos de prueba como matrices de adyacencia

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

Respuestas:

9

Mathematica, 62 bytes

Sort@#==#⋃#&[Join@@FindCycle[#,∞,All]]&&ConnectedGraphQ@#&

Cheques: (find all cycles, there are no duplicate edges)y(The graph is a connected graph)

JungHwan Min
fuente
1
gdebería ser #, ¿verdad?
ngenisis
66
¿Entonces me estás diciendo que no hay isCactusconstrucción? Estoy decepcionado.
Aaron
Alguien debería escribir uno.
Draco18s
Debe poner Mathematica Simplified como una respuesta separada.
mbomb007
3
@ Aaron Sería CactusQsi existiera, creo.
NieDzejkob