Đề bài

Chứng minh rằng đồ thị G ở Hình 19 có ít nhất một chu trình Hamilton.

Phương pháp giải

Trong đồ thị, một đường đi được gọi là đường đi Hamilton nếu đường đi đó đi qua tất cả các đinht của đồ thị, mỗi đỉnh đúng 1 lần.

Nếu chu trình là đường đi Hamilton thì chu trình đó được gọi là chu trình Hamilton.

Lời giải của GV Loigiaihay.com

Đồ thị G ở Hình 19 gồm 6 đỉnh, trong đó các đỉnh A, D, E có bậc 4, các đỉnh B, C có bậc 5 và đỉnh F có bậc 2 nên tổng bậc của hai đỉnh không kề nhau bất kì đều không nhỏ hơn 6. Do đó, theo định lí Ore, đồ thị G có ít nhất một chu trình Hamilton.

Xem thêm : Chuyên đề học tập Toán 11 - Cánh diều

Báo lỗi - Góp ý

BÌNH LUẬN

Danh sách bình luận

Đang tải bình luận...

Các bài tập cùng chuyên đề

Bài 1 :

Một người đưa thư xuất phát từ vị trí A, các điểm cần phát thư nằm dọc con đường đi qua. Biết rằng người này phải đi trên mỗi con đường ít nhất một lần (để phát được thư cho tất cả các điểm cần phát nằm dọc theo con đường đó) và cuối cùng quay lại điểm xuất phát. Độ dài các con đường như hình vẽ (đơn vị độ dài). Hỏi tổng quãng đường người đưa thư có thể đi ngắn nhất có thể là bao nhiêu?

Xem lời giải >>

Bài 2 :

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) được phát biểu như sau: Thành phố có 7 cây cầu bắc qua sông như Hình 2.15a dưới đây, có thể nào đi dạo qua khắp các cây cầu nhưng mỗi cầu chỉ đi qua một lần không?

Nếu ta coi mỗi khu vực A, B, C, D của thành phố là một đỉnh, mỗi cầu qua lại hai khu vực như một cạnh nối hai đỉnh, thì bản đồ thành phố Königsberg là một đa đồ thị như Hình 2.15b. Vấn đề đặt ra chính là: Có thể vẽ được Hình 2.15b bằng một nét liền hay không?

Xem lời giải >>

Bài 3 :

Đồ thị nào dưới đây có một đường đi Euler? Hãy chỉ ra một đường đi Euler của nó.

Xem lời giải >>

Bài 4 :

Đồ thị nào dưới đây có một đường đi Euler? Hãy chỉ ra một đường đi Euler của nó.

Xem lời giải >>

Bài 5 :

Hãy thử vẽ mỗi hình trên Hình 2.16 bằng một nét liền.

Xem lời giải >>

Bài 6 :

Đồ 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ó.

Xem lời giải >>

Bài 7 :

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. Hãy chỉ ra một cách để đi tham quan cả 5 thành phố đó, mà không cần đến địa điểm nào quá một lần.

Xem lời giải >>

Bài 8 :

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 hoặc một chu trình Hamilton khi có thể.

Xem lời giải >>

Bài 9 :

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?

Xem lời giải >>

Bài 10 :

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.

Xem lời giải >>

Bài 11 :

Cho đồ thị G như Hình 27. Tìm một đường đi Hamilton từ S đến R.

Xem lời giải >>

Bài 12 :

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 \(\frac{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 \(\frac{{n - 1}}{2}\)”.

Xem lời giải >>

Bài 13 :

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.

Xem lời giải >>

Bài 14 :

Với giá trị nào của n thì đồ thị đầy đủ K_n có một chu trình Euler? Có một đường đi Euler?

Xem lời giải >>

Bài 15 :

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?

Xem lời giải >>

Bài 16 :

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

Xem lời giải >>

Bài 17 :

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

Xem lời giải >>

Bài 18 :

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.

Xem lời giải >>

Bài 19 :

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

Xem lời giải >>

Bài 20 :

Chứng minh rằng đồ thị G ở Hình 17 có ít nhất một chu trình Hamilton.

Xem lời giải >>

Bài 21 :

Tìm hai đường đi Hamilton bắt đầu từ đỉnh E của đồ thị trong Hình 15.

Xem lời giải >>

Bài 22 :

Quan sát đường đi màu đỏ trên đồ thị ở Hình 13 và cho biết đường đi đó có đi qua tất cả các đỉnh của đồ thị hay không và mỗi đỉnh đi qua bao nhiêu lần.

Xem lời giải >>

Bài 23 :

Chứng minh rằng đồ thị ở Hình 11a không có chu trình Euler.

Xem lời giải >>

Bài 24 :

Hãy chỉ ra hai đường đi Euler trong đồ thị ở Hình 11a.

Xem lời giải >>

Bài 25 :

Tìm bậc của mỗi đỉnh và chỉ ra một chu trình Euler (nếu có) của đồ thị ở Hình 20.

Xem lời giải >>

Bài 26 :

Tìm bậc của mỗi đỉnh và chỉ ra một chu trình Hamilton (nếu có) của đồ thị ở Hình 21.

Xem lời giải >>

Bài 27 :

Một cuộc họp có 6 người tham dự. Hai người bất kì trong họ hoặc quen nhau hoặc không quen nhau. Chứng minh rằng có 3 người trong 6 người đó đôi một quen nhau hoặc đôi một không quen nhau.

Xem lời giải >>

Bài 28 :

Thành phố Königsberg thuộc Phổ (nay là Kaliningrad thuộc Nga) có bảy cây cầu nối bốn vùng đất được chia bởi các nhánh sông Pregel như hình dưới.

Vào mỗi sáng Chủ nhật, người dân thành phố thường đi dạo qua các cây cầu. Họ tự hỏi không biết có thể bắt đầu từ một điểm nào đó trong thành phố, đi qua khắp các cây cầu, mỗi cầu chỉ đi qua một lần, rồi quay về điểm xuất phát.

Theo em, có hay không một cách đi như vậy?

Xem lời giải >>

Bài 29 :

Hãy giải đáp câu hỏi của người dân Königsberg ở Hoạt động khởi động (còn gọi là bài toán Bảy cây cầu).

Thành phố Königsberg thuộc Phổ (nay là Kaliningrad thuộc Nga) có bảy cây cầu nối bốn vùng đất được chia bởi các nhánh sông Pregel như hình dưới.

Vào mỗi sáng Chủ nhật, người dân thành phố thường đi dạo qua các cây cầu. Họ tự hỏi không biết có thể bắt đầu từ một điểm nào đó trong thành phố, đi qua khắp các cây cầu, mỗi cầu chỉ đi qua một lần, rồi quay về điểm xuất phát.

Xem lời giải >>

Bài 30 :

Đồ thị sau có đường đi Euler không? Nếu có, hãy chỉ ra một đường đi như vậy.

Xem lời giải >>