Hiểu phân vùng trong lý thuyết đồ thị

Trong lý thuyết đồ thị, phân chia một đồ thị là phép chia tập hợp đỉnh của nó thành hai tập hợp rời nhau (được gọi là tập hợp phân chia) sao cho tất cả các cạnh đều kết nối các đỉnh từ các tập hợp phân chia khác nhau. Nói cách khác, không có cạnh nào giữa các đỉnh trong cùng một tập hợp partite.

Ví dụ, xét một đồ thị có 4 đỉnh {a,b,c,d} và chúng ta chia tập hợp đỉnh thành hai phần: {a,b} và {đĩa CD}. Biểu đồ là hai phần vì tất cả các cạnh kết nối các đỉnh từ các phần khác nhau.

Bipartition có thể được sử dụng để giảm độ phức tạp của các thuật toán cho các vấn đề về đồ thị như truyền tải đồ thị, tìm đường đi ngắn nhất và khớp đồ thị.