Tóm tắt đề bài:
Cho $G$ là đồ thị vô hướng, liên thông mạnh có $n$ đỉnh và $e$ cạnh, xác định xem $G$ có phải đồ thị hai phía (bipartite graph) hay không?
Hướng giải:
Đề đã cho là đồ thị liên thông mạnh. Vì vậy ta sẽ dùng thuật tô màu đồ thị để xác định.
- Nếu một đỉnh chưa tô màu, thử tô màu đỉnh đó màu 1. Khi đó, tất cả các đỉnh kề với 1 phải có màu 2. Nếu không thỏa các điều kiện này, thử tô đỉnh đó màu 2 và cũng xét các điều kiện tương ứng. Nếu không tô được thì out ở bước này.
- Nếu một đỉnh có màu 1 bắt buộc các đỉnh kề với đỉnh này phải có màu 2 và ngược lại. Nếu có 2 đỉnh cùng màu thì out.
Nếu đề bài không cho điều kiện liên thông mạnh, ta phải thêm 1 bước là xác
định số thành phần liên thông. Đồ thị hai phía chỉ có 1 thành phần liên thông
duy nhất.
No comments:
Post a Comment