October 2024 – T's Lab

Một đồ thị $G$ được gọi là hai phần (hay lưỡng phân) nếu $V(G)$ có thể phân hoạch thành hai tập con $X$ và $Y$ , sao cho mỗi phần tử của $E(G)$ có một đầu mút trong $X$ và đầu mút còn lại trong $Y$ . Khi đó $X$ và $Y$ được gọi là các phần của đồ thị lưỡng phân. Ta ký hiệu đồ thị lưỡng phân với hai phần $X$ và $Y$ bởi $G[X,Y]$ . Nếu trong $G[X,Y]$ , mọi đỉnh thuộc $X$ được nối với mọi đỉnh của $Y$ thì $G[X,Y]$ được gọi là đồ thị lưỡng phân đầy đủ.

Ví dụ 1. Gọi $X$ và $Y$ lần lượt là tập các cầu thủ bóng đá và tập các câu lạc bộ trong một thành phố. Khi đó ta có đồ thị lưỡng phân $G[X,Y]$ , ở đây $x\in X$ được nối với $y\in Y$ khi và chỉ khi $x$ đã từng chơi cho $y$ .

Ví dụ 2 (Bài toán tối ưu trong đường sắt). Giả sử ta có một lịch trình các chuyến tàu cùng các điểm dừng của chúng, và cần tìm một tập hợp các ga tàu càng nhỏ càng tốt sao cho mọi chuyến tàu ghé thăm ít nhất một trong các ga đã chọn. Bài toán này có thể được mô hình hóa như một bài toán trên đồ thị lưỡng phân có các phần là tập các chuyến tàu và tập các ga tàu, mỗi chuyến tàu nối với ga mà nó sẽ dừng.

Bây giờ chúng tôi sẽ giới thiệu một số kết quả cơ bản về đồ thị hai phần.

Định lý 1. Cho đồ thị lưỡng phân $G[X,Y]$ không có đỉnh cô lập và thỏa mãn $\deg (x)\geq \deg (y)$ với mọi $xy\in E(G)$ ( $x\in X$ và $y\in Y$ ). Khi đó $\mid X\mid \leq \mid Y\mid$ . Đẳng thức xảy ra khi và chỉ khi $\deg (x)= \deg (y)$ với mọi $xy\in E(G)$ ( $x\in X$ và $y\in Y$ ).

Chứng minh. Vì $G$ không có đỉnh cô lập nên với mỗi $(x,y)\in X\times Y$ , ta có

$\displaystyle \sum_{y^{\prime}\in N(x)}\frac{1}{\deg (x)}=\sum_{x^{\prime}\in N(y)}\frac{1}{\deg (y)}=1.$

Suy ra

$\displaystyle \mid X\mid =\sum_{x\in X}\sum_{y\in N(x)}\frac{1}{\deg (x)}=\sum_{\substack{(x,y)\in X\times Y\\ xy\in E(G)}}\frac{1}{\deg x},$

và

$\displaystyle \mid Y\mid =\sum_{y\in Y}\sum_{x\in N(y)}\frac{1}{\deg (y)}=\sum_{\substack{(x,y)\in X\times Y\\ xy\in E(G)}}\frac{1}{\deg y}.$

Kết hợp với giả thiết $\deg (x)\geq \deg (y)$ với mọi $xy\in E(G)$ ( $x\in X$ và $y\in Y$ ) ta có những điều cần chứng minh. $\Box$

Định lý 2. Một đồ thị là lưỡng phân khi và chỉ khi nó không chứa chu trình độ dài lẻ.

Chứng minh. Nếu một đồ thị là lưỡng phân thì dọc theo một chu trình của nó, các đỉnh thuộc hai phần sẽ xuất hiện luân phiên. Vì thế, mỗi chu trình trong đồ thị lưỡng phân phải có độ dài là số chẵn. Bây giờ xét một đồ thị $G$ không chứa chu trình với độ dài là số lẻ. Ta chỉ cần xét tình huống $G$ là một đồ thị liên thông.

Gọi $T$ là một cây bao trùm trong $G$ (nó tồn tại theo [1]), và chọn một đỉnh $r$ làm gốc của cây này. Gọi $C$ là tập tất cả các đỉnh mà đường đi trong $T$ nối $r$ với nó có độ dài chẵn, và $L$ là tập tất cả các đỉnh mà đường đi trong $T$ nối $r$ với nó có độ dài chẵn. Khi đó $V(G)$ được phân hoạch thành hai phần $C$ và $L$ .

Ta sẽ chứng minh $G$ là đồ thị lưỡng phân với các phần là $L$ và $C$ . Xét hai đỉnh kề nhau $x$ và $y$ của $G$ . Nếu $xy\in T$ thì độ dài của $rTx$ và độ dài của $rTy$ khác tính chẵn-lẻ, do đó trong hai đỉnh $x$ , $y$ có một đỉnh thuộc $C$ và đỉnh còn lại thuộc $L$ . Nếu $xy\not \in T$ , từ giả thiết ta thấy chu trình $xTy\cup xy$ có độ dài chẵn. Theo phần chứng minh trước thì mỗi cạnh khác $xy$ thuộc chu trình này có các đầu mút thuộc hai phần khác nhau của phân hoạch, suy ra $x$ và $y$ thuộc hai phần khác nhau của phân hoạch. $\Box$