Câu hỏi:
13/07/2024 4,585
Mỗi đồ thị sau có một chu trình Euler hoặc một chu trình Hamilton hay không? Hãy vẽ một chu trình Euler hoặc một chu trình Hamilton khi có thể.
Quảng cáo
Trả lời:
Giải bởi Vietjack
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.
Hot: 500+ Đề thi thử tốt nghiệp THPT các môn, ĐGNL các trường ĐH... file word có đáp án (2025). Tải ngay
Sách thầy cô Vietjack biên soạn:
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
Đã bán 104
₫ 136.000
₫ 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
Đã bán 211
₫ 119.000
₫ 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
Đã bán 1k
₫ 104.000
₫ 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
Đã bán 218
₫ 130.000
₫ 75.000
Bình luận
CÂU HỎI HOT CÙNG CHỦ ĐỀ
Câu 1:
Đồ thị nào dưới đây có một đường đi Euler? Hãy chỉ ra một đường đi Euler của nó.
Xem đáp án »
13/07/2024
3,698
Câu 2:
Đồ thị nào trong Hình 2.2.3 có đường đi Hamilton? Hãy chỉ ra một đường đi Hamiton của nó.
Xem đáp án »
13/07/2024
3,435
Câu 3:
Cho đồ thị G như Hình 2.26. Tìm một chu trình Hamilton xuất phát từ đỉnh S của G.
Xem đáp án »
13/07/2024
2,909
Câu 4:
Có 5 thành phố du lịch A, B, C, D, E và các con đường nối các thành phố này như Hình 2.20. Hãy chỉ ra một cách để đi tham quan cả 5 thành phố đó, mà không cần đến địa điểm nào quá một lần.
Xem đáp án »
13/07/2024
2,849
Câu 5:
Hãy chỉ ra một ví dụ chứng tỏ rằng điều kiện bậc của mỗi đỉnh của đồ thị G không nhỏ hơn \(\frac{n}{2}\) trong Định lí Dirac, không thể thay bằng điều kiện “bậc của mỗi đỉnh không nhỏ hơn \(\frac{{n - 1}}{2}\)”.
Xem đáp án »
13/07/2024
2,018
Câu 6:
Với giá trị nào của n thì đồ thị đầy đủ Kn có một chu trình Euler? Có một đường đi Euler?
Xem đáp án »
13/07/2024
1,875
🔥 Đề thi HOT:
-
10 Bài tập Nhận biết góc phẳng của góc nhị diện và tính góc phẳng nhị diện (có lời giải)
-
Bài tập Hình học không gian lớp 11 cơ bản, nâng cao có lời giải (P11)
-
10 Bài tập Biến cố hợp. Biến cố giao (có lời giải)
-
Bài tập Xác suất ôn thi THPT Quốc gia có lời giải (P1)
-
15 câu Trắc nghiệm Khoảng cách có đáp án (Nhận biết)
-
10 Bài tập Nhận biết góc phẳng của góc nhị diện và tính góc phẳng nhị diện (có lời giải)
-
10 Bài tập Bài toán thực tiễn liên quan đến thể tích (có lời giải)
-
23 câu Trắc nghiệm Xác suất của biến cố có đáp án (Phần 2)
Hãy Đăng nhập hoặc Tạo tài khoản để gửi bình luận
-
-
Bình luận