Câu hỏi:
13/07/2024 1,838Quảng cáo
Trả lời:
Lời giải:
Cho đơn đồ thị G có 5 đỉnh như hình vẽ sau:
Mỗi đỉnh của đồ thị này đều có bậc là 2 hoặc 3, đều không nhỏ hơn \(\frac{{5 - 1}}{2} = 2\), thỏa mãn điều kiện của định lí Dirac nếu thay điều kiện “bậc của mỗi đỉnh của đồ thị G không nhỏ hơn \(\frac{n}{2}\)” bằng điều kiện “bậc của mỗi đỉnh không nhỏ hơn \(\frac{{n - 1}}{2}\)”.
Định lí Dirac là một điều kiện đủ cho sự tồn tại chu trình Hamilton, nhưng đồ thị trên lại không có chu trình Hamilton. Do vậy, đây vì ví dụ cần đưa ra để 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}\)”.
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
CÂU HỎI HOT CÙNG CHỦ ĐỀ
Câu 1:
Câu 2:
Câu 3:
Câu 4:
Câu 5:
Câu 6:
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