Đồ thị lưỡng phân

Định nghĩa:

Đồ thị lưỡng phân là đồ thị G=(V; E) mà tập đỉnh V có thể phân hoạch thành hai tập hợp X, Y sao cho tập cạnh E chỉ gồm các cạnh nối hai đỉnh không cùng một tập hợp. Ta còn kí hiệu đồ thị lưỡng phân này là G=(X,Y;E)

Một tính chất cơ bản để nhận biết đồ thị lưỡng phân là định lý sau đây

Định lý: Một đồ thị G là đồ thị lưỡng phân khi và chỉ khi mọi chu trình của nó có độ dài chẵn.

Chứng minh. Giả sử G=(X,Y; E) là một đồ thị lưỡng phân. Khi đó dọc theo chu trình bất kỳ của G các đỉnh thuộc tập X và tập Y lần lượt kế tiếp nhau. Do đó, khi trở về đỉnh xuất phát đầu tiên, ta phải đi qua một số chẵn các đỉnh, do đó số cạnh ( bằng số đỉnh) của chu trình là một số chẵn.

Đảo lại, giả sử rằng G là một đồ thị mà tất cả các chu trình của G đều có độ dài chẵn. Ta sẽ chứng minh rằng tất cả các thành phần liên thông của G đều là các đồ thị lưỡng phân, và do đố G cũng là đồ thị lưỡng phân.

Thật vậy, giả sử rằng $G_1$ là một thành phần liên thông của G và $P_0$ là một đỉnh của đồ thị $G_1$. Với mỗi đỉnh P của đồ thị $G_1$, ta chọn một đường đi W nối đỉnh $P_0$ với đỉnh P. Nếu đường đi W có độ dài chẵn thì đỉnh P thuộc tập X, còn nếu đường đi W có độ dài lẻ thì đỉnh P được lấy vào tập Y. Sự phân loại các đỉnh của đồ thị $G_1$ không phụ thuộc vào cách chọn đường đi W. thật vậy, nếu có đường đi W với độ dài chẵn và đường đi W' với độ dài lẻ nối đỉnh $P_0$ với đỉnh P thì đồ thị $G_1$ sẽ có chu trình với độ dài lẻ, mâu thuẫn với giả thiết ban đầu.

Với các thiết lập tập hợp X và Y này, các đỉnh của đồ thị $G_1$ hoặc thuộc tập hợp X hoặc thuộc tập hợp Y. Bây giờ ta chuwgns minh rằng $G_1$ chỉ có các cạnh nối các đỉnh không cùng mọt tập hợp với nhau mà thôi. Thật vậy, giả sử rằng có hai đỉnh P và Q kề nhau trong đồ thị $G_1$ thì chugns không thể cùng thuộc một tập hợp X hoặc Y, nếu không từ $P_0$ ta có thể đi đến đỉnh P rồi tới đỉnh Q bởi cạnh (P,Q) và trở về đỉnh $P_0$ với một đường đi lẻ cạnh, điều không thể xảy ra trong đồ thị G do G chỉ có chu trình với số chẵn cạnh mà thôi. Như vậy đồ thị G là đồ thị lưỡng phân với hai tập đỉnh X và Y.