Câu hỏi:

12/07/2024 648

Chứng minh rằng đồ thị G ở Hình 17 có ít nhất một chu trình Hamilton.

Chứng minh rằng đồ thị G ở Hình 17 có ít nhất một chu trình Hamilton.    (ảnh 1)

Quảng cáo

Trả lời:

verified
Giải bởi Vietjack

Ta có: d(A) = 3, d(B) = 4, d(C) = 3, d(E) = 3, d(F) = 3. Đồ thị G ở Hình 17 gồm 5 đỉnh, mỗi đỉnh của đồ thị đều có bậc không nhỏ hơn 52. Do đó, theo định lí Dirac, đồ thị G có ít nhất một chu trình Hamilton.

Bình luận


Bình luận

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

Câu 1:

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

Xem đáp án » 13/07/2024 4,593

Câu 2:

Một cuộc họp có 6 người tham dự. Hai người bất kì trong họ hoặc quen nhau hoặc không quen nhau. Chứng minh rằng có 3 người trong 6 người đó đôi một quen nhau hoặc đôi một không quen nhau.

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

Câu 3:

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

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

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

Câu 4:

Có sáu thành phố A, B, C, D, E, G sao cho hai thành phố bất kì trong chúng đều có đường nối với nhau. Sử dụng đồ thị để mô tả tình huống đó. 

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

Câu 5:

Cho hai ví dụ về đồ thị đơn.

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

Câu 6:

Có năm thành phố A, B, C, D, E sao cho hai thành phố bất kì trong chúng đều có đúng một đường nối với nhau. Sử dụng đồ thị để mô tả tình huống đó. 

Xem đáp án » 11/07/2024 1,612

Câu 7:

Có bao nhiêu đỉnh bậc lẻ trong đồ thị ở Hình 5a?

Có bao nhiêu đỉnh bậc lẻ trong đồ thị ở Hình 5a?   (ảnh 1)

Xem đáp án » 11/07/2024 1,523
Vietjack official store
Đăng ký gói thi VIP

VIP +1 - Luyện thi tất cả các đề có trên Website trong 1 tháng

  • Được thi tất cả các đề của các lớp có trên Khoahoc.vietjack.com
  • Ngân hàng câu hỏi trắc nghiệm theo các mức độ Nhận biết, Thông hiểu, Vận dụng, Vận dụng cao.
  • Luyện chuyên sâu, rèn tốc độ với trọn bộ đề thi thử, đề minh họa, chính thức các năm.
  • Hỏi bài tập với đội ngũ chuyên môn cao của chúng tôi.

Đặt mua

VIP +3 - Luyện thi tất cả các đề có trên Website trong 3 tháng

  • Được thi tất cả các đề của các lớp có trên Khoahoc.vietjack.com
  • Ngân hàng câu hỏi trắc nghiệm theo các mức độ Nhận biết, Thông hiểu, Vận dụng, Vận dụng cao.
  • Luyện chuyên sâu, rèn tốc độ với trọn bộ đề thi thử, đề minh họa, chính thức các năm.
  • Hỏi bài tập với đội ngũ chuyên môn cao của chúng tôi.

Đặt mua

VIP +6 - Luyện thi tất cả các đề có trên Website trong 6 tháng

  • Được thi tất cả các đề của các lớp có trên Khoahoc.vietjack.com
  • Ngân hàng câu hỏi trắc nghiệm theo các mức độ Nhận biết, Thông hiểu, Vận dụng, Vận dụng cao.
  • Luyện chuyên sâu, rèn tốc độ với trọn bộ đề thi thử, đề minh họa, chính thức các năm.
  • Hỏi bài tập với đội ngũ chuyên môn cao của chúng tôi.

Đặt mua

VIP +12 - Luyện thi tất cả các đề có trên Website trong 12 tháng

  • Siêu tiết kiệm - Được thi tất cả các đề của các lớp có trên Khoahoc.vietjack.com
  • Ngân hàng câu hỏi trắc nghiệm theo các mức độ Nhận biết, Thông hiểu, Vận dụng, Vận dụng cao.
  • Luyện chuyên sâu, rèn tốc độ với trọn bộ đề thi thử, đề minh họa, chính thức các năm.
  • Hỏi bài tập với đội ngũ chuyên môn cao của chúng tôi.

Đặt mua