Có bốn khu phố A, B, C và D được nối với nhau bằng những cây cầu như Hình 27. 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? Nếu có, hãy chỉ ra một cách đi như vậy.

Quảng cáo
1 câu trả lời 118
Biểu thị mỗi khu phố 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) = d(D) = 4.
Suy ra tất cả các đỉnh của đồ thị trên đều có bậc chẵn.
Do đó đồ thị trên có chu trình Euler.
Vậy nói cách khác, 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.
Chẳng hạn, bắt đầu từ đỉnh A, ta có thể đi theo chu trình Euler: AabADcdDBCA.
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
