If you cre

• A covering for Figure 2 is {1, 2, 3, 17}.
• Show the minimum cover for the bipartite graph shown in Figure 2.
o The cover is {1, 16, 17}.
Figure 2 Bipartite Graph
• Examples:
o Suppose you have a set of interpreters and a set of languages that need to be
interpreted. Edges represent “can interpret.” We want to find the minimal
number of interpreters to hire so that you can interpret all languages.
o Set of people and a set of categories (male, Asian, CS major, single, ...). We want
to form a committee with representation from all groups.
• Set cover – given a collection of subsets, find a minimum number of subsets such that
their union is the universe.
o Can you see how to map this problem to the bipartite cover problem?
 Nodes for each subset. Nodes for each element. Edges represent “contains.”
• This ability to map one problem into another is key to using knowledge of “algorithms community.” This is likely the reason why I always try to find similarities between things that seem different (e.g., cleaning up for company).
• NP-hard – no one has developed a polynomial time algorithm. o Also called intractable or exponential.
o We use greedy algorithms to approximate.
• Greedy criterion – Select the vertex of A that covers the largest number of uncovered vertices of B. Also keep a Boolean array that tells whether each node is covered or not.
o This idea could be implemented via a max tournament tree of “willCover” – take the biggest.
Shortest Paths
• Given a digraph with each edge in the graph having a nonnegative cost (or length).
• Try to find the shortest paths (in a digraph) from a node to all other nodes.
• Greedy criterion – From the vertices to which the shortest path has not been generated,
select one that results in the least path length (the smallest one).
• Have a reached set of nodes and an unreached set of nodes.
1. Initially, only the start node is reached.
The Greedy Method Page 4

2. Use a min priority queue to store the total path lengths of each of the reached nodes to its successors.
3. While priority queue is not empty
 Pick the shortest total length node.
• If it has already been reached, discard.
• Else count it as reached.
 Enqueue the total path lengths of each of the reached nodes to its
successors.
• For example, consider the digraph Figure 3 in and calculate the shortest path.
Figure 3 Shortest Path
Minimal Spanning Trees
• Problem – select a subset of the edges such that a spanning tree is formed and the weight of the edges is minimal.
• Example – need to connect all sites to sewer system - want to minimize the amount of pipe.
• Consider the spanning tree shown in Figure 4.
Figure 4 Spanning Tree
• Prim’s algorithm
o Greedy criterion – From the remaining edges, select a least-cost edge whose
addition to the set of selected edges forms a tree. Tree – set of vertices already in MST
Succ – set of vertices not in Tree but in Succ[Tree] Place any vertex (to serve as root) in MST.
The Greedy Method
Page 5
1. Find the smallest edge that connects Tree with Succ
2. Add the edge to the MST and update Tree and Succ
• Uses a greedy method – obtain a globally optimal solution by means of a locally optimal
solution.
• Using Figure 4 and Prim’s algorithm, we add the edges in the following order: (1,6),
(6,5), (5,4), (4,3), (3,2), and (2, 7).
• How do we find smallest edge? (sort or priority queue)
• Kruskal’s algorithm
o Greedy criterion – From the remaining edges, select a least-cost edge that does not result in a cycle when added to the set of already selected edges.
Let each vertex be a separate component.
1. Examine each edge in increasing order of cost.
2. If edge connects vertices in same component, discard it. Otherwise, add edge to
MST. Update components.
• Using Figure 4 and Kruskal’s algorithm, we add the edges in the following order: (1,6),
(3,4), (2,7), (2,3), (4,5), and (5,6).
• How do we find smallest edge? (sort or priority queue)
More Traversals of a Graph or Digraph
• Tour – visit each vertex in a graph exactly once and finish at the vertex started from.
• Eulerian tour – find a path/tour through the graph such that every edge is visited
exactly once. (Easy – check nodal degree; if all are even, it is possible.)
• Hamiltonian tour – find a path through the graph such that every vertex is visited
exactly once. (NP complete)
• See Figure 5 for different tours.
Figure 5 Different Tours
The Greedy Method
Page 6

at the bottom of the page.

OTHERWISE NO CREDIT ! (If you use the "Create a child page" button, this should happen automatically...)