5) Cuối cùng, nếu V
1 ∩ V
2 = ∅ thì két luận đồ thị là đồ thị hai phần.
Ví dụ 5.5: Xét đồ thị vô hướng.
Hình 5.5. Đồ thị vô hướng
Bắt đầu chọn: V
1 = {1} , V
2 = {2, 4}.
Sau đó thêm vào V
1 = {1, 2, 3, 4, 5} , ta có: V
1 ∩ V
2≠ ∅ .
Vậy đồ thị trên không là đồ thị hai phần.
Nếu bỏ cạnh (2, 4) thì đồ thị trên trở thành đồ thị hai phần.
Bạn đang xem 5) - LY THUYET DO THI BAI 8
