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

Giải Bài 2.25 trang 50 Chuyên đề Toán 11

Bài tập cuối chuyên đề 2   Đã kiểm chéo

Đề bài

Kiểm tra xem các điều kiện của định lí Ore có thoả mãn với các đồ thị trên Hình 2.39 không.

Bài có hình vẽ / bảng trong sách — xem ở trang 50 · mở sách.
Hình trong bài (mô tả bằng lời):

Hình 2.39: Hai đồ thị dạng ngũ giác với các đỉnh AA (đỉnh trên), BB (phải trên), CC (phải dưới), DD (trái dưới), EE (trái trên).
a) Ngũ giác A,B,C,D,EA, B, C, D, E có các cạnh ngoài A−BA-B, B−CB-C, C−DC-D, D−ED-E, E−AE-A; cùng các cạnh trong (đường chéo): E−BE-B, A−DA-D, A−CA-C (từ AA kẻ tới DD và CC, và EE nối BB).
b) Ngũ giác A,B,C,D,EA, B, C, D, E có các cạnh ngoài A−BA-B, B−CB-C, C−DC-D, D−ED-E, E−AE-A; cùng một cạnh trong E−BE-B.

Lời giải

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

Cả hai đồ thị trong Hình 2.39 đều có n=5n = 5 đỉnh, nên ta cần kiểm tra điều kiện: mọi cặp đỉnh không kề nhau có tổng bậc không nhỏ hơn 55.

a) Đồ thị có các cạnh ABAB, BCBC, CDCD, DEDE, EAEA, EBEB, ADAD, ACAC.

Bậc của các đỉnh:

- AA kề với BB, CC, DD, EE nên deg⁡(A)=4\deg(A) = 4;
- BB kề với AA, CC, EE nên deg⁡(B)=3\deg(B) = 3;
- CC kề với AA, BB, DD nên deg⁡(C)=3\deg(C) = 3;
- DD kề với AA, CC, EE nên deg⁡(D)=3\deg(D) = 3;
- EE kề với AA, BB, DD nên deg⁡(E)=3\deg(E) = 3.

Vì AA kề với tất cả các đỉnh còn lại nên các cặp đỉnh không kề nhau chỉ gồm (B,D)(B, D) và (C,E)(C, E). Ta có:

deg⁡(B)+deg⁡(D)=3+3=6≥5;\deg(B) + \deg(D) = 3 + 3 = 6 \geq 5;

deg⁡(C)+deg⁡(E)=3+3=6≥5.\deg(C) + \deg(E) = 3 + 3 = 6 \geq 5.

Vậy mọi cặp đỉnh không kề nhau đều có tổng bậc không nhỏ hơn 55, do đó điều kiện của định lí Ore được thoả mãn.

b) Đồ thị có các cạnh ABAB, BCBC, CDCD, DEDE, EAEA, EBEB.

Bậc của các đỉnh:

- AA kề với BB, EE nên deg⁡(A)=2\deg(A) = 2;
- BB kề với AA, CC, EE nên deg⁡(B)=3\deg(B) = 3;
- CC kề với BB, DD nên deg⁡(C)=2\deg(C) = 2;
- DD kề với CC, EE nên deg⁡(D)=2\deg(D) = 2;
- EE kề với AA, BB, DD nên deg⁡(E)=3\deg(E) = 3.

Các cặp đỉnh không kề nhau là (A,C)(A, C), (A,D)(A, D), (B,D)(B, D), (C,E)(C, E). Xét cặp (A,C)(A, C):

deg⁡(A)+deg⁡(C)=2+2=4<5.\deg(A) + \deg(C) = 2 + 2 = 4 < 5.

Vậy tồn tại cặp đỉnh không kề nhau có tổng bậc nhỏ hơn 55, do đó điều kiện của định lí Ore không được thoả mãn.

Đáp số

a) Điều kiện của định lí Ore được thoả mãn (mọi cặp đỉnh không kề nhau đều có tổng bậc ≥5\geq 5)b) Điều kiện của định lí Ore không được thoả mãn (cặp A,CA, C không kề nhau có deg⁡(A)+deg⁡(C)=4<5\deg(A)+\deg(C)=4<5)

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.