✨Đồ thị hai phía

thumb|Ví dụ về đồ thị hai phía không có chu trình Trong Lý thuyết đồ thị, đồ thị hai phía (đồ thị lưỡng phân hay đồ thị hai phần) (tiếng Anh: bipartite graph) là một đồ thị đặc biệt, trong đó tập các đỉnh có thể được chia thành hai tập không giao nhau thỏa mãn điều kiện không có cạnh nối hai đỉnh bất kỳ thuộc cùng một tập.

Những tính chất của đồ thị hai phía được đề cập đến đầu tiên bởi Dénes Kőnig(1916) . Dénes Kőnig cũng là người viết cuốn sách đầu tiên Theorie der endlichen und unendlichen Graphen 1936 về Lý thuyết đồ thị.

Đồ thị hai phía xuất hiện trong các bài toán dùng đồ thị biểu diễn quan hệ hai ngôi giữa hai tập A và tập B không giao nhau. Một ví dụ cho quan hệ này là quan hệ hôn nhân giữa hai tập hợp người nam và nữ.

Định nghĩa

Một đồ thị đơn vô hướng $G:=(V,E)$ được gọi là hai phía mà tập đỉnh của nó có thể chia thành hai tập con $X$ và $Y$ rời nhau sao cho bất kì cạnh nào của đồ thị cũng nối một đỉnh của $X$ với một đỉnh thuộc $Y$. Khi đó người ta còn ký hiệu là:

$G:=(X\; \backslash bigcup\; Y,\; E)$và gọi một tập (chẳng hạn $X$) là **tập các đỉnh trái** và tập còn lại (chẳng hạn $Y$) là **tập các đỉnh phải** của đồ thị hai phía $G$..

Nếu $|V\_1|=|V\_2|$ thì $G$ được gọi là đồ thị hai phía cân bằng.

Ví dụ

khung|giữa|Ví dụ về các đồ thị hai phía

khung|giữa|Ví dụ đồ thị không phải đồ thị hai phía

$K\_3$ không phải là đồ thị lưỡng phân vì nếu ta chia các đỉnh của nó thành 2 phần rời nhau thì một trong 2 phần này phải chứa 2 đỉnh. Nếu đồ thị là lưỡng phân thì các đỉnh này không thể nối với nhau bằng một cạnh. Nhưng trong K3 mỗi đỉnh được nối với đỉnh khác bằng một cạnh.

Một vài ví dụ trừu tượng:

• Mỗi cây là đồ thị hai phía.

• Biểu đồ chu kỳ với một số chẵn các đỉnh là đồ thị hai phía. ==Thuật toán kiểm tra một đồ thị liên thông là đồ thị hai phía

• Quang phổ của một đồ thị là đối xứng khi và chỉ khi nó là một đồ thị hai phía.

Ứng dụng

• Đồ thị hai phía thường được dùng để mô hình các bài toán ghép cặp (matching problem), quan hệ hôn nhân giữa tập những người đàn ông và tập những người đàn bà, sinh viên chọn trường, thầy giáo chon tiết dạy trong thời khóa biểu v.v...

• Đồ thị Levi là một dạng của đồ thị hai phía sử dụng để mô hình tỷ lệ mắc giữa điểm và đường trong một cấu hình.