Giải bài tập 2.11 trang 45 chuyên đề Toán 11 Kết nối

2.11. 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}$".


Điều kiện bậc của mỗi đỉnh của đồ thị G không nhỏ hơn $\frac{n}{2}$ thì đồ thị G có một chu trình Hamilton.

Điều kiện bậc của mỗi đỉnh của đồ thị G không nhỏ hơn $\frac{n-1}{2}$ thì đồ thị G có một đường đi Hamilton.

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 của đồ thị G không nhỏ hơn $\frac{n-1}{2}$ thì đồ thị sẽ chỉ có đường đi Hamilton.

Tuy nhiên ta có ví dụ:

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}__alt__quot;.

 

Ta thấy bậc của mỗi đỉnh thỏa mãn điều kiện bậc của mỗi đỉnh của đồ thị G không nhỏ hơn $\frac{n-1}{2}$.

Nhưng đồ thị trên có một chu trình Hamilton, ví dụ ABCFDEA. Do đó, đồ thị thỏa mãn điều kiện bậc của mỗi đỉnh của đồ thị G không nhỏ hơn $\frac{n}{2}$.

Vậy đ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}$".


Bình luận

Giải bài tập những môn khác