Cây bao trùm tối thiểu và cây đường ngắn nhất có chia sẻ ít nhất một cạnh không?

Question

Tôi đang nghiên cứu lý thuyết đồ thị và tôi có một câu hỏi về kết nối giữa các cây bao trùm tối thiểu và cây đường ngắn nhất.

Hãy để G là đồ thị được kết nối, không bị theo dõi, trong đó tất cả các cạnh được tính trọng số với chi phí khác nhau. Hãy T là một MST của G và để T _s được cây một ngắn nhất-con đường đối với một số nút s. Có phải T và T _s đảm bảo chia sẻ ít nhất một cạnh?

Tôi tin rằng điều này không phải lúc nào cũng đúng, nhưng tôi không thể tìm thấy một ví dụ. Có ai có một gợi ý về làm thế nào để tìm một counterexample?

Answer 1

Tôi nghĩ rằng tuyên bố này thực sự là đúng, vì vậy tôi nghi ngờ bạn có thể tìm thấy một ví dụ.

Dưới đây là gợi ý - lấy bất kỳ nút nào trong biểu đồ và tìm một cây đường đi ngắn nhất cho nút đó. Bây giờ hãy xem xét điều gì sẽ xảy ra nếu bạn chạy Prim's algorithm bắt đầu từ nút đó - bạn có thể đảm bảo rằng ít nhất một cạnh từ MST sẽ tìm đường vào cây đường đi ngắn nhất không?

Hy vọng điều này sẽ hữu ích!

Answer 2

Proof đến đỉnh s và cây ngắn nhất-con đường của nó T _s, nêm trong MST T là w (s, v), và giả sử nó không tồn tại trong T _s. sau đó phải có một con đường ngắn hơn từ v để s, và có một đỉnh trong đường dẫn (vì w (s, v) không phải là con đường ngắn nhất), mà giả sử là p , và làm cho s ->p ->v, w (s, v)> = đường dẫn (s ->p ->v). Di w (s, v) và thêm w (s, p) trong T, khi tất cả các cạnh là số dương và khác nhau, w (s, p) < w (s, v). chúng tôi có một cây bao trùm tối thiểu nhỏ hơn T '.

Nhưng T là MST.Here là contradiciton. Giả định không nắm giữ, trong đó chứng minh rằng T và T _s phải chia sẻ ít nhất một cạnh, và nó là w (s, v) trong MST T.

Nếu có trọng lượng với 0 chi phí, tình huống là như nhau. Bạn có thể giả sử rằng hai đỉnh mà w (a, b) = 0 là cùng một đỉnh, và loại bỏ một trong số chúng. Bằng chứng hoạt động khi trọng số không âm.

khi một số trọng lượng là tiêu cực và w (s, p)> w (s, v), có nghĩa là, w (p, v) < 0, w (s, v)> = đường dẫn (s ->p ->v) có thể không làm cho w (s , p) < w (s, v) .Nhưng trong MST T, w (s, v) nên cũng không tồn tại, bởi vì con đường (s ->p ->v) làm s để v với chi phí ít hơn, thay thế w (s, v) trong T với w (s, p) và w (p, v) nếu cần thiết làm cho một cây một ít tối thiểu kéo dài T'. Vẫn còn contradiciton.