Câu hỏi:

17/06/2026 136

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

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 » 17/06/2026 514

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 » 17/06/2026 306

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 » 17/06/2026 202

Câu 4:

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 » 17/06/2026 184

Câu 5:

Chứng minh rằng không có đơn đồ thị với 12 đỉnh và 28 cạnh mà các đỉnh đều có bậc 3 hoặc 6.

Xem đáp án » 17/06/2026 165

Câu 6:

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

Xem đáp án » 17/06/2026 155

Câu 7:

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 » 17/06/2026 146

Câu 8:

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 » 17/06/2026 136

Câu 9:

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 » 17/06/2026 129

Câu hỏi mới nhất

Xem thêm »
Xem thêm »