Câu hỏi:

13/07/2024 1,418

Tìm bậc của mỗi đỉnh và chỉ ra một chu trình Hamilton (nếu có) của đồ thị ở Hình 21.

Tìm bậc của mỗi đỉnh và chỉ ra một chu trình Hamilton (nếu có) của đồ thị ở Hình 21. (ảnh 1)

Quảng cáo

Trả lời:

verified
Giải bởi Vietjack

Ta có: d(A) = 3, d(B) = 3, d(C) = 4, d(D) = 4, d(E) = 2.

Vì đồ thị ở Hình 21 gồm có 5 đỉnh nên tổng bậc của hai đỉnh không kề nhau bất kì đều không nhỏ hơn 5. Do đó, theo định lí Ore, đồ thị này có ít nhất một chu trình Hamilton.

Một chu trình Hamilton của đồ thị này là ABCEDA.

CÂU HỎI HOT CÙNG CHỦ ĐỀ

Lời giải

+) Ví dụ về đồ thị liên thông:

Cho ví dụ về một đồ thị liên thông và một đồ thị không liên thông.  (ảnh 1)

Ở hình trên, hai đỉnh bất kì của đồ thị đều được nối với nhau bằng một đường đi. Vậy đồ thị đó là đồ thị liên thông.

+) Ví dụ về đồ thị không liên thông:

Cho ví dụ về một đồ thị liên thông và một đồ thị không liên thông.  (ảnh 2)

Ở hình trên, mỗi đỉnh thuộc khối bên trên đều không thể nối được với mỗi đỉnh thuộc khối bên dưới bằng một đường đi. Vậy đồ thị đó là đồ thị không liên thông.

Lời giải

Gọi 6 người bất kì là A, B, C, D, E, G.

Trong 6 người đó ta chọn ra một người A.Trong 5 người còn lại ta chia thành 2 nhóm:

- Nhóm 1 gồm những người quen A.

- Nhóm 2 gồm những người không quen A.

Có 5 người mà chỉ có 2 nhóm. Do đó, tồn tại ít nhất 3 người thuộc cùng một nhóm. Tức là tồn tại ít nhất 3 người quen A hoặc tồn tại ít nhất 3 người không quen A.

- Nếu tồn tại ít nhất 3 người quen A. Gọi 3 người đó là B, C, D:

+ Nếu trong 3 người B, C, D có 2 người nào đó quen nhau. Giả sử 2 người đó là B và C thì ta có 3 người A, B, C là 3 người đôi một quen nhau.

+ Nếu trong 3 người B, C, D không có 2 người nào đó quen nhau thì 3 người B, C, D là 3 người đôi một không quen nhau.

- Nếu tồn tại 3 người không quen A. Giả sử 3 người đó là D, E, G:

+ Trong 3 người D, E, G nếu có 2 người nào đó không quen nhau. Giả sử 2 người đó là D và E thì 3 người A, D, E là 3 người đôi một không quen nhau.

+ Nếu trong 3 người D, E, G không có 2 người nào không quen nhau thì 3 người D, E, G là 3 người đôi một quen nhau.

Vậy trong 6 người bất kì luôn tồn tại 3 người đôi một quen nhau hoặc 3 người đôi một không quen nhau (đpcm).

Lời giải

Bạn cần đăng ký gói VIP ( giá chỉ từ 199K ) để làm bài, xem đáp án và lời giải chi tiết không giới hạn.

Nâng cấp VIP

Lời giải

Bạn cần đăng ký gói VIP ( giá chỉ từ 199K ) để làm bài, xem đáp án và lời giải chi tiết không giới hạn.

Nâng cấp VIP

Lời giải

Bạn cần đăng ký gói VIP ( giá chỉ từ 199K ) để làm bài, xem đáp án và lời giải chi tiết không giới hạn.

Nâng cấp VIP

Lời giải

Bạn cần đăng ký gói VIP ( giá chỉ từ 199K ) để làm bài, xem đáp án và lời giải chi tiết không giới hạn.

Nâng cấp VIP

Lời giải

Bạn cần đăng ký gói VIP ( giá chỉ từ 199K ) để làm bài, xem đáp án và lời giải chi tiết không giới hạn.

Nâng cấp VIP