Chuyên đề học tập Toán 11

Giải Bài 2.11 trang 45 Chuyên đề Toán 11

Bài 9. Đường đi Euler và đường đi Hamilton   Đã kiểm chéo

Đề bài

Hãy chỉ ra một ví dụ chứng tỏ rằng điều kiện bậc của mỗi đỉnh của đồ thị GG không nhỏ hơn n2\dfrac{n}{2} trong Định lí Dirac, không thể thay bằng điều kiện "bậc của mỗi đỉnh không nhỏ hơn n−12\dfrac{n-1}{2}".

Lời giải

Nhắc lại Định lí Dirac (SGK). Cho đồ thị GG có nn đỉnh (n≥3n\ge 3). Nếu bậc của mỗi đỉnh của GG đều không nhỏ hơn n2\dfrac{n}{2} thì GG có chu trình Hamilton.

Ta phải chỉ ra một đồ thị trong đó bậc của mỗi đỉnh đều không nhỏ hơn n−12\dfrac{n-1}{2} nhưng đồ thị không có chu trình Hamilton. Khi đó điều kiện n2\dfrac{n}{2} không thể hạ xuống thành n−12\dfrac{n-1}{2}.

Xây dựng ví dụ (n=5n=5). Xét đồ thị GG gồm hai tam giác (hai đồ thị đầy đủ K3K_3) có chung đúng một đỉnh OO:
- Tam giác thứ nhất: O,A,BO, A, B với các cạnh OA,OB,ABOA, OB, AB;
- Tam giác thứ hai: O,C,DO, C, D với các cạnh OC,OD,CDOC, OD, CD.

Đồ thị có 55 đỉnh nên n=5n=5 và n−12=5−12=2\dfrac{n-1}{2}=\dfrac{5-1}{2}=2.

Kiểm tra bậc của các đỉnh.
- deg⁡(O)=4\deg(O)=4 (nối với A,B,C,DA,B,C,D);
- deg⁡(A)=deg⁡(B)=deg⁡(C)=deg⁡(D)=2\deg(A)=\deg(B)=\deg(C)=\deg(D)=2.

Vậy mọi đỉnh đều có bậc ≥2=n−12\ge 2=\dfrac{n-1}{2}, tức là GG thỏa mãn điều kiện "bậc mỗi đỉnh không nhỏ hơn n−12\dfrac{n-1}{2}".

(Lưu ý: n2=2,5\dfrac{n}{2}=2{,}5, mà deg⁡(A)=2<2,5\deg(A)=2<2{,}5 nên GG không thỏa mãn điều kiện Dirac — đúng như mong muốn.)

Chứng tỏ GG không có chu trình Hamilton. Khi bỏ đỉnh OO (cùng các cạnh nối với nó), đồ thị tách thành hai phần rời nhau là {A,B}\{A,B\} và {C,D}\{C,D\}; như vậy OO là đỉnh cắt. Một chu trình Hamilton phải đi qua đủ cả bốn đỉnh A,B,C,DA, B, C, D. Nhưng mọi đường nối từ nhóm {A,B}\{A,B\} sang nhóm {C,D}\{C,D\} đều bắt buộc đi qua OO, trong khi một chu trình chỉ được đi qua OO đúng một lần. Do đó không thể vừa nối A,BA,B vừa chuyển sang C,DC,D rồi quay về khép kín — nghĩa là GG không có chu trình Hamilton.

Kết luận. Đồ thị GG ở trên có bậc mỗi đỉnh ≥n−12\ge \dfrac{n-1}{2} nhưng không có chu trình Hamilton. Vậy trong Định lí Dirac, điều kiện bậc mỗi đỉnh không nhỏ hơn n2\dfrac{n}{2} không thể thay bằng điều kiện bậc mỗi đỉnh không nhỏ hơn n−12\dfrac{n-1}{2} (đpcm).

Đáp số

đpcm

Lời giải do Thư viện nhà trường biên soạn, giải và kiểm chéo độc lập theo SGK 2026-2027.