Come verificare se un grafico non orientato ha un ciclo di lunghezza dispari

Question

Sto tentando di trovare un algoritmo O (| V | + | E |) per verificare se un grafico collegato non ha un ciclo di lunghezza dispari o meno.

Sto considerando di eseguire una ricerca di larghezza sul grafico e provare ad etichettare i vertici in bianco e nero in modo tale che due vertici etichettati con lo stesso colore siano adiacenti.

Esiste un algoritmo neater noto per risolvere questo problema in tempo lineare?

Answer 1

Il tuo approccio è quello giusto. Non puoi fare di meglio.

Il motivo è che se si etichettano i vertici in base alla profondità mentre si esegue BFS, tutti i bordi connettono le stesse etichette o etichette che differiscono di uno. È chiaro che se c'è un bordo che collega le stesse etichette, allora c'è un ciclo dispari. In caso contrario, possiamo colorare tutte le etichette dispari in bianco e tutte le etichette pari in nero.

Answer 2

Può anche essere eseguito utilizzando DFS e numerando i vertici.

1. orologio = 1
2. Inizia con 's' un vertice, contrassegnare come "visitato" e chiamare Esplora (s)

Esplora (u)

1. se è già "visitato", quindi se (orologio-Num [u]) è dispari, allora c'è un ciclo dispari,

   altro contrassegno "u" come "visitato"

2. Num [u] = clock ++;

3. per tutti i nodi adiacenti v di u

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

Answer 3

Nella inizializzazione, è anche necessario impostare Num [s] = 0.