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

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

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

Đề bài

a) Giả sử GG là một đồ thị với nn đỉnh và (n−1)(n−2)2+2\dfrac{(n-1)(n-2)}{2}+2 cạnh. Sử dụng Định lí Ore, hãy chứng minh GG có một chu trình Hamilton.

b) Tìm một đồ thị với nn đỉnh và (n−1)(n−2)2+1\dfrac{(n-1)(n-2)}{2}+1 cạnh mà không có chu trình Hamilton.

Lời giải

Nhắc lại Định lí Ore. Cho GG là đồ thị đơn, vô hướng có nn đỉnh với n≥3n\ge 3. Nếu với *mọi* cặp đỉnh u,vu,v không kề nhau ta đều có deg⁡(u)+deg⁡(v)≥n\deg(u)+\deg(v)\ge n thì GG có một chu trình Hamilton.

a) Chứng minh GG có chu trình Hamilton.

Số cạnh của GG là
m=(n−1)(n−2)2+2.m=\dfrac{(n-1)(n-2)}{2}+2 .

Lấy tùy ý hai đỉnh u,vu,v không kề nhau của GG. Ta sẽ chứng minh deg⁡(u)+deg⁡(v)≥n\deg(u)+\deg(v)\ge n.

Xóa hai đỉnh u,vu,v (cùng các cạnh nối với chúng) khỏi GG, ta được một đồ thị đơn G′G' có n−2n-2 đỉnh. Vì đồ thị đơn n−2n-2 đỉnh có nhiều nhất (n−22)=(n−2)(n−3)2\dbinom{n-2}{2}=\dfrac{(n-2)(n-3)}{2} cạnh nên
số cạnh của G′ ≤ (n−2)(n−3)2.\text{số cạnh của }G'\ \le\ \dfrac{(n-2)(n-3)}{2}.

Mỗi cạnh bị xóa khi bỏ u,vu,v là cạnh nối với uu hoặc nối với vv. Do uu và vv *không kề nhau* nên không có cạnh nào nối trực tiếp uu với vv, vì vậy số cạnh nối với uu hoặc vv đúng bằng deg⁡(u)+deg⁡(v)\deg(u)+\deg(v) (không bị đếm trùng). Suy ra
m=(số cạnh của G′)+deg⁡(u)+deg⁡(v) ≤ (n−2)(n−3)2+deg⁡(u)+deg⁡(v).m=\big(\text{số cạnh của }G'\big)+\deg(u)+\deg(v)\ \le\ \dfrac{(n-2)(n-3)}{2}+\deg(u)+\deg(v).

Từ đó
deg⁡(u)+deg⁡(v) ≥ m−(n−2)(n−3)2=(n−1)(n−2)2+2−(n−2)(n−3)2.\deg(u)+\deg(v)\ \ge\ m-\dfrac{(n-2)(n-3)}{2}=\dfrac{(n-1)(n-2)}{2}+2-\dfrac{(n-2)(n-3)}{2}.

Tính hiệu hai phân số:
(n−1)(n−2)2−(n−2)(n−3)2=(n−2)[(n−1)−(n−3)]2=(n−2)⋅22=n−2.\dfrac{(n-1)(n-2)}{2}-\dfrac{(n-2)(n-3)}{2}=\dfrac{(n-2)\big[(n-1)-(n-3)\big]}{2}=\dfrac{(n-2)\cdot 2}{2}=n-2.

Vậy
deg⁡(u)+deg⁡(v) ≥ (n−2)+2=n.\deg(u)+\deg(v)\ \ge\ (n-2)+2=n.

Vì u,vu,v là cặp đỉnh không kề nhau tùy ý nên điều kiện của Định lí Ore được thỏa mãn (với n≥3n\ge 3). Theo Định lí Ore, GG có một chu trình Hamilton. ■\blacksquare

b) Đồ thị có (n−1)(n−2)2+1\dfrac{(n-1)(n-2)}{2}+1 cạnh mà không có chu trình Hamilton.

Xét đồ thị GG gồm:
- Một đồ thị đầy đủ Kn−1K_{n-1} trên n−1n-1 đỉnh (mọi cặp trong n−1n-1 đỉnh này đều kề nhau), có đúng (n−12)=(n−1)(n−2)2\dbinom{n-1}{2}=\dfrac{(n-1)(n-2)}{2} cạnh;
- Thêm đỉnh thứ nn, gọi là vv, và nối vv với đúng một đỉnh của Kn−1K_{n-1} bằng một cạnh.

Khi đó GG có nn đỉnh và số cạnh là
(n−1)(n−2)2+1.\dfrac{(n-1)(n-2)}{2}+1 .

Đỉnh vv chỉ có deg⁡(v)=1\deg(v)=1. Trong một chu trình Hamilton, mỗi đỉnh phải nối với hai đỉnh khác của chu trình, tức mọi đỉnh của chu trình đều có bậc ít nhất bằng 22. Vì deg⁡(v)=1<2\deg(v)=1<2 nên vv không thể nằm trên bất kì chu trình nào; do đó GG không có chu trình Hamilton.

(Đồ thị này cho thấy số cạnh (n−1)(n−2)2+2\dfrac{(n-1)(n-2)}{2}+2 ở câu a) là nhỏ nhất bảo đảm chắc chắn có chu trình Hamilton: chỉ cần ít hơn 11 cạnh thì kết luận có thể không còn đúng.)

Đáp số

đpcmLấy Kn−1K_{n-1} rồi nối thêm một đỉnh bằng một cạnh (đỉnh treo bậc 1); đồ thị có (n−1)(n−2)2+1\dfrac{(n-1)(n-2)}{2}+1 cạnh và không có chu trình Hamilton

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.