Câu hỏi:

12/07/2024 1,343

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

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:

Vì đồ thị Hình 2.41 là liên thông và các đỉnh đều có bậc chẵn (ở đây đều là bậc 4) nên đồ thị có chu trình Euler.

Một chu trình Euler xuất phát từ đỉnh A là ABCDABDCA và tổng độ dài của nó là

7 + 6 + 8 + 5 + 7 + 2 + 3 + 8 + 4 + 1 = 51.

Vậy một chu trình cần tìm là ABCDABDCA và có độ dài là 51.

Bình luận


Bình luận

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

Câu 1:

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 3,144

Câu 2:

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 3,047

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

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

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

Câu 6:

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

Xem đáp án » 11/07/2023 1,191