Design an algorithm to find the minimum cost spanning tree for the graph of part$($c$)$ and

extend the tree to obtain a minimum cost spanning tree for the graph of part$($a$).$

$($b$)$

$($c$)$

a$)$ Design an algorithm to determine minimum cost of a tree.

b$)$ How many minimum spanning trees does it have?

c$)$ Suppose Kruskal's algorithm is run on this graph. In what order are the edges added

to the MST$?$

d$)$ Analyze your algorithm and give the results using order notation.Assume there are $n$ workers and $n$ jobs. Let $V_{ij}$ be the value of assigning worker $i$ to job $j.$ An

Assignment of workers to jobs correspond to the assignment of $0$ or $1$ to the variables $x_{ij},1$

$$I,$jn.$ Then $x_{ij}=1$ means worker $i$ is assigned to job $j,$ and $x_{ij}=0$ means, the worker $i$ is

not assigned to job $j.$ A valid assignment is one in which each worker is assigned to exactly

one job and exactly one worker is assigned to any one job. The value of an assignment is ${\displaystyle \underset{?}{\overset{?}{}}}i$

${\displaystyle \underset{?}{\overset{?}{}}}j{V}_{ij}{x}_{ij}$

For example assume that there are three workers $w1,w2,w3$ and three jobs $j1,j2$ and $j3.$ Let

the values of assignment be $V11=11,v12=5,v13=8,V21=3,v22=7,v23=15,v31=8,v32=12$

and $v33=9.$ Then a valid assignment is $x12=1$ and $x23=1$ and $x31=1.$ The rest of the $j\text{'}s$ are

zero's. The value of the assignment is $5+15+8=28.$

The optimal assignment is a valid assignment of maximum value. Write algorithms for two

different greedy schemes. One of these assigns a worker to the best possible job. The other

assigns a job the best possible worker. Show that neither of these schemes is guaranteed to

yield optimal assignments. Is either scheme always better than the other? Assume $V_{ij}>0.$

Analyze your algorithm and give the results using order notation.