Biểu đồ hai phía
Biểu đồ hai phía - một biểu đồ có các đỉnh có thể được chia thành hai tập hợp sao cho mỗi cạnh kết nối các các đỉnh từ các tập hợp khác nhau.
Thông thường, trong ngữ cảnh của đồ thị hai phía, khái niệm màu sắc đỉnh được sử dụng. Việc chia một biểu đồ thành hai phần được gọi là tô màu các đỉnh của nó bằng hai màu khác nhau. Mỗi cạnh phải nối các đỉnh có màu khác nhau.
DFS.
Thuật toán
Chúng ta bắt đầu vẽ từ một đỉnh tùy ý và tô màu tùy ý.
Khi đi dọc theo mỗi cạnh, hãy sơn đỉnh tiếp theo bằng màu đối diện.
Nếu trong khi duyệt qua các đỉnh lân cận, chúng ta tìm thấy một đỉnh đã được sơn cùng màu với đỉnh hiện tại, thì đó là một chu trình lẻ trong đồ thị, nghĩa là nó không phải là hai cạnh.