CS2040s: MST (Minimum Spanning Tree)

Minimum Spanning Tree

A spanning tree is a acyclic subset of the edges that connects all nodes.
A minimum spanning tree is a spanning tree with minimum weight

The weight is the sum of all the weights of all the edges in the tree.

Can we use MST to find shortest paths? Nope

=> Shortest path are not related to MST

The MST may not cover the edge of the shortest path.

Application:

- Network designs

- Machine learning

- Data mining
- Electrical networks
- Ethernet autoconfig
- Road networks
- Bottleneck paths
- Telephone networks

Properties

Assumptions:

- Edge weight are distinct

- Graph is connected and undirected

1. No cycles

=> If there are a cycle, removing the edge will reduce the weight

2. Cutting an MST will result in two MST

3. Cycle property
=>For every cycle, the maximum edge is not in the MST
=>For every cycle, Minimum weight (in cycle) is not always in the MST

4. Cut property
=>for every partition of nodes, the minimum weight edge across the cut must be in the MST

=> A cut is the splitting of graph such that there is two disjoint subsets.

For every vertex, the minimum outgoing edge is always part of the MST, 
True

=> Due to the cut property, if we cut every one node from the rest of the graph, the connected is always minimum weight edge

For every vertex the maximum outgoing edge could be part of the mst
True

=> A maximum edge for an node might be the minimum for another

PRIM's Algorithm

Build spanning tree

Basic Idea:

Imagine a set S of nodes where it contains some random nodes.

1. Init: S = {A}

2. Identify cut: {S, V-S}

3. Find min weight edge on cut by taking the shortest edge among all nodes in set S

4. Add new node connected to S

5. Repeat 2 onward

computeMST (G) foreach v in V do key[v] = ∞ pred[v] = -1 key[0] = 0 PQ = empty Priority Queue foreach v in V do insert (v, key[v]) into PQ while PQ is not empty do u = getMin(PQ) foreach edge(u,v) in E do if PQ contains v then w = weight of edge (u,v) if w < key[v] then pred[v] = u key[v] = w decreasePriority (PQ, v, w) end

We can find the lightest edge with min weight on a cut using a PQ

Running time: O(ElogV)

=> Each vertex is added/remove from PQ

=> Using a PQ O(nlogn) -> O(VlogV) where logV is the sort and V is the number of vertices went through

=> Each edge -> One decrease Key [Each time we are decreasing an edge]
=> Look through all the edges for each node -> O(E)

-> O(ELogV)

Dijkstra vs Prim

Both are greedy

- Efficient

- Optimum

- Both using a PQ

Dij => PQ for distance

Prim=> PQ for Edge weight

Longest Path in a DAG

Solution 1:

Shortest path relaxation:

Modify it, flip the sign in the condition for the relax function

Initialised everything to negative infinity

Time: O(V+E)

Negate the edges.

Run the shortest path algorithm

This work because it is a DAG.

THIS CANT WORK IF IT IS NOT A DAG

=> Create negative cycles

Scheduling

Given a set of tasks {A, B, C, D, E, F} and a set of constraints:
 A must be completed at least 10 mins before C
 D must be completed at most 20 minutes after E
 B must be done after FDevise an efficient algorithm to tell if there is a feasible schedule.

When there are a series of relationship, it is a graph.

We must model this problem using graph and find how to solve it using the graph algo that we already know.

Represent each node as a job, split that node into two nodes that signifies the start and end

e.g if job 0 takes 5 mins,

the s0 and e0 is two nodes connected by a weight 4 edge

The e0 is then connected to the next node s1 connected using the weight edges required before 1 can be runned after completing 0

We can have a dummy start node and dummy end node.

We use to get the longest path.

=> This is because we need to pass through everything

Using bellman ford we can do this.