Cómo comprobar si un gráfico no dirigido tiene un ciclo de longitud impar

Question

Estoy tratando de encontrar un algoritmo de tiempo O (| V | + | E |) para verificar si un gráfico no dirigido conectado tiene un ciclo de longitud impar o no.

Estoy considerando hacer una búsqueda de primer orden en el gráfico e intentar etiquetar los vértices en blanco y negro de forma que no haya dos vértices etiquetados con el mismo color adyacentes.

¿Hay algún algoritmo más limpio para resolver este problema en tiempo lineal?

Answer 1

Su enfoque es el correcto. No puedes hacer nada mejor que eso.

La razón por la que funciona es que si etiqueta los vértices por su profundidad mientras hace BFS, entonces todos los bordes conectan las mismas etiquetas o etiquetas que difieren en uno. Está claro que si hay un borde que conecta las mismas etiquetas, entonces hay un ciclo extraño. De lo contrario, podemos colorear todas las etiquetas impares en blanco y todas las etiquetas pares en negro.

Answer 2

También se puede hacer usando DFS y la numeración de los vértices.

1. Reloj = 1
2. de inicio con un vértice 's', marcarlo como "visitado" y llamar Explora (s)

Explora (u)

1. si ya está "visitado", entonces si (clock-Num [u]) es impar, entonces hay un ciclo impar,

   else marque 'u' como "visitado"

2. Num [u] = clock ++;

3. para todos los nodos v adyacente de u

   i) Explore(v) 
       ii) clock=Num[u] 
   

Answer 3

En la inicialización, también es necesario para establecer Num [s] = 0.