as you know we have equivalent condition for graphs so I want to ask a very basic question and please help me what is exactly w1(e1) and w1(e2) and w2(e1) and w2(e1) ? If e1 means path from A to B so w1 means the weight of the path e1 and so what about w2 and what does it mean means ? is there any link for this kind of topic to understand better ?

thank you so much

this is main question

enter image description here

  • $\begingroup$ Where are you reading this from? Upload a photo of it or provide a link. $\endgroup$ – RandomPerfectHashFunction Oct 1 '19 at 20:40
  • 1
    $\begingroup$ Please merge your comment into seamless question post via edit, there should be a standalone question that doesn't require reading comments. Thank you. $\endgroup$ – Evil Oct 1 '19 at 21:44
  • $\begingroup$ Please edit your question provide a full reference for the source where you encountered the quoted material. Please transcribe the mathematics into text or MathJax, rather than including a picture. Thank you. $\endgroup$ – D.W. Oct 2 '19 at 6:19
  • $\begingroup$ frankly speaking it doesn't have any reference and this question is on paper $\endgroup$ – graphicart86 Oct 2 '19 at 9:04

The solution provided here is highly inelegant as it uses a lemma which is a more general result. This 'solution' should instead be considered as more of a hint: a minimal solution can instead be found by extracting the most relevant parts of the proof of the lemma.

Note that $w_1(e_1)<w_1(e_2)\Leftrightarrow w_2(e_1)>w_2(e_2)$ implies that $w_1(e_1)=w_1(e_2)\Leftrightarrow w_2(e_1)=w_2(e_2)$. In particular, if we order the edges in a non-decreasing order according to $w_1$, then we have also ordered them in non-increasing order according to $w_2$.

Now, recall that any minimal spanning tree (for $(G,w_1)$) can be found by Kruskal's algorithm (lemma -- https://cs.stackexchange.com/a/95625/109876), so in particular there is an order on the edges which is non-decreasing for $w_1$ such that $\mathcal{T}(\mathcal{V},\mathcal{E}')$ is selected. This same order is non-increasing for $w_2$, and can therefore be used to find a maximum spanning tree (for $(G,w_2)$) using Kruskal's algorithm. But since Kruskal's selection process is independent of the actual weights (and depends only on the ordering and whether the current edge creates a cycle or not), the algorithm will output $\mathcal{T}(\mathcal{V},\mathcal{E}')$ again.

  • $\begingroup$ Thank you so much for your reply but still I have a question maybe stupid question but when it says w1 and w2 for e1 does it mean an edge with two weight ? if yes so what about e2 ? e2 with w1 and w2 again and does it mean e2 has 2 different weight value ? $\endgroup$ – graphicart86 Oct 2 '19 at 9:04
  • $\begingroup$ A weighted graph can be defined as a pair $(G,w)$ where $G=(V,E)$ is a graph and $w$ is a weight function where $w$'s support is included in $E$. In this problem, we consider the two following weighted graphs $(G,w_1)$ and $(G,w_2)$ (on the same underlying graph). But in each of the graphs each edge only has one weight. $\endgroup$ – integrator Oct 2 '19 at 9:15
  • $\begingroup$ @graphicart86 Yes, you are starting off with two different edge-weighted graphs. The two graphs have the same vertex and edge sets, but different weight functions. If you order the edges as $e_1,e_2,\ldots,e_m$ and if this lists the edges of the first graph in increasing order of weights, then this also lists the edges of the second graph in decreasing order of weights. $\endgroup$ – Ashwin Ganesan Oct 7 '19 at 3:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.