Câu hỏi:
12/07/2024 1,413
Với giá trị nào của n thì đồ thị đầy đủ Kn có một chu trình Hamilton? Có một đường đi 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).
Quảng cáo
Trả lời:
Giải bởi Vietjack
Lời giải:
Đồ thị đầy đủ Kn có n ≥ 2, n ∈ ℕ.
+ Với n = 2 ta có K2 không có chu trình Hamilton, nhưng có đường đi Hamilton (đi từ đỉnh này qua đỉnh còn lại).
+ Với n ≥ 3, n ∈ ℕ.
Đồ thị đầy đủ Kn là một đơn đồ thị có n đỉnh và mỗi đỉnh có bậc là n – 1.
- Sử dụng định lí Ore, ta thấy Kn có một chu trình Hamilton khi mỗi cặp đỉnh không kề nhau đều có tổng bậc không nhỏ hơn n, tức là (n – 1) + (n – 1) ≥ n, tương đương với n ≥ 2, kết hợp với điều kiện suy ra n ≥ 3, n ∈ ℕ. (Ta cũng có thể sử dụng định lí Dirac để tìm điều kiện của n)
- Sử dụng Định lí 4 (suy ra từ định lí Dirac), ta thấy Kn có một đường đi Hamilton khi mỗi đỉnh có bậc không nhỏ hơn \(\frac{{n - 1}}{2}\), tức là n – 1 ≥ \(\frac{{n - 1}}{2}\), tương đương với n ≥ 1, kết hợp với điều kiện suy ra n ≥ 3, n ∈ ℕ.
Vậy với n ≥ 3, n ∈ ℕ thì đồ thị đầy đủ Kn có một chu trình Hamilton và với n ≥ 2, n ∈ ℕ thì đồ thị đầy đủ Kn có một đường đi Hamilton.
Nhà sách vietjack
- Trọng tâm Hóa học 11 dùng cho cả 3 bộ sách Kết nối, Cánh diều, Chân trời sáng tạo VietJack - Sách 2025 ( 58.000₫ )
- 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 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₫ )
Bình luận
CÂU HỎI HOT CÙNG CHỦ ĐỀ
Câu 1:
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ể.
Xem đáp án »
13/07/2024
4,099
Câu 2:
Đồ 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,257
Câu 3:
Đồ 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,047
Câu 4:
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,449
Câu 5:
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,220
Câu 6:
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
1,838
Câu 7:
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,767
🔥 Đề thi HOT:
-
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 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 Biến cố hợp. Biến cố giao (có lời giải)
-
38 câu trắc nghiệm Toán 11 Kết nối tri thức Lôgarit có đáp án
-
100 câu trắc nghiệm Đạo hàm cơ bản (P1)
-
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 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)
Hãy Đăng nhập hoặc Tạo tài khoản để gửi bình luận
-
-
Bình luận