Đồ thị hai phía

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 formula_1 được gọi là hai phía mà tập đỉnh của nó có thể chia thành hai tập con formula_2 và formula_3 rời nhau sao cho bất kì cạnh nào của đồ thị cũng nối một đỉnh của formula_2 với một đỉnh thuộc formula_3. Khi đó người ta còn ký hiệu là: 
formula_6và gọi một tập (chẳng hạn formula_2) là tập các đỉnh trái và tập còn lại (chẳng hạn formula_3) là tập các đỉnh phải của đồ thị hai phía formula_9..
Nếu formula_10 thì formula_9 được gọi là đồ thị hai phía cân bằng.
Ví dụ.
formula_12 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:
Thuật toán kiểm tra một đồ thị liên thông là đồ thị hai phía.
Để kiểm tra một đồ thị liên thông có phải là đồ thị hai phía hay không, ta có thể áp dụng thuật toán sau:
Với một đỉnh formula_13 bất kì:
 X:= {v}; Y:=formula_14;
 repeat
 Y:= Y formula_15 Kề(X);
 X:= X formula_16 Kề(Y);
 until (X formula_17 Y formula_18) or (X và Y là tối đại - không bổ sung được nữa);
 if X formula_17 Y formula_18 then
 (Không phải đồ thị hai phía)
 else
 (Đây là đồ thị hai phía
 X là tập các đỉnh trái: các đỉnh đến được từ v qua một số chẵn cạnh
 Y là tập các đỉnh cạnh phải: các đỉnh đến được từ v qua một số lẻ cạnh);
Định lý.
Một đồ thị A là hai phần khi và chỉ khi G không có chu trình lẻ.
Chứng minh theo chiều thuận
G là hai phần và có 1 chu trình đi qua u ∈ U khi đó số lần đi vào u bằng số lần đi
ra khỏi u và tổng số cạnh của chu trình là số cạnh kề với tập đỉnh thuộc một trong
hai tập U hoặc V thuộc chu trình đó,nên ta có 1 chu trình độ dài chẵn.
Ta có hình vẽ minh hoạ như sau:
Chứng minh theo chiều nghịch
Không mất tính tổng quát ta giả sử G liên thông,chọn một đỉnh u bất kì,với mỗi
đỉnh v ∈ V(G) do tính liên thông của G sẽ tồn tại một đường đi từ u đến v nếu độ
dài đường đi này là chẵn thì cho v vào tập U,ngược lại thì cho v vào V.
Ta sẽ chứng minh:
1. Cách xây dựng này là không mâu thuẫn.
2. Không có cạnh nào trong U.
3. Không có cạnh nào trong V.
Từ ba điều trên thì đồ thị đã cho là đồ thị hai phần.
Ta đi chứng minh 3 ý trên.
1. Giả sử phản chứng tồn tại hai đường đi chẵn,lẻ từ u đến v thì sẽ tồn tại một chu trình lẻ suy ra mâu thuẫn với giả thiết.
2. Giả sử tồn tại cạnh (x,y) ∈ U khi đó tồn tại đường đi độ dài chẵn từ u đến x và từ v đến y nên sẽ có 1 chu trình lẻ.
3. Tương tự như trường hợp 2.
formula_21 Định lý được chứng minh