[Help] Proof for a problem about Maximum Spanning Tree

Правка en1, от dang_252, 2020-10-30 12:52:54

Recently I came across a problem:

Given an undirected graph $$$n$$$ vertices with $$$m$$$ weighted edges. Find a simple cycle with the value "Max weighted edge" + "Min weighted edge" maximized and print that value.

So my algorithm is:

  • Build a Maximum Spanning Tree

  • With an edge $$$u-v$$$ weight $$$w$$$ that is not in the MST, take max answer $$$w$$$ + Max weighted edge on that path $$$u-v$$$ on the MST.

In the second point, I could not prove if "Max weighted edge on that path $$$u-v$$$ on the MST" is maximized. What if there is another path from $$$u$$$ to $$$v$$$ with "Max weighted edge" larger.

I tried to prove that the Maximum Spanning Tree guarantees that the path $$$u-v$$$ have "max weighted edge" maximized but it turned out quite wrong in my mind as we can use edges that is not belong to the current MaxST to lead $$$u$$$ to a large edge then lead to $$$v$$$.

So how my algorithm actually guarantees with an edge $$$u-v$$$ weight $$$w$$$ that is not in the MST, the "Max weighted edge on that path $$$u-v$$$ on the MST" is the maximum "Max weight edge" path from $$$u$$$ to $$$v$$$?

How to prove that from $$$u$$$ to $$$v$$$ there is not any other path that have "Max weighted edge" larger than the one in the MST which will make the answer better?

Thanks in advanced.

Теги help, mst

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en1 Английский dang_252 2020-10-30 12:52:54 1297 Initial revision (published)