Giải chi tiết chuyên đề Toán 11 kết nối mới bài tập cuối chuyên đề 2

Đồ thị này là một đơn đồ thị nhưng không phải là đồ thị đầy đủ. 

2.21. Chứng minh rằng không có đơn đồ thị với 12 đỉnh và 28 cạnh mà các đỉnh đều có bậc 3 hoặc 6. 

Hướng dẫn trả lời:

Gọi x là số đỉnh bậc 3 của đồ thị. Khi đó số đỉnh bậc 6 của đồ thị là 12 - x. Tổng tất cả các bậc của đỉnh là 3x + 6(12 - x).

Vì đồ thị có 28 cạnh nên ta có: 3x + 6(12 - x) = 2.28 = 56 ⇔ $x=\frac{16}{3}$ (loại, vì số đỉnh phải là số tự nhiên).

Suy ra điều cần phải chứng minh.

2.22. Chứng minh rằng nếu G là một đơn đồ thị có ít nhất hai đỉnh thì G có ít nhất hai đỉnh có cùng bậc.

Hướng dẫn trả lời:

Gọi số đỉnh của đồ thị là n (n ≥ 2)

Theo Nguyên lí chuồng bồ câu: Nếu một số lượng n vật thể được đặt vào m chuồng bồ câu, với điều kiện n > m, thì ít nhất một chuồng bồ câu sẽ có nhiều hơn 1 vật thể.

Một bậc của một đỉnh coi như một chuồng: tối đa n - 1, tối thiểu là 1.

Ví dụ: n = 10, 10 đỉnh có tối thiểu: bậc 1; tối đa: bậc 9.

Đồ thị có 10 đỉnh thì có hai đỉnh cùng bậc. (đcpcm)

2.23. Tìm số đỉnh nhỏ nhất cần thiết để có thể xây dựng một đồ thị đầy đủ với ít nhất 1000 cạnh.

Hướng dẫn trả lời:

Gọi số đỉnh của đồ thị là n.

Theo bài tập 2.4 trang 40 (Bài 8: Một vài khái niệm cơ bản) ta có: Một đồ thị đầy đủ có n đỉnh thì có $\frac{n(n-1)}{2}$ cạnh.

Ta có: $\frac{n(n-1)}{2}\geq 1000\Leftrightarrow n^{2}-n-2000\geq 0$

$\Leftrightarrow x \leq \frac{1-3\sqrt{889}}{2}$ hoặc $\frac{1+3\sqrt{889}}{2} \leq x$

Vì n là số tự nhiên dương nên chọn giá trị $45\approx \frac{1+3\sqrt{889}}{2}\leq x$

Vậy số đỉnh nhỏ nhất cần thiết là 45 thì có thể xây dựng một đồ thị đầy đủ với ít nhất 1 000 cạnh

2.24. Hãy chỉ ra ít nhất 5 đường đi từ S đến Y trong đồ thị trên Hình 2.38.

Hướng dẫn trả lời:

Đường đi từ S đến Y là: SVIZY, SVUIZY, SVIZXY, SIZY, SIZWXY.

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

Hướng dẫn trả lời:

Định lí Ore: Nếu G là đơn đồ thị có n đỉnh (n ≥ 3) và mỗi cặp đỉnh không kề nhau đều có tổng bậc không nhỏ hơn n thì G có một chu trình Hamilton.

Hình 2.39a có 5 đỉnh, các cặp đỉnh không kề nhau là B và D (tổng bậc hai đỉnh là 3 + 3 = 6 > 5); C và E (tổng bậc hai đỉnh là 3 + 3 = 6 > 5). Suy ra, đồ thị thỏa mãn với các điều kiện của định lí Ore. 

Hình 2.39b có 5 đỉnh, các cặp đỉnh không kề nhau là M và Q (tổng bậc hai đỉnh là 2 + 2 = 4 < 5); M và P (tổng bậc hai đỉnh là 2 + 2 = 4 < 5); N và Q (tổng bậc hai đỉnh là 3 + 2 = 5); P và H (tổng bậc hai đỉnh là 2 + 3 = 5). Suy ra có cặp đỉnh M và Q, M và P không thỏa mãn điều kiện của định lí Ore. 

2.26. Tìm một chu trình Euler trong đồ thị trên Hình 2.40.

Hướng dẫn trả lời:

Một chu trình Euler trong đồ thị trên Hình 2.40 là: ABCDEFAECA.

2.27. Giải bài toán người đưa thư đối với đồ thị có trọng số trên Hình 2.41.

Hướng dẫn trả lời: