Câu hỏi:

11/07/2023 383

Kiểm tra xem các điều kiện của định lí Ore có thỏa mãn với các đồ thị trên Hình 2.39 không.
Media VietJack

Sá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).

Mua bộ đề Hà Nội Mua bộ đề Tp. Hồ Chí Minh Mua đề Bách Khoa

Quảng cáo

Trả lời:

verified
Giải bởi Vietjack

Lời giải:

Ta thấy hai đồ thị ở Hình 2.39 đều là đơn đồ thị và mỗi đồ thị đều có số đỉnh lớn hơn 3.

+) Đối với Hình 2.39 a), đặt tên các đỉnh như hình vẽ:

Media VietJack

Đồ thị này có 5 đỉnh, các đỉnh đều có bậc là 3, trừ đỉnh A có bậc là 4 nên mỗi cặp đỉnh không kề nhau có tổng bậc nhỏ nhất là 6, mà 6 > 5, do đó đồ thị này thỏa mãn định lí Ore. Vậy đồ thị Hình 2.39 a) có một chu trình Hamilton.

+) Đối với Hình 2.39 a), đặt tên các đỉnh như hình vẽ:

Media VietJack

Đồ thị này có 5 đỉnh, đỉnh E và đỉnh B đều có bậc là 3, các đỉnh còn lại đều có bậc là 2 nên mỗi cặp đỉnh không kề nhau có tổng số bậc nhỏ nhất là 4 (chẳng hạn đỉnh A và đỉnh D), do đó đồ thị này không thỏa mãn định lí Ore. Tuy nhiên thì đồ thị này vẫn có chu trình Hamilton, một chu trình Hamilton của đồ thị là ABCDEA.

Do đó, ta khẳng định lại định lí Ore chỉ là một điều kiện đủ cho sự tồn tại của chu trình Hamilton.

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

Câu 1:

Vẽ đồ thị G = (V, E) với các đỉnh và các cạnh như sau:

V = {1; 2; 3; 4; 5; 6; 7; 8} và E = {12; 13; 23; 34; 35; 67; 68; 78}.

Đồ thị này có phải là đơn đồ thị không? Có phải là đồ thị đầy đủ không?

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

Câu 2:

Giải bài toán người đưa thư với đồ thị có trọng số trên Hình 2.42.
Media VietJack

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

Câu 3:

Viết tập hợp các đỉnh và tập hợp các cạnh của mỗi đồ thị sau:
Media VietJack

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

Câu 4:

Chứng minh rằng nếu G là một đơn đồ thị có ít nhất hai đỉnh thì G có ít nhất hai đỉnh cùng bậc.

Xem đáp án » 12/07/2024 917

Câu 5:

Tìm một chu trình Euler trong đồ thị trên Hình 2.40.
Media VietJack

Xem đáp án » 13/07/2024 767

Câu 6:

Giải bài toán người đưa thư với đồ thị có trọng số trên Hình 2.41.
Media VietJack

Xem đáp án » 12/07/2024 677

Câu 7:

Hãy chỉ ra ít nhất 5 đường đi từ S đến Y trong đồ thị trên Hình 2.38.
Media VietJack

Xem đáp án » 13/07/2024 447

Bình luận


Bình luận
Đă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 2 - 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 3 - 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 4 - 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

tailieugiaovien.com.vn