Câu hỏi:
13/07/2024 857Sách mới 2k7: 30 đề đánh giá năng lực DHQG Hà Nội, Tp. Hồ Chí Minh, BKHN 2025 mới nhất (600 trang - chỉ từ 140k).
Quả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}\)”.
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:
Câu 7:
về câu hỏi!