Tìm hai đường đi Hamilton bắt đầu từ đỉnh E của đồ thị trong Hình 15.
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.
Quan sát đồ thị Hình 15, ta thấy rằng hai đường đi Hamilton bắt đầu từ đỉnh E của đồ thị này là EACDB và ECDBA.
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?
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?
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ó.
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ó.
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.
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ó.
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.
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ể.
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?
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.
Bài 11 :
Cho đồ thị G như Hình 27. Tìm một đường đi Hamilton từ S đến R.
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}\)”.
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.
Bài 14 :
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 15 :
Với giá trị nào của n thì đồ thị đầy đủ Kn có một chu trình Hamilton? Có một đường đi Hamilton?
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.
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.
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.
Bài 19 :
Tìm một chu trình Euler trong đồ thị trên Hình 2.40.
Bài 20 :
Chứng minh rằng đồ thị G ở Hình 19 có ít nhất một chu trình Hamilton.
Bài 21 :
Chứng minh rằng đồ thị G ở Hình 17 có ít nhất một chu trình Hamilton.
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.
Bài 23 :
Chứng minh rằng đồ thị ở Hình 11a không có chu trình Euler.
Bài 24 :
Hãy chỉ ra hai đường đi Euler trong đồ thị ở Hình 11a.
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.
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.
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.
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?
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.
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.
Danh sách bình luận