Sự khác nhau giữa tối thiểu Spanning Tree và Shortest Path Tree

Question

Dưới đây là một tiêu thụ đặc biệt:

Hoặc chứng minh những điều sau hoặc đưa ra một phản ví dụ:

(a) là con đường giữa một cặp đỉnh trong một tối thiểu cây bao trùm của một đồ thị không bị vạch trần nhất thiết phải là con đường ngắn nhất (trọng lượng tối thiểu)?

(b) Giả sử rằng cây bao trùm tối thiểu của biểu đồ là duy nhất. Có phải là đường đi giữa một cặp đỉnh trong cây bao trùm tối thiểu của một biểu đồ không giới hạn là không nhất thiết phải là đường đi ngắn nhất (trọng lượng tối thiểu) không?

trả lời của tôi là

(a)

Không, ví dụ, đối với đồ thị dưới 0, 1, 2, 0-1 là 4, 1-2 là 2, 2-0 là 5 , sau đó con đường ngắn nhất đúng 0-2 là 5, nhưng mst là 0-1-2, trong mst, 0-2 là 6

(b)

vấn đề của tôi đi vào này (b).

Tôi không hiểu cách whether the MST is unique có thể ảnh hưởng đến đường đi ngắn nhất.

Đầu tiên, sự hiểu biết của tôi là khi trọng số của các cạnh không khác biệt, nhiều MST có thể tồn tại cùng một lúc, đúng không?

Thứ hai, ngay cả khi MST là duy nhất, câu trả lời của (a) ở trên vẫn áp dụng cho (b), phải không?

Answer 1

Về (a), tôi đồng ý.

Về (b), đối với một số biểu đồ, có thể có nhiều cây bao trùm tối thiểu có cùng trọng số. Xem xét một vòng tròn C3 với đỉnh a, b, c; trọng số a-> b = 1, b-> c = 2, a-> c = 2. Biểu đồ này có hai MST, {a-b-c} và {c-a-b}.

Tuy nhiên, counterexample của bạn vẫn giữ, vì MST là duy nhất ở đó.

Answer 2

Vì vậy, cho phép hãy xem một đồ thị rất đơn giản:

(A)---2----(B)----2---(C) 
\     /
    ---------3---------- 

Các cây bao trùm nhỏ nhất cho biểu đồ này bao gồm hai cạnh A-B và B-C. Không có các cạnh khác tạo thành một cây bao trùm tối thiểu.

Nhưng tất nhiên, đường đi ngắn nhất từ ​​A đến C là A-C, không tồn tại trong MST.

EDIT

Vì vậy, để trả lời một phần (b) câu trả lời là không, bởi vì có một con đường ngắn hơn mà tồn tại mà không có trong MST.

Answer 3

Không phải MST liên quan đến nút bắt đầu ?!
Sau đó, anh ta đang cố gắng lấy đường đi ngắn nhất từ ​​nút bắt đầu MST. Do đó, có, đường dẫn ngắn nhất được MST cung cấp bắt đầu từ A!