Algorithm 19

Question

Why 2nd statement false

Q. 26 Consider the following statements
I. Let $T$ be a minimum spanning tree of a graph G. Then for any two vertices $u$ and $v$ the path from $u$ to $v$ in $T$ is the shortest path from $u$ to $v$ in the graph $G$.
II. Suppose that average edge weight for a graph $G$ is $A_{\text {avg }}$. Then the minimum spanning tree of $G$ will have weight at most $(n-1) A_{\text {avg }}$. Where $n$ is number of vertices in graph $G$.
Which of the above statements are true?

• A. Only I
  
• B. Only II
  
• C. both I and II
  
• D. None of these

Answer 1

Counter example is

Comments

here why have u ignored 29 ?  I think MST = 30 +31 + 30 + 29 =120.

---

yes, you are right, i mistaken... i will think what should be the counter example.

---

@nephron

check it now, i came up with another example.

---

 

Is that's right ??

 

---

yes, this example also right.

---

but the problem is .... in the exam it is difficult to find such an example.... when we are already under immense pressure

---

but this a simplest way to solve by  "Hit and trail"

it's not easy to by hearted all these statements and conditions also

---

@Magma

it's not easy to by hearted all these statements and conditions also

He doesn't intense that by heart this statement, he is saying we can prove it.

@nephron

yes, i too agree, it is some what difficult, to find counter example under immense pressure, But Proving it is wrong by other method is more difficult than this.

Answer 2

Let,

n1 = MST edges  = V-1 = n-1 and

n2 = Rest of the edges

(MST_edgesSum + Rest_edgesSum ) = (n1 + n2) A_avg

MST_edgesSum = (n1 + n2)A_avg  -  Rest_edgesSum

MST_edgesSum = (n1)A_avg  + n2(A_avg - A_avgRestEdges)

Thus, Mst edges Sum can atmost be  equal to (n1)Aavg  if ,

                       n2(A_avg - A_avgRestEdges ) =0

               A_avg - A_avgRestEdges can take zero, positive as well as negative value  and

              n2 =0 is possible only when we have graph G itself being MST and there are no extra edges

Thus, MST_edgesSum  >=  (n1)A_avg. , when  A_avg - A_avgRestEdges  takes positive value.

          MST_edgesSum  <=  (n1)A_avg    , when  A_avg - A_avgRestEdges  takes negative value.

          Equality will hold when graph G = MST.

But the question demands MST_edgesSum  <=  (n1)A_avg.  is always true. So, the stmt. false.

Comments

1.

if  A_avg will correspond to only MST edges , then how the above relation hold good? 

>> In this case n2 =0. If u have only MST edges how come u can have extra edges. A_avg correspond to total edges of the graph.

2.

n2 is zero ( no extra edges) ===> it is zero.  

if u consider n2 =0, then u have presumed the special case that the graph G is MST. So, I have taken n2 !=0 for the purpose of generalisation.

3.

n2 ≠ 0 ===> how can we say (A_avg - A_avgRestEdges) always lead to ≥ 0 ?

u will have to consider (A_avg - A_avgRestEdges)>,<,=0. and anything is possible and the stmt mentioned in the holds false

---

I have edited the answer to make it more detailed for understanding. I think this is my final submission and I find the proof to be correct. Earlier I had given intuitive answer where E/V was used to determine the answer. So, I changed to give a mathematical explaination.

---

Now, it looks ok, in your previous edit you didn't mentioned that MST_edgesSum  <=  (n1)A_avg    , when  A_avg - A_avgRestEdges  takes negative value, that is the reason i commented