$2.[$Spanning Trees Over Small Perturbations$]$: Minimum Spanning Trees play a vital role in routing TCP$/$IP packages. Joey runs the IT Division for a local hospital. He has represented all computers, switches, and routers within the hospital intranet as nodes and their connections $($physical and wireless$)$ as edges. He used communication time, i$.$e$.,$ the time it takes to send a package from a node to a connected node, between neighboring nodes, as the edge weight. He then ran Prim's algorithm to find an MST of the resulting graph. He routes the intranet packages between the nodes using the MST$.$

However, he did not like running Prim's algorithm for reasons nobody could understand and was adamant about never running any MST algorithm covered in any Algorithm course again. Let us suppose the original network was $\backslash ($ G$($V$,$ E$,$ W$)\backslash )$ and the resulting spanning tree was $\backslash ($ T$\backslash$left$($V$,$ E$^\{\backslash$prime$\},$ W$^\{\backslash$prime$\}\backslash$right$)\backslash ).$ Note: Joey can still use the 'blue' rule and the 'red' rule $($just not on the whole graph, as that corresponds to the Greedy Algorithm we discussed in the class$).$

$($a$)$

It was working great for Joey until a new computer was added to the network. Let us represent the new node being added as $\backslash ($ v $\backslash ).$ When node $\backslash ($ v $\backslash )$ is added to $\backslash ($ G $\backslash ),$ edges incident on $\backslash ($ v $\backslash )$ are also added to $\backslash ($ G $\backslash ).$ Help Joey avoid rerunning an MST algorithm by designing an approach to update $\backslash ($ T $\backslash )$ efficiently. Describe your approach and give a pseudocode.

$($b$)$ Joey has run into trouble again. This time, a physical cable between two nodes in the MST got damaged. The cable vendor was not able to replace the cable. Help Joey update $\backslash ($ T $\backslash )$ efficiently again. Describe your approach and give a pseudocode.

$($c$)$ Joey's self$-$inflicted $($nobody is forcing him not to rerun the MST algorithms$)$ troubles do not seem to end. This time, a cable that was not in the tree was damaged and replaced by a much faster cable, thus decreasing the cost of the edge. Help Joey update $\backslash ($ T $\backslash )$ efficiently again. Describe your approach and give a pseudocode.