Chuyên đề Toán 11 CTST Bài 2. Đường đi Euler và đường đi Hamilton có đáp án
16 câu hỏ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?
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ẽ.
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.
a) Nếu coi mỗi vùng đất của thành phố Königsberg là một đỉnh, mỗi cây cầu là một cạnh nối hai đỉnh thì ta được một đồ thị G như Hình 1.
Câu hỏi của người dân thành phố trở thành: có hay không cách vẽ bằng một nét bút liền (không nhấc bút) đi qua tất cả các cạnh của đồ thị, mỗi cạnh đúng một lần, sao cho điểm kết thúc trùng với điểm xuất phát?
Hãy thử vẽ và đưa ra dự đoán của mình.
b) Nếu không có cây cầu nối giữa A và D nhưng có thêm một cây cầu nối B và C thì ta có đồ thị H như Hình 2. Có thể vẽ một nét liền đi qua tất cả các cạnh của đồ thị này, mỗi cạnh đúng một lần không?
a) Sau khi thử vẽ, ta dự đoán: không có cách vẽ bằng một nét bút liền (không nhấc bút) đi qua tất cả các cạnh của đồ thị, mỗi cạnh đúng một lần, sao cho điểm kết thúc trùng với điểm xuất phát.
b) Ta có thể vẽ một nét liền đi qua tất cả các cạnh của đồ thị này, mỗi cạnh đúng một lần bằng cách lần lượt vẽ các cạnh m, s, r, n, CB, BD, DC.
Chú ý: Ta có thể bắt đầu vẽ từ đỉnh khác và có thể thay đổi thứ tự các cạnh (đường cong) trong khi vẽ miễn là cách vẽ đó thỏa mãn yêu cầu bài toán.
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?
a) Một chu trình Euler của đồ thị G là: AB, a, b, BC, CD, DE, EA.
Ta có d(A) = 2; d(B) = 4; d(C) = 2; d(D) = 2; d(E) = 4.
Vậy đồ thị đã cho không có đỉnh nào là đỉnh bậc lẻ.
b) Đồ thị S không có chu trình Euler vì nếu một đường đi bắt đầu và kết thúc tại cùng một đỉnh thì cạnh CD bắt buộc phải đi qua ít nhất hai lần; nếu một đường đi bắt đầu tại đỉnh này và kết thúc tại đỉnh kia thì không được gọi là chu trình.
Tương tự như vậy, đồ thị T không có chu trình Euler.
Đồ thị S có: d(A) = 2; d(B) = 2; d(C) = 3; d(D) = 1. Suy ra đồ thị S có hai đỉnh bậc lẻ là C, D.
Đồ thị T có: d(A) = 3; d(B) = 2; d(C) = 3; d(D) = 2. Suy ra đồ thị T có hai đỉnh bậc lẻ là A, C.
Vậy cả hai đồ thị S và T đều có đỉnh bậc lẻ.
Hãy chỉ ra một đường đi Euler trên mỗi đồ thị sau. Mỗi đồ thị có bao nhiêu đỉnh bậc lẻ?
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ẻ.
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.
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ẻ.
Đồ thị sau có đường đi Euler không? Nếu có, hãy chỉ ra một đường đi như vậy.
Ta có d(A) = d(B) = d(C) = d(D) = 4 và d(E) = d(F) = 3.
Suy ra đồ thị H có đúng 2 đỉnh bậc lẻ là E, F.
Do đó đồ thị H có đường đi Euler.
Chẳng hạn, bắt đầu từ đỉnh E, ta có thể đi theo đường đi Euler: EAabADcdDFCBEF.
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 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.
Đồ thị ở Hình 15b biểu diễn các điểm vui chơi trong một công viên với những con đường nối giữa chúng như Hình 15a. Có thể đi theo những con đường này để thăm tất cả các điểm vui chơi mỗi điểm đúng một lần hay không? Nếu có, chỉ ra ít nhất một đường đi như vậy.
Ta có thể đi theo những con đường này để thăm tất cả các điểm vui chơi mỗi điểm đúng một lần.
Chẳng hạn, ta có thể đi theo một số đường đi như sau: ANMBCPD, NBMADPC, DANMBCP,…
Hãy chỉ ra rằng mỗi đồ thị sau đây có chu trình Hamilton.
⦁ Hình 21a:
Đồ thị ở Hình 21a có các đỉnh A, F có bậc 2.
Suy ra chu trình Hamilton h (nếu có) phải đi qua các cạnh AB, AD, FD, FC trong đồ thị ở Hình 21a.
Do đó h không thể đi qua các cạnh BD, DC.
Nếu xóa đi hai cạnh này thì đỉnh B, C trở thành có bậc 2.
Vì vậy h phải đi qua cạnh BC.
Khi đó ta được chu trình Hamilton h: ADFCBA.
⦁ Hình 21b:
Đồ thị ở Hình 21b có các đỉnh F, I có bậc 2.
Suy ra chu trình Hamilton h (nếu có) phải đi qua các cạnh FE, FB, IA, IC.
Do đó ta được chu trình Hamilton h: AICBFEDA (hoặc AICDEFBA).
Vậy cả hai đồ thị đã cho đều có chu trình Hamilton.
Học thông minh hơn mỗi ngày
Xem toàn bộ 16 câu hỏi và nhiều hơn nữa với tài khoản miễn phí
Các đỉnh của đồ thị ở Hình 22 biểu thị các điểm du lịch trong một thành phố, các cạnh biểu thị đường đi giữa các điểm du lịch này. Có hay không một cách đi tham quan tất cả các điểm du lịch của thành phố, mỗi điểm qua đúng một lần, xuất phát và kết thúc tại cùng một điểm du lịch?
Đồ thị ở Hình 22 có các đỉnh B, K có bậc 2.
Suy ra chu trình Hamilton h (nếu có) phải đi các các cạnh AB, BC, AK, KI.
Do đó h không thể đi qua các cạnh AI, AD, AD, AE.
Nếu xóa đi bốn cạnh trên thì các đỉnh A, D trở thành bậc 2.
Suy ra h phải đi qua các cạnh AB, AK, DC, DF.
Do đó h không thể đi qua các cạnh CE, CF.
Nếu xóa đi thêm hai cạnh trên thì đỉnh E trở thành bậc 2.
Suy ra h phải đi qua các cạnh EI, EF.
Vì vậy ta được chu trình Hamilton h: ABCDFEIKA.
Vậy có cách đi tham quan tất cả các điểm du lịch của thành phố, mỗi điểm qua đúng một lần, xuất phát và kết thúc tại cùng một điểm du lịch.
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.
⦁ Đồ thị G:
Ta có d(A) = d(B) = d(C) = d(D) = 4.
Suy ra đồ thị G có tất cả các đỉnh đều có bậc chẵn.
Vậy đồ thị G có chu trình Euler.
Chẳng hạn, ta có chu trình Euler: AabACDBcdBA.
⦁ Đồ thị H:
Ta có d(A) = d(B) = d(E) = 4; d(C) = d(D) = 3.
Suy ra đồ thị H có hai đỉnh C, D có bậc lẻ.
Vậy đồ thị H không có chu trình Euler.
Đồ thị ở Hình 24 có đường đi Euler không? Nếu có hãy chỉ ra một đường đi như vậy.
Ta có d(A) = 1; d(B) = d(C) = 3; d(D) = d(F) = 2; d(E) = 5.
Đồ thị H có 3 đỉnh có bậc lẻ nên không có đường đi Euler.
Chỉ ra một chu trình Hamilton của đồ thị ở Hình 25.
Một số chu trình Hamilton của đồ thị G là: BADECB, BECDAB, ADECBA,…
Chú ý: Đồ thị G có thể có các chu trình Hamilton khác bắt đầu từ một trong các đỉnh còn lại.
Chỉ ra một đường đi Hamilton của đồ thị ở Hình 26.
Một số đường đi Hamilton của đồ thị H là: EDQCFBNMAP, EAPBNMDQCF, FBPAEDMNCQ,…
Chú ý: Đồ thị H có thể có các đường đi Hamilton khác.
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.
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.
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.
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.
Bạn có thích hoạt động này không?
Hãy lưu hoặc chia sẻ nội dung này đến mọi người.
Gợi ý cho bạn
Ý tưởng của bạn, bài học của bạn
Tự thiết kế đề thi, bài giảng hoặc flashcard theo cách riêng.
![[Năm 2022] Đề thi thử môn Vật lí THPT Quốc gia có lời giải - Đề số 21](/_next/image?url=https%3A%2F%2Fvideo.vietjack.com%2Fupload%2Fimages%2Fvj-image%2Fimage-3izficdefgfoel0s9j8s-1786772791.jpg&w=3840&q=75)
