Quảng cáo
Trả lời:
Giải bởi Vietjack
Lời giải:
Bằng cách loaị bỏ tất cả các chi tiết ngoại trừ các vùng đất và các cây cầu, sau đó thay thế mỗi vùng đất bằng một điểm và thay thế mỗi câu cầu nối hai vùng đất bằng một đoạn nối hai điểm, ta nhận được một đồ thị G có 6 đỉnh (tương ứng 6 vùng đất) và có 15 cạnh (tương ứng 15 cây cầu) như hình vẽ trên.
Ta thấy đồ thị G liên thông và đỉnh A có bậc 4, đỉnh B có bậc 3, đỉnh C có bậc 5, đỉnh D có bậc 8, đỉnh E có bậc 4, đỉnh F có bậc 6 hay mọi đỉnh của G đều có bậc chẵn, chỉ trừ B và C có bậc lẻ, do đó theo Định lí 2, ta suy ra đồ thị G có một đường đi Euler từ A đến B. Chẳng hạn, một đường đi Euler của đồ thị G là BAFCDADFDEFECDBC.
Vậy có thể đi dạo chơi qua các cây cầu trong Hình 2.25, mỗi cây cầu vừa đúng một lần.
Đăng nhập để xem lời giải
Lưu tiến độ và luyện tập hiệu quả hơn. Hoàn toàn miễn phí!
Đang tải chế độ Học...
Dành cho bạn Hot
CÂU HỎI HOT CÙNG CHỦ ĐỀ
Đăng nhập để xem lời giải
Lưu tiến độ và luyện tập hiệu quả hơn. Hoàn toàn miễn phí!
Lời giải
Lời giải:
+) Đồ thị Hình 2.24 a) có các đỉnh đều có bậc là 3 nên theo định lí Euler đồ thị này không có chu trình Euler.
Lại có đồ thị a) có 4 đỉnh, tổng số bậc của hai đỉnh không kề nhau luôn không nhỏ hơn 4 nên theo định lí Ore, đồ thị a) có một chu trình Hamilton.
Một chu trình Hamiltol của đồ thị a) là ABCDA.
+) Đồ thị Hình 2.24 b) liên thông và có các đỉnh đều có bậc chẵn (ở đây là bậc 4) nên theo định lí Euler, đồ thị này có một chu trình Euler. Một chu trình Euler của đồ thị này là ABCDEADBECA.
Lại có đồ thị b) có 5 đỉnh, tổng số bậc của hai đỉnh không kề nhau luôn không nhỏ hơn 5 nên theo định lí Ore, đồ thị b) có một chu trình Hamilton.
Một chu trình Halminton của đồ thị này là ABCDEA.
+) Đồ thị Hình 2.24 c) có các đỉnh đều có bậc là 3 nên theo định lí Euler đồ thị này không có chu trình Euler.
Lại có đồ thị c) có 8 đỉnh, mặc dù đồ thị này không thỏa mãn cả 2 định lí Ore và Dirac nhưng đồ thị vẫn có một chu trình Hamilton.
Một chu trình Hamiltol của đồ thị c) là ABCDHGFEA.
+) Đồ thị Hình 2.24 d) có đỉnh A và B là đỉnh bậc 3, nên theo định lí Euler đồ thị này không có chu trình Euler. Đồ thị d) này cũng không có chu trình Hamilton.
Đăng nhập để xem lời giải
Lưu tiến độ và luyện tập hiệu quả hơn. Hoàn toàn miễn phí!
Lời giải
Lời giải:
- Đồ thị Hình 2.19a có đường đi Euler từ A đến B vì đồ thị này liên thông và các đỉnh A, B có bậc 3 (bậc lẻ), còn các đỉnh C, D, E đều có bậc 2 (bậc chẵn). Một đường đi Euler của đồ thị này là ACBDAEB.
- Đồ thị Hình 2.19b không có đường đi Euler vì đồ thị này có bốn đỉnh bậc lẻ (ở đây là bậc bằng 3).
Đăng nhập để xem lời giải
Lưu tiến độ và luyện tập hiệu quả hơn. Hoàn toàn miễn phí!
Lời giải
Bạn cần đăng ký gói VIP ( giá chỉ từ 250K ) để làm bài, xem đáp án và lời giải chi tiết không giới hạn.
Đăng nhập để xem lời giải
Lưu tiến độ và luyện tập hiệu quả hơn. Hoàn toàn miễn phí!
Lời giải
Bạn cần đăng ký gói VIP ( giá chỉ từ 250K ) để làm bài, xem đáp án và lời giải chi tiết không giới hạn.
Đăng nhập để xem lời giải
Lưu tiến độ và luyện tập hiệu quả hơn. Hoàn toàn miễn phí!
Lời giải
Bạn cần đăng ký gói VIP ( giá chỉ từ 250K ) để làm bài, xem đáp án và lời giải chi tiết không giới hạn.
Đăng nhập để xem lời giải
Lưu tiến độ và luyện tập hiệu quả hơn. Hoàn toàn miễn phí!
Lời giải
Bạn cần đăng ký gói VIP ( giá chỉ từ 250K ) để làm bài, xem đáp án và lời giải chi tiết không giới hạn.
Đăng nhập để xem lời giải
Lưu tiến độ và luyện tập hiệu quả hơn. Hoàn toàn miễn phí!
Lời giải
Bạn cần đăng ký gói VIP ( giá chỉ từ 250K ) để làm bài, xem đáp án và lời giải chi tiết không giới hạn.
Đăng ký để học cùng Vietjack. Hoàn toàn miễn phí!
Bằng việc đăng ký, bạn đồng ý với Điều khoản sử dụng và Chính sách bảo mật của Vietjack.
Nhắn tin Zalo
Hỏi bài tập