Câu hỏi:
13/07/2024 5,124Quảng cáo
Trả lờ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ẻ.
Hot: Học hè online Toán, Văn, Anh...lớp 1-12 tại Vietjack với hơn 1 triệu bài tập có đáp án. Học ngay
- Trọng tâm Sử, Địa, GD KTPL 11 cho cả 3 bộ Kết nối, Chân trời, Cánh diều VietJack - Sách 2025 ( 38.000₫ )
- Sách - Sổ tay kiến thức trọng tâm Vật lí 11 VietJack - Sách 2025 theo chương trình mới cho 2k8 ( 45.000₫ )
- Sách lớp 11 - Trọng tâm Toán, Lý, Hóa, Sử, Địa lớp 11 3 bộ sách KNTT, CTST, CD VietJack ( 52.000₫ )
- Sách lớp 10 - Combo Trọng tâm Toán, Văn, Anh và Lí, Hóa, Sinh cho cả 3 bộ KNTT, CD, CTST VietJack ( 75.000₫ )
CÂU HỎI HOT CÙNG CHỦ ĐỀ
Lời giải
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.
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.
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.
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.
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.