Có năm vùng đất A, B, C, D và E được nối với nhau bằng những cây cầu như Hình 28.
a) Có hay không cách đi qua tất cả các cây cầu, mỗi cây cầu chỉ qua một lần, rồi quay trở lại nơi xuất phát?
b) Nếu không yêu cầu quay lại nơi bắt đầu thì có cách đi như vậy không? Nếu có, hãy chỉ ra một cách đi.

Quảng cáo
1 câu trả lời 107
a) 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ẽ.

Ta có d(A) = d(B) = d(C) = 4; d(D) = d(E) = 3.
Suy ra đồ thị trên có đúng hai đỉnh bậc lẻ là D, E.
Do đó đồ thị trên có đường đi Euler nhưng không có chu trình Euler.
Vậy nói cách khác, không có cách đi qua tất cả các cây cầu, mỗi cây cầu chỉ qua một lần, rồi quay trở lại nơi xuất phát.
b) Nếu không yêu cầu quay lại nơi bắt đầu thì có cách đi như vậy (vì đồ thị trên có đường đi Euler).
Chẳng hạn, bắt đầu từ đỉnh A, ta có thể đi theo đường đi Euler: DACDECBabBE.
Quảng cáo
Bạn cần hỏi gì?
Câu hỏi hot cùng chủ đề
-
Đã trả lời bởi chuyên gia
135949 -
Hỏi từ APP VIETJACK
Đã trả lời bởi chuyên gia
76973 -
Đã trả lời bởi chuyên gia
72601 -
Đã trả lời bởi chuyên gia
48019
