Câu hỏi:

13/07/2024 11,993

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?

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Ủ ĐỀ

Lời giải

a) Đồ thị G:

Ta có d(A) = d(B) = d(C) = d(D) = d(E) = 4.

Vậy đồ thị G có chu trình Euler vì các đỉnh của đồ thị G đều có bậc chẵn.

Chẳng hạn, bắt đầu từ đỉnh A, ta có thể đi theo chu trình Euler: ABECAEDCBDA.

b) Đồ thị H:

Ta có d(A) = d(D) = 4; d(B) = d(C) = 3; d(E) = 2.

Vậy đồ thị H không có chu trình Euler vì hai đỉnh B, C có bậc lẻ.

Lời giải

Một đường đi Euler (từ A đến D) trên đồ thị G là: ACBDAD.

Một đường đi Euler (từ E đến F) trên đồ thị H là: EABFCDEF.

Đồ thị G có: d(A) = 3; d(B) = 2; d(C) = 2; d(D) = 3. Suy ra đồ thị G có hai đỉnh bậc lẻ là A, D.

Đồ thị H có: d(A) = 2; d(B) = 2; d(C) = 2; d(D) = 2; d(E) = 3; d(F) = 3. Suy ra đồ thị H có hai đỉnh bậc lẻ là E, F.

Vậy đồ thị G có 2 đỉnh bậc lẻ, đồ thị H có 2 đỉnh bậc lẻ.

Lời giải

Bạn cần đăng ký gói VIP ( giá chỉ từ 199K ) để làm bài, xem đáp án và lời giải chi tiết không giới hạn.

Nâng cấp VIP

Lời giải

Bạn cần đăng ký gói VIP ( giá chỉ từ 199K ) để làm bài, xem đáp án và lời giải chi tiết không giới hạn.

Nâng cấp VIP

Lời giải

Bạn cần đăng ký gói VIP ( giá chỉ từ 199K ) để làm bài, xem đáp án và lời giải chi tiết không giới hạn.

Nâng cấp VIP