Câu hỏi:

13/07/2024 1,664

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?

Sách mới 2k7: Bộ 20 đề minh họa Toán, Lí, Hóa, Văn, Sử, Địa…. form chuẩn 2025 của Bộ giáo dục (chỉ từ 49k/cuốn).

Đề toán-lý-hóa Đề văn-sử-địa Tiếng anh & các môn khác

Quảng cáo

Trả lời:

verified
Giải bởi Vietjack

Lời giải:

Đồ thị đầy đủ Kn có n ≥ 2, n ℕ.

Đồ thị đầy đủ Kn là đồ thị liên thông.

Mỗi đỉnh của Kn đều có bậc là n – 1.

+) Theo định lí Euler, K có chu trình Euler khi Kn liên thông (đã thỏa mãn) và mọi đỉnh của Kn đều có bậc chẵn, điều này có nghĩa để K có một chu trình Euler thì n – 1 phải là số chẵn hay n phải là số lẻ, tức là n = 2k + 1 (k *). Vậy với n = 2k + 1 (k *) thì đồ thị đầy đủ Kn có một chu trình Euler.

+) Đồ thị Kn có một đường đi Euler từ A đến B khi và chỉ khi Kn liên thông và mọi đỉnh của Kn đều có bậc chẵn, chỉ trừ A và B có bậc lẻ. Mà mọi đỉnh của Kn đều có bậc là n – 1, nghĩa là mọi đỉnh của Kn đều có bậc chẵn hoặc đều có bậc lẻ.

- Với n = 2, ta có K2 có 2 đỉnh đều có bậc là 1 (là bậc lẻ) nên ta có đường đi Euler từ đỉnh này qua đỉnh còn lại.

- Với n > 2, n * thì mọi đỉnh của Kn đều có bậc cùng chẵn hoặc cùng lẻ lớn hơn 2, do đó không thỏa mãn điều kiện để Kn có đường đi Euler.

Vậy đồ thị đầy đủ Kcó một đường đi Euler khi n = 2.

Bình luận


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ể.
Media VietJack

Xem đáp án » 13/07/2024 3,666

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ó.
Media VietJack

Xem đáp án » 13/07/2024 2,939

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ó.
Media VietJack

Xem đáp án » 13/07/2024 2,766

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.
Media VietJack

Xem đáp án » 13/07/2024 2,089

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.
Media VietJack

Xem đáp án » 13/07/2024 1,824

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,640