NO - Summary of Chapter 9

Given a graph $G$ its MSP (Minimum Spanning Tree, defined as $T^{\ast }$) is a connected sub-graph containing no cycles and spanning over all the nodes, also the MSP has the minimum possible total cost of the arcs (each arc has cost $c_{ij}$)

The arcs of $G$ that make the MSP are called or tree arcs, while the one that are excluded from the MSP are called non-tree arcs.

---

There are 2 equivalent condition for finding the MSP of a graph:

Cut Optimality

$\forall (i,j)\in T^{\ast },c_{ij}\le c_{kl},k\in S,l\in S^{\prime }$ where: $\left[S,S^{\prime }\right]$ is the cut obtained by removing the arc $(i,j)$ from $T^{\ast }$.

Path Optimality

$$\forall (k,l)\notin T^{\ast },c_{ij}\le c_{kl},(i,j)\in P$$

where: $P$ is the path on $T^{\ast }$ from $i$ to $j$.

---

Formulation of MSP Problem

• Variables: $b_{ij}$ : boolean, $1$ if $(i,j)$ belongs to $T^{\ast }$, $0$ otherwise.
  
• Constants: $c_{ij}$ : cost of arc $(i,j)$ $n$ : number of nodes
  
• Objective Functions: $\min \overline{b}\cdot \overline{c}$ (minimize the cost of the arcs in $T^{\ast }$)
  
• Constraints:

$$\sum _i\sum _j{b}_{ij}==n-1$$

span over all nodes → the number of arcs is fixed.

$$\sum _{b\in \text{arcs}}{b}_{ij}<=\text{number of nodes in arcs}-1\forall \text{arcs}\in S$$

Where:

• $\text{arcs}$ is a set of arcs of the graph.
• S is a set containing all possible combination of arcs in the graph. no-cycles → Given all possible combination of arcs we have that each combination has to have a number of “active” arcs ($b_{ij}=1$) less or equal than the number of nodes less $1$ present in the combination. (otherwise it would be a cycle)

---

Kruskal Algorithm:

Complexity: $O(mlog(m))+O(m+nlog(n))$ operations

---

Prim Algorithm

In practice the Prim Algorithm is the better one

Complexity: $O(m+nlog(n))$ operations

---