Đồ thị hai phía

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) [1][2][3]. 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 [4] 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 ${\displaystyle 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 ${\displaystyle X}$ và ${\displaystyle 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 ${\displaystyle X}$ với một đỉnh thuộc ${\displaystyle Y}$. Khi đó người ta còn ký hiệu là: ${\displaystyle G:=(X\bigcup Y,E)}$và gọi một tập (chẳng hạn ${\displaystyle X}$) là tập các đỉnh trái và tập còn lại (chẳng hạn ${\displaystyle Y}$) là tập các đỉnh phải của đồ thị hai phía ${\displaystyle G}$..[5]

Nếu ${\displaystyle |V_{1}|=|V_{2}|}$ thì ${\displaystyle G}$ được gọi là đồ thị hai phía cân bằng.

Ví dụ

Ví dụ về các đồ thị hai phía

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

${\displaystyle 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.[6]

• Biểu đồ chu kỳ với một số chẵn các đỉnh là đồ thị hai phía.[6]
• Biểu đồ Hypercube, các hình khối từng phần, và đồ thị trung bình là đồ thị hai phía.[7]

Thuật toán kiểm tra một đồ thị liên thông là đồ thị hai phía[5]

Để 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 ${\displaystyle v}$ bất kì:

X:= {v}; Y:=${\displaystyle \varnothing }$;
repeat
Y:= Y ${\displaystyle \cup }$ Kề(X);
X:= X ${\displaystyle \cup }$ Kề(Y);
until (X ${\displaystyle \cap }$ Y ${\displaystyle \neq \;\varnothing }$) or (X và Y là tối đại - không bổ sung được nữa);
if X ${\displaystyle \cap }$ Y ${\displaystyle \neq \;\varnothing }$ 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ẻ[2].

• Chứng minh

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:

Hình minh hoạ

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ẻ.

Chu trình lẻ

3. Tương tự như trường hợp 2.

${\displaystyle \Rightarrow \;}$ Định lý được chứng minh

Tính chất

• Kích thước của phủ đỉnh nhỏ nhất bằng kích thước của cặp ghép lớn nhất
• Kích thước của tập độc lập lớn nhất cộng kích thước của cặp ghép lớn nhất bằng số đỉnh.
• Trong đồ thị hai phía liên thông, kích thước của phủ cạnh nhỏ nhất bằng kích thước tập độc lập lớn nhất
• Trong đồ thị hai phía liên thông, kích thước của phủ cạnh nhỏ nhất cộng kích thước của phủ đỉnh nhỏ nhất bằng số đỉnh.
• Một đồ thị là hai phía khi và chỉ khi có thể tô màu nó bằng hai màu.[8]
• Quang phổ của một đồ thị là đối xứng khi và chỉ khi nó là một đồ thị hai phía.[9]

Ứ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...[5]
• Một ví dụ bài toán phân công công việc. Giả sử ta có một nhóm người P và một tập công việc J, trong đó không phải ai cũng hợp với mọi công việc. Ta có thể mô hình bài toán bằng một đồ thị với tập đỉnh là P + J. Nếu người ${\displaystyle p_{i}}$ có thể làm công việc ${\displaystyle j_{i}}$, đồ thị sẽ có một cạnh nối giữa ${\displaystyle p_{i}}$ và ${\displaystyle j_{i}}$. Định lý hôn nhân cung cấp một đặc điểm của đồ thị hai phía: tồn tại cặp ghép hoàn hảo (perfect matching).
• Đồ thị hai phía được sử dụng trong lý thuyết mã hóa (coding theory) hiện đại, đặc biệt khi giải mã các codeword nhận được từ kênh. Đồ thị nhân tử (factor graph) và đồ thị Tanner là các ví dụ.[10]

• Đồ 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.[11]

Xem thêm

• Đồ thị hai phía đầy đủ
• Dulmage-Mendelsohn Decomposition

Liên kết ngoài

• Weisstein, Eric W., "Complete k-Partite Graph" từ MathWorld.

Tham khảo

1. Asratian, Armen S., Tristan MJ Denley, and Roland Häggkvist. Bipartite graphs and their applications. Vol. 131. Cambridge University Press, 1998.
2. ^ D. König, Über Graphen und ihre Anwendung auf Determinantentheorie und Mengenlehre, Math. Ann. 77 (1916), no. 4, 453–465.
3. Asratian, Denley & Häggkvist (1998)Lỗi harv: không có mục tiêu: CITEREFAsratianDenleyHäggkvist1998 (trợ giúp), Theorem 2.1.3, p. 8. Asratian et al. attribute this characterization to a 1916 paper by Dénes Kőnig.
4. Kőnig, Dénes (1936), Theorie der endlichen und unendlichen Graphen, Leipzig: Akademische Verlagsgesellschaft. Translated from German by Richard McCoart, Theory of finite and infinite graphs, Birkhäuser, 1990, ISBN 0-8176-3389-8
5. ^ Giải thuật và lập trình (Lê Minh Hoàng), Đại Học Sư Phạm Hà Nội, 1999-2002
6. ^ Scheinerman, Edward A. (2012), Mathematics: A Discrete Introduction (ấn bản thứ 3), Cengage Learning, tr. 363, ISBN 9780840049421.
7. Ovchinnikov, Sergei (2011), Graphs and Cubes, Universitext, Springer. See especially Chapter 5, "Partial Cubes", pp. 127–181.
8. Asratian, Denley & Häggkvist (1998)Lỗi harv: không có mục tiêu: CITEREFAsratianDenleyHäggkvist1998 (trợ giúp), p. 7.
9. Biggs, Norman (1994), Algebraic Graph Theory, Cambridge Mathematical Library (ấn bản thứ 2), Cambridge University Press, tr. 53, ISBN 9780521458979.
10. Moon, Todd K. (2005), Error Correction Coding: Mathematical Methods and Algorithms, John Wiley & Sons, tr. 638, ISBN 9780471648000.
11. Grünbaum, Branko (2009), Configurations of Points and Lines, Graduate Studies in Mathematics, 103, American Mathematical Society, tr. 28, ISBN 9780821843086.

Thư mục

• The Art of Computer Programming, 3rd edition, Author: Donald E.Knuth. Publisher: Addison-Wesley, 1998
• Introduction to Algorithms, 2nd edition, ISBN: 0262032937, Author: Thomas H.Cormen, Charles E.Leiserson, Ronald,L.Rivest. Publisher: The MIT Press,2001
• Lý thuyết đồ thị (Trần Đan Thư - Dương Anh Đức), Trường Đại Học Khoa Học Tự Nhiên, Nhà Xuất Bản Đại học Quốc gia TP Hồ Chí Minh - 2008
• Giải thuật và lập trình (Lê Minh Hoàng), Đại Học Sư Phạm Hà Nội, 1999-2002