Câu hỏi:

13/07/2024 639

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.

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? (ảnh 1)

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?

Sách mới 2k7: 30 đề đánh giá năng lực DHQG Hà Nội, Tp. Hồ Chí Minh, BKHN 2025 mới nhất (600 trang - chỉ từ 140k).

Mua bộ đề Hà Nội Mua bộ đề Tp. Hồ Chí Minh Mua đề Bách Khoa

Quảng cáo

Trả lời:

verified
Giải bởi Vietjack

Sau bài học này, chúng ta sẽ giải quyết được bài toán trên như sau:

Biểu thị mỗi vùng đất bằng một đỉnh, mỗi cây cầu bằng một cạnh nối hai đỉnh, ta được đồ thị như hình vẽ.

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? (ảnh 2)

Ta thấy d(A) = 5; d(B) = d(C) = d(D) = 3.

Suy ra tất cả các đỉnh của đồ thị trên đều có bậc lẻ.

Do đó đồ thị không có chu trình Euler.

Nói cách khác, không 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.

CÂU HỎI HOT CÙNG CHỦ ĐỀ

Câu 1:

Mỗi đồ thị sau đây có chu trình Euler không? Nếu có, hãy chỉ ra một chu trình như vậy.

Mỗi đồ thị sau đây có chu trình Euler không? Nếu có, hãy chỉ ra một chu trình như vậy. (ảnh 1)

Xem đáp án » 13/07/2024 2,489

Câu 2:

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

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

Xem đáp án » 13/07/2024 995

Câu 3:

a) Chỉ ra một chu trình Euler của đồ thị G ở Hình 5. Đồ thị này có đỉnh nào bậc lẻ không?

a) Chỉ ra một chu trình Euler của đồ thị G ở Hình 5. Đồ thị này có đỉnh nào bậc lẻ không?   b) Chỉ ra rằng các đồ thị S và T sau đây không có chu trình Euler. Các đồ thị này có đỉnh bậc lẻ không?   (ảnh 1)

b) Chỉ ra rằng các đồ thị S và T sau đây không có chu trình Euler. Các đồ thị này có đỉnh bậc lẻ không?

a) Chỉ ra một chu trình Euler của đồ thị G ở Hình 5. Đồ thị này có đỉnh nào bậc lẻ không?   b) Chỉ ra rằng các đồ thị S và T sau đây không có chu trình Euler. Các đồ thị này có đỉnh bậc lẻ không?   (ảnh 2)

Xem đáp án » 11/07/2024 981

Câu 4:

Chỉ ra một chu trình Hamilton của đồ thị ở Hình 25.

Chỉ ra một chu trình Hamilton của đồ thị ở Hình 25.   (ảnh 1)

Xem đáp án » 11/07/2024 962

Câu 5:

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

Đồ thị ở Hình 24 có đường đi Euler không? Nếu có hãy chỉ ra một đường đi như vậy. (ảnh 1)

Xem đáp án » 13/07/2024 954

Câu 6:

Chỉ ra một đường đi Hamilton của đồ thị ở Hình 26.

Chỉ ra một đường đi Hamilton của đồ thị ở Hình 26.   (ảnh 1)

Xem đáp án » 13/07/2024 928

Câu 7:

Mỗi đồ thị trong Hình 23 có chu trình Euler không? Nếu có hãy chỉ ra một chu trình như vậy.

Mỗi đồ thị trong Hình 23 có chu trình Euler không? Nếu có hãy chỉ ra một chu trình như vậy. (ảnh 1)

Xem đáp án » 12/07/2024 840

Bình luận


Bình luận
Đăng ký gói thi VIP

VIP 1 - Luyện thi tất cả các đề có trên Website trong 1 tháng

  • Được thi tất cả các đề của các lớp có trên Khoahoc.vietjack.com
  • Ngân hàng câu hỏi trắc nghiệm theo các mức độ Nhận biết, Thông hiểu, Vận dụng, Vận dụng cao.
  • Luyện chuyên sâu, rèn tốc độ với trọn bộ đề thi thử, đề minh họa, chính thức các năm.
  • Hỏi bài tập với đội ngũ chuyên môn cao của chúng tôi.

Đặt mua

VIP 2 - Luyện thi tất cả các đề có trên Website trong 3 tháng

  • Được thi tất cả các đề của các lớp có trên Khoahoc.vietjack.com
  • Ngân hàng câu hỏi trắc nghiệm theo các mức độ Nhận biết, Thông hiểu, Vận dụng, Vận dụng cao.
  • Luyện chuyên sâu, rèn tốc độ với trọn bộ đề thi thử, đề minh họa, chính thức các năm.
  • Hỏi bài tập với đội ngũ chuyên môn cao của chúng tôi.

Đặt mua

VIP 3 - Luyện thi tất cả các đề có trên Website trong 6 tháng

  • Được thi tất cả các đề của các lớp có trên Khoahoc.vietjack.com
  • Ngân hàng câu hỏi trắc nghiệm theo các mức độ Nhận biết, Thông hiểu, Vận dụng, Vận dụng cao.
  • Luyện chuyên sâu, rèn tốc độ với trọn bộ đề thi thử, đề minh họa, chính thức các năm.
  • Hỏi bài tập với đội ngũ chuyên môn cao của chúng tôi.

Đặt mua

VIP 4 - Luyện thi tất cả các đề có trên Website trong 12 tháng

  • Siêu tiết kiệm - Được thi tất cả các đề của các lớp có trên Khoahoc.vietjack.com
  • Ngân hàng câu hỏi trắc nghiệm theo các mức độ Nhận biết, Thông hiểu, Vận dụng, Vận dụng cao.
  • Luyện chuyên sâu, rèn tốc độ với trọn bộ đề thi thử, đề minh họa, chính thức các năm.
  • Hỏi bài tập với đội ngũ chuyên môn cao của chúng tôi.

Đặt mua

tailieugiaovien.com.vn