Câu hỏi:

13/07/2024 1,572

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

Sách mới 2k7: Tổng ôn Toán, Lí, Hóa, Văn, Sử, Địa…. kỳ thi tốt nghiệp THPT Quốc gia 2025, đánh giá năng lực (chỉ từ 110k).

Tổng ôn toán Tổng ôn lý Các môn khác

Quảng cáo

Trả lời:

verified
Giải bởi Vietjack

Lời giải:

Đồ thị Hình 2.42 chỉ có hai đỉnh bậc lẻ là D và E nên ta có thể tìm được một đường đi Euler từ D đến E (đường đi này đi qua mỗi cạnh đúng một lần).

Một đường đi Euler từ D đến E là DBACDEBCE và tổng độ dài của nó là

2 + 4 + 4 + 2 + 6 + 3 + 5 + 1 = 27.

Để quay trở lại điểm xuất phát và có đường đi ngắn nhất, ta cần tìm một đường đi ngắn nhất từ E đến D theo thuật toán gắn nhãn vĩnh viễn.

Đường đi ngắn nhất từ E đến D là ECD và có độ dài là 1 + 2 = 3.

Vậy một chu trình cần tìm là DBACDEBCECD và có độ dài là 27 + 3 = 30.

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

Câu 2:

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

Câu 3:

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 1,035

Câu 4:

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

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

Câu 5:

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 729

Câu 6:

Tìm số đỉnh nhỏ nhất cần thiết để có thể xây dựng một đồ thị đầy đủ với ít nhất 1 000 cạnh.

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

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

Vietjack official store