October 2, 2015

Wiring Electronic Circuits Problem (1)

  • Chapter 23 of Introduction to Algorithms (3rd Edition), Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein.
  • Design of electronic circuits
    • Interconnect pins of components, pins are electrically equivalent
    • Interconnect \(n\) pins to \(n-1\) cables (each to a pair of pins)
    • Prefer wiring using least amount of wire
  • Model problem with an undirected graph
    • \(V\), set of pins
    • \(E\), set of conections between pins
    • \(W\), cost of connecting two pins associated to the edges

Wiring Electronic Circuits Problem (2)

  • Find the acyclic subset \(T \subseteq E\) connecting all vertices with the minimum weight

    \[w(T) = \sum_{(u,v) \in T} w(u,v)\]

  • \(T\) is acyclic and connects all vertices
  • \(T\) is known as a spanning tree

  • The problem of finding this tree is known as the minimum spanning tree problem

Algorithms to Cover

  • Kruskal
  • Prim
  • Execution time
    • \(O(ElgV)\), implemented with binary heaps
  • Enhancement for Prim
    • \(O(E + VlgV)\) with Fibonacci heaps
    • Enhancement when \(|V|\) is much smaller than \(|E|\)
  • Both algorithms are greedy
    • Do not usually guarantee finding global optimal solutions
    • For \(MST\) can be proved that some strategies do find an \(ST\) with minimum weight

Growing an \(MST\)

  • Given an undirected connected graph, \(G = (V, E)\) with a weights function \(w : E \rightarrow R\)
  • We want to find an \(MST\) for \(G\)
  • We could consider a greedy strategy
    • Generic algorithm

Loop Invariant - Generic Algorithm - \(MST\)

  • Before each iteration
    • \(A\) is a subset of an \(MST\)
  • Each step
    • Determine an edge \((u, v)\) that can be added to \(A\) without violating this invariant
      • \(A \cup \{(u, v)\}\) is also a subset of the \(MST\)
      • An edge with this characteristic is called a safe edge for \(A\), because we can add it in a safe way, keeping the invariant

Generic MST Algorithm

  • Initialization
    • After line 1, set \(A\) trivially satisfies the loop invariant
  • Maintenance
    • The loop in lines 2 - 4 keeps the invariant by adding only safe edges
  • Termination
    • All edges added to \(A\) are in the \(MST\), then set \(A\) returned in line 5 should be an \(MST\)

How Can We Find Safe Edges?

  • This is the hard part of the process
  • Rule to recognize safe edges
  • Theorem 23.1

Theorem 23.1

  • Let \(G = (V, E)\) be a connected, undirected graph with a real-valued weight function \(w\) defined on \(E\). Let \(A\) be a subset of \(E\) that is included in some minimum spanning tree for \(G\), let \((S, V - S)\) be any cut of \(G\) that respects \(A\), and let \((u, v)\) be a light edge crossing \((S, V - S)\). Then, edge \((u, v)\) is safe for \(A\).

Definitions

  • A CUT \((S, V - S)\) of an undirected graph \(G = (V, E)\) is a partition of \(V\)
  • An edge \((u, v) \in E\) CROSSES cut \((S, V - S)\) if any of its endpoints is in \(S\) and the otherone is in \(V - S\)
  • We say that a cut RESPECTS a set \(A\) of edges if no edge in \(A\) crosses the cut.
  • An edge is a LIGHT EDGE crossing a cut if its weight is the minimum of the edges crossing the cut
    • An edge is a light edge satisfying a property if its weight is the minimum among any edge satisfying the property

\(MST\) for a Connected Graph

  • Total weight: 37
  • It isn't unique, changing \((b, c)\) for \((a, h)\) we have another \(MST\) with weight 37

Examples of a Cut

Theorem 23.1, to Recognize Safe Edges

  • Given \(G = (V, E)\) a connected and undirected graph with a weights function \(w\) with real values defined over \(E\)
  • Let \(A\) be a subset of \(E\) included in an \(MST\) of \(G\), and let \((S, V - S)\) be any cut of \(G\) that respects \(A\), and let \((u, v)\) be a light edge crossing \((S, V - S)\). Then, edge \((u, v)\) is safe for \(A\)

Proof of Theorem 23.1

  • Let \(T\) be an \(MST\) that includes \(A\)
  • We assume that \(T\) doesn't contain light edge \((u, v)\)
  • We will build another \(MST\), \(T^{\prime}\) that includes \(A \cup \{(u, v)\}\)
    • Cut and paste technique
    • Proving that \((u, v)\) is a safe edge for \(A\)

Proof of Theorem 23.1

Proof of Theorem 23.1

  • The edge \((u, v)\) forms a cycle with the edges in the path \(p\) from \(u\) to \(v\) in \(T\)
  • Because \(u\) and \(v\) are in opposite sides of the cut \((S, V - S)\), then there is at least an edge in \(T\) in the path \(p\) that also crosses the cut
    • Let \((x, y)\) be that edge that also crosses the cut
  • \((x, y)\) is not in \(A\) because the cut respects \(A\)
  • Because \((x, y)\) is in the unique path from \(u\) to \(v\) in \(T\), if we remove \((x, y)\) we break \(T\) in two components
  • Adding \((u, v)\) we reconnect the components and form a new \(MST\), \(T^{\prime} = T - \{(x, y)\} \cup \{(u, v)\}\)

Proof of Theorem 23.1

  • We now prove that \(T^{\prime}\) is also an \(MST\)
  • Because \((u, v)\) is a light edge that crosses \((S, V - S)\) and \((x, y)\) also crooses this cut
    • \(w(u, v) \leq w(x, y)\)
  • Then
    • \(w(T^{\prime}) = w(T) - w(x, y) + w(u, v) \leq w(T)\)
  • But \(T\) is an \(MST\), then \(w(T) \leq w(T^{\prime})\)
    • Then \(T^{\prime}\) must also be an \(MST\)

Proof of Theorem 23.1

  • Now we prove that \((u, v)\) is really a safe edge for \(A\)
  • As \(A \subseteq T^{\prime}\) because \(A \subseteq T\) and \((x, y) \notin A\)
    • Then \(A \cup \{(u, v)\} \subseteq T^{\prime}\)
    • Consequently, as \(T^{\prime}\) is an \(MST\), \((u, v)\) is safe for \(A\)

Corolary 23.2

  • Let \(G = (V, E)\) be a connected and undirected graph with a weights function \(w\) defined over \(E\) with real values
  • Let \(A\) be a subset of \(E\) that is included in some \(MST\) of \(G\)
  • Let \(C = (V_C, E_C)\) a connected component (tree) in the forest \(G_A =(V, A)\)
  • If \((u, v)\) is a light edge that connects \(C\) to any other component in \(G_A\), then \((u, v)\) is safe for \(A\)

Kruskal's and Prim's Algorithms

  • Variants of the generic algorithm
  • Use a specific rule to determine a safe edge
  • Kruskal
    • Set \(A\) is a forest
    • Safe edge added \(A\) is always the edge with the lowest weight in the graph that connects two distinct components
  • Prim's
    • Set \(A\) forms a unique tree
    • The safe edge added to \(A\) is always the edge with the lowest weight that connects the tree to a vertex that is not in the tree

Kruskal

  • The safe ede to add to the forest is that edge \((u, v)\) that connects any of two trees in the forest but with the lowest weight
  • Because \((u, v)\) must be a light edge that connects \(C_1\) to other tree
    • Corolary 23.2 implies that \((u, v)\) is a safe edge for \(C_1\)
  • Kruskal's is greedy

Kruskal's Algorithm

Kruskal's Example (1)

Kruskal's Example (2)

Kruskal's Example (3)

Kruskal's Execution Time

  • It depends on the implementation of the disjoint-set data structure
    • \(O(ElgV)\)

Prim's

  • Similar to the Dijkstra algorithm to find shortest paths in a graph (we will see it as well)
  • Property
    • Edges in set \(A\) always form a tree
  • The tree is initialized with an arbitrary root vertex and it is grown until the tree is expanded to all vertices in \(V\)
  • Each step a light edge is added to the tree \(A\) that connects it with a vertex that hasn't been connected
  • According to corolary 23.2, the rule adds only edges that are safe for \(A\), then, at the end, the edges of \(A\) form an \(MST\)
  • Prim's is greedy

Prim's Algorithm

Prim's Algorithm

  • Priority Queue on a key field
    • For each vertex \(V\), \(key[v]\) is the minimum weight for any edge that connects \(v\) to an edge in the tree
    • By convention \(key[v] = \infty\) if that edge doesn't exist
  • \(\pi[v]\) names the father of \(v\) in the tree

Homework

  • Study the loop invariant of the \(MST-PRIM\) algorithm

  • Show that a graph has a unique minimum spanning tree if, for every cut of the graph, there is a unique light edge crossing the cut.

  • What happens if we have negative weights in a graph while constructing a MST?

Prim's Example (1)

Prim's Example (2)

Prim's Example (3)

Prim's Execution Time

  • \(O(ElgV)\)
  • It can be enhanced with Fibonacci-Heaps
    • \(O(E + VlgV)\)

Exercise

  • We need to find the lowest cost for the road network connecting 5 cities. The cities and the cost to build the road between them are:
    • Cities: a, b, c, d, e
    • a-b: 3
    • a-c: 5
    • a-d: 11
    • a-e: 9
    • b-c: 3
    • b-d: 9
    • b-e: 8
    • c-e: 10
    • d-e: 7
  • Find the lowest cost road using the Kruskal's and Prim's algorithms.