Jak sprawdzić, czy nieukierunkowany wykres ma nieparzysty cykl długości?

Question

Próbuję znaleźć algorytm czasowy O (| V | + | E |), aby sprawdzić, czy połączony niepowiązany wykres ma cykl nieparzystej długości, czy też nie.

Rozważam wykonanie pierwszego zakresu na wykresie i próbę oznaczenia wierzchołków w czerni i bieli, tak aby nie byłysiadowały dwa wierzchołki oznaczone tym samym kolorem.

Czy istnieje jakiś znany algorytm do rozwiązania tego problemu w czasie liniowym?

Answer 1

Twoje podejście jest właściwe. Nie możesz zrobić nic lepszego.

Powodem tego jest to, że jeśli etykietujesz wierzchołki według ich głębokości podczas wykonywania BFS, wszystkie krawędzie łączą te same etykiety lub etykiety, które różnią się o jeden. Oczywiste jest, że jeśli istnieje krawędź łącząca te same etykiety, wówczas istnieje nieparzysty cykl. Jeśli nie, możemy pokolorować wszystkie etykiety nieparzyste, białe, a wszystkie równe czarne.

Answer 2

Można to również zrobić przy użyciu systemu plików DFS i numerowania wierzchołków.

1. Clock = 1
2. start z wierzchołkiem 's', oznaczyć ją jako "odwiedził" i nazywają Przeglądaj (s)

Przeglądaj (u)

1. jeśli u jest już "odwiedzane", to jeśli (zegar-Num [u]) jest nieparzyste, wówczas występuje nieparzysty cykl,

   inny znak "u" jako "odwiedzony"

2. Num [u] = zegar ++;

3. dla każdego sąsiedniego węzłów v u

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

Answer 3

Przy inicjalizacji, można również trzeba ustawić Num [s] = 0.