Bài 2.12 trang 45 Chuyên đề học tập Toán 11 Kết nối tri thức

Giải Chuyên đề Toán 11 Bài 9: Đường đi Euler và đường đi Hamilton - Kết nối tri thức

Bài 2.12 trang 45 Chuyên đề Toán 11: a) Giả sử G là một đồ thị với n đỉnh và $\frac{\left(n-1\right)\left(n-2\right)}{2}+2$ cạnh. Sử dụng Định lí Ore, hãy chứng minh G có một chu trình Hamilton.

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

Lời giải:

Nội dung đang cập nhập...

Lời giải bài tập Chuyên đề Toán 11 Bài 9: Đường đi Euler và đường đi Hamilton hay, chi tiết khác:

• Mở đầu trang 41 Chuyên đề Toán 11: Trong lí thuyết đồ thị, bài toán Bảy câu cầu ở Königsberg (nay là thành phố Kaliningrad, nước Nga) ....

• HĐ1 trang 41 Chuyên đề Toán 11: Hãy thử vẽ mỗi hình trên Hình 2.16 bằng một nét liền ....

• Luyện tập 1 trang 41 Chuyên đề Toán 11: Đồ thị nào dưới đây có một đường đi Euler? Hãy chỉ ra một đường đi Euler của nó ....

• HĐ2 trang 43 Chuyên đề Toán 11: Nhận biết đường đi Hamilton Có 5 thành phố du lịch A, B, C, D, E và các con đường nối các thành phố này như Hình 2.20 ....

• Luyện tập 2 trang 44 Chuyên đề Toán 11: Đồ thị nào trong Hình 2.2.3 có đường đi Hamilton? Hãy chỉ ra một đường đi Hamiton của nó ....

• Bài 2.7 trang 44 Chuyên đề Toán 11: Mỗi đồ thị sau có một chu trình Euler hoặc một chu trình Hamilton hay không? Hãy vẽ một chu trình Euler ....

• Bài 2.8 trang 44 Chuyên đề Toán 11: Có thể nào đi dạo chơi qua các cây cầu trong Hình 2.25, mỗi cây cầu vừa đúng một lần? ....

• Bài 2.9 trang 44 Chuyên đề Toán 11: Cho đồ thị G như Hình 2.26. Tìm một chu trình Hamilton xuất phát từ đỉnh S của G ....

• Bài 2.10 trang 44 Chuyên đề Toán 11: Cho đồ thị G như Hình 27. Tìm một đường đi Hamilton từ S đến R ....

• Bài 2.11 trang 45 Chuyên đề Toán 11: 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ị G không nhỏ hơn ....

• Bài 2.13 trang 45 Chuyên đề Toán 11: Với giá trị nào của n thì đồ thị đầy đủ Kn có một chu trình Euler? Có một đường đi Euler? ....

• Bài 2.14 trang 45 Chuyên đề Toán 11: Với giá trị nào của n thì đồ thị đầy đủ K_n có một chu trình Hamilton? Có một đường đi Hamilton? ....