Home » ĐỒ THỊ » Toán rời rạc: Kiểm tra đồ thị hai phía hay không?

Toán rời rạc: Kiểm tra đồ thị hai phía hay không?

Kiểm tra đồ thị hai phía

 

Có Ma trận kề của đồ thị lưu trong file văn bản có dạng như sau:

ma tran

Kết quả: Không hai phía.

HD: 

  • Đơn đồ thì G=(V,E) được gọi là hai phía nếu như tập đỉnh V của nó có thể phân hoạch thành hai tập X và Y sao cho mỗi cạnh của đồ thị chỉ nối với một đỉnh trong X và một đỉnh trong Y.
  • Thuật toán kiểm tra đồ thị liên thông là đồ thị hai phía:
  1.  Chọn v là một đỉnh bất kì của đồ thị. Đặt X={v};
  2. Tìm Y là tập đỉnh kề của các đỉnh trong X. Nếu X giao Y khác rỗng thì đồ thị không phải là 2 phía. Kết thúc. Ngược lại xuống B3.
  3. Tìm T là tập các đỉnh kề của các đỉnh trong Y. Nếu T giao Y khác rỗng thì đồ thị không phải là 2 phía. Kết thúc. Nếu T=X thì đồ thị là 2 phía, kết thúc. Ngược lại gán X=T và lặp lại B2.

Ví dụ

Untitled

 

 Code tham khảo đồ thị hai phía:

 

Share
  • Guest

    cái này đồ thị ko liên thông cho kết quá ko đúng

  • duc

    Đối với đồ thị ko liên thông thì sao?

Share
Free WordPress Themes - Download High-quality Templates