in Graph Theory
537 views
0 votes
0 votes

Let $G$ be a simple undirected complete and weighted graph with vertex set $V = {0, 1, 2, …. 99.}$ Weight of the edge $(u, v)$ is $\left | u-v \right |$ where $0\leq u, v\leq 99$ and $u\neq v$. Weight of the corresponding maximum weighted spanning tree is______________


Doubt:Here asking for maximum weight spanning tree. So, there weight will be $0$ to every node. Isnot it? but answer given 7351.   

in Graph Theory
by
537 views

1 Answer

1 vote
1 vote
Best answer

Answer :-

selected by

4 Comments

See

if there are n vertex and also n edge , there is atleast 1 cycle

right?

Here in ur answer also some possibility of forming cycle

So, how do u determine, that those cycle will not be formed? or ur graph free from those cycle?
0
0

if there are n vertex and also n edge , there is atleast 1 cycle

Yes. 

 So, how do u determine, that those cycle will not be formed? or ur graph free from those cycle?

Apply the prim's algorithm on the 2nd graph which is in the given answer with relaxation after removing each vertex from min-heap.. This algo takes care of loop.. Right? 

0
0
yes, I got it, by taking small example like 1 to 9

but very difficult with primes
1
1

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true