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

• Where are you reading this from? Upload a photo of it or provide a link. – RandomPerfectHashFunction Oct 1 '19 at 20:40
• Please merge your comment into seamless question post via edit, there should be a standalone question that doesn't require reading comments. Thank you. – Evil Oct 1 '19 at 21:44
• 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. – D.W. Oct 2 '19 at 6:19
• frankly speaking it doesn't have any reference and this question is on paper – graphicart86 Oct 2 '19 at 9:04

Note that $$w_1(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.
• 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. – integrator Oct 2 '19 at 9:15
• @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. – Ashwin Ganesan Oct 7 '19 at 3:52