Đồ 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.

Mở rộng của định lý Dirac

Định lý Ore: Nếu đồ thị vô hướng G=(V,E) có số đỉnh là $n \ge 3$ và $deg(u)+deg(v) \ge n$ thỏa mãn cho mọi cặp đỉnh không kề nhau u và v của G, thì G là đồ thị Hamilton.

Chứng minh.

Giả sử định lý không đúng và G=(V, E) có cỡ cực đại cấp n thỏa mãn các điều kiện của Định lý nhưng không là đồ thị Hamilton. Dễ thấy rằng thêm một cạnh bất kỳ vào một đồ thị có những tính chất chỉ ra trong định lý sẽ tạo ra một đồ thị cũng có những tính chất ấy. Vì G là đồ thị không là Hamilton cấp n có cỡ cực đại thỏa mãn các điều kiện , nên đồ thị nhận được khi thêm vào G một cạnh bất kì nối hai đỉnh không kề nhau trong G là đồ thị có chu trình Hamilton cạnh thêm đó. Suy ra hai đỉnh bất kỳ không kề nhau trong G được nối với nhau bằng một đường Hamilton

Vì G không là đồ thị Hamilton nên G khác đồ thị đầy đủ $K_n$. Do đó tồn tại hai đỉnh không kề nhau trong G, chẳng hạn $v_1$ và $v_n$. Theo khẳng định vừa chứng minh ở đoạn trên tồn tại trong G đường Hamilton nối $v_1$ với $v_n$ chẳng hạn $v_1v_2..v_n$.

Kí hiệu các đỉnh kề với $v_1$ bằng $v_{i_1},v_{i_2},..v_{i_k}$ trong đó k là bậc của đỉnh $v_1$ và $2=i_1<i_2<..<i_k$. Hiền nhiên là $v_n$ không thể kề với một đỉnh nào của G dạng $v_{i_j-1}$ bởi vì khi đó G sẽ có chu trình Hamilton là $v_1v_2..v_{i_j-1}v_nv_{n-1}..v_{i_j}v_1$.

Do đó ký hiệu $N(v_1)=\begin{Bmatrix}
v_{i_j} \in V|j=1,2,..k
\end{Bmatrix}$ và $N*(v_n)=\begin{Bmatrix}
v_{i+1} \in V | v_i \ne v_n, \begin{Bmatrix}
v_i,v_n
\end{Bmatrix} \in E
\end{Bmatrix}$

Thì $N(v_1) \cap N^*(v_n)$ là rỗng.

Vì thế: $n \le deg(v_1)+deg(v_n) = k+(n-1-k)=n-1$ (mâu thuẫn)

Như vậy ta có điều phải chứng minh.

Có thể thấy rằng định lý Dirac  này là hệ quả của định lý Ore do:

nếu có hai đỉnh trong đồ thị không kề nhau bất kì u và v trong G ta có $deg(u)+deg(v) \ge n/2+n/2=n$ áp dụng định lý Ore ta có điều phải chứng minh.