Làm thế nào để kiểm tra nếu một đồ thị vô hướng có một chu kỳ dài lẻ

Question

Tôi đang cố gắng tìm một thuật toán thời gian O (| V | + | E |) để kiểm tra xem một biểu đồ không bị kết nối có một chu kỳ có chiều dài lẻ hay không.

Tôi đang cân nhắc thực hiện Tìm kiếm thứ nhất trên biểu đồ và cố gắng gắn nhãn các đỉnh đen và trắng sao cho không có hai đỉnh được gắn nhãn có cùng màu liền kề nhau.

Có thuật toán nào được biết đến để giải quyết vấn đề này trong thời gian tuyến tính không?

Answer 1

Cách tiếp cận của bạn là đúng. Bạn không thể làm tốt hơn thế.

Lý do hoạt động là nếu bạn gắn nhãn cho các đỉnh theo chiều sâu của chúng trong khi thực hiện BFS, thì tất cả các cạnh sẽ kết nối các nhãn hoặc nhãn giống nhau khác nhau. Rõ ràng là nếu có một cạnh kết nối các nhãn giống nhau thì có một chu kỳ lẻ. Nếu không thì chúng ta có thể tô màu tất cả các nhãn màu trắng và tất cả các nhãn màu đen.

Answer 2

Nó cũng có thể được thực hiện bằng cách sử dụng DFS và đánh số các đỉnh.

1. Clock = 1
2. Bắt đầu với một đỉnh 's', đánh dấu nó như là "viếng thăm" và gọi Explore (s)

Khám phá (u)

1. nếu u đã "truy cập", thì nếu (đồng hồ-Num [u]) là lẻ, thì có một chu kỳ lẻ,

   khác đánh dấu 'u' là "đã truy cập"

2. Num [u] = clock ++;

3. cho tất cả các nút liền kề v của u

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

Answer 3

Trong khởi tạo, bạn cũng cần phải thiết lập Num [s] = 0.