This preview shows page 1-2-3-4-5-6-7-53-54-55-56-57-58-59-60-106-107-108-109-110-111-112 out of 112 pages.
15-251Great Theoretical Ideas in Computer ScienceGraphs IILecture 19, October 28, 2008RecapTheorem: Let G be a graph with n nodes and e edgesThe following are equivalent:1. G is a tree (connected, acyclic)3. G is connected and n = e + 1 4. G is acyclic and n = e + 15. G is acyclic and if any two non-adjacent points are joined by a line, the resulting graph has exactly one cycle2. Every two nodes of G are joined by a unique pathCayley’s FormulaThe number of labeled trees on n nodes is nn-2Cayley’s FormulaA graph is planar ifA graph is planar if it can be drawn in the plane without crossing edgesEuler’s FormulaEuler’s FormulaIf G is a connected planar graph with n vertices, e edges and f faces, then n – e + f = 2Graph ColoringA coloring of a graph is an assignment of a color to each vertex such that no neighboring vertices have the same colorGraph ColoringSpanning TreesSpanning TreesA spanning tree of a graph G is a tree that touches every node of G and uses only edges from GSpanning TreesA spanning tree of a graph G is a tree that touches every node of G and uses only edges from GEvery connected graph has a spanning treeImplementing GraphsAdjacency MatrixAdjacency MatrixSuppose we have a graph G with n vertices. The adjacency matrix is the n x n matrix A=[aij] with:Adjacency MatrixSuppose we have a graph G with n vertices. The adjacency matrix is the n x n matrix A=[aij] with:aij = 1 if (i,j) is an edgeaij = 0 if (i,j) is not an edgeAdjacency MatrixSuppose we have a graph G with n vertices. The adjacency matrix is the n x n matrix A=[aij] with:aij = 1 if (i,j) is an edgeaij = 0 if (i,j) is not an edgeGood for dense graphs!ExampleExampleA =0 1 1 11 0 1 11 1 0 11 1 1 0Counting PathsThe number of paths of length k from node i to node j is the entry in position (i,j) in the matrix AkCounting PathsThe number of paths of length k from node i to node j is the entry in position (i,j) in the matrix AkCounting PathsThe number of paths of length k from node i to node j is the entry in position (i,j) in the matrix AkA2 =Counting PathsThe number of paths of length k from node i to node j is the entry in position (i,j) in the matrix AkA2 =0 1 1 11 0 1 11 1 0 11 1 1 00 1 1 11 0 1 11 1 0 11 1 1 0Counting PathsThe number of paths of length k from node i to node j is the entry in position (i,j) in the matrix AkA2 =0 1 1 11 0 1 11 1 0 11 1 1 00 1 1 11 0 1 11 1 0 11 1 1 03 2 2 22 3 2 22 2 3 22 2 2 3=Adjacency ListAdjacency ListSuppose we have a graph G with n vertices. The adjacency list is the list that contains all the nodes that each node is adjacent toAdjacency ListSuppose we have a graph G with n vertices. The adjacency list is the list that contains all the nodes that each node is adjacent toGood for sparse graphs!Example1234Example12341: 2,32: 1,3,43: 1,2,44: 2,3http://www.math.ucsd.edu/~fan/hear/“Can you hear the shape of a graph?”Graphical MuzakFinding Optimal TreesFinding Optimal TreesTrees have many nice properties (uniqueness of paths, no cycles, etc.)Finding Optimal TreesTrees have many nice properties (uniqueness of paths, no cycles, etc.)We may want to compute the “best” tree approximation to a graphFinding Optimal TreesTrees have many nice properties (uniqueness of paths, no cycles, etc.)We may want to compute the “best” tree approximation to a graphIf all we care about is communication, then a tree may be enough. We want a tree with smallest communication link costsFinding Optimal TreesProblem: Find a minimum spanning tree, that is, a tree that has a node for every node in the graph, such that the sum of the edge weights is minimum48796119587Tree Approximations48796119587Tree ApproximationsKruskal’s AlgorithmA simple algorithm for finding a minimum spanning treeFinding an MST: Kruskal’s AlgorithmFinding an MST: Kruskal’s AlgorithmCreate a forest where each node is a separate treeFinding an MST: Kruskal’s AlgorithmCreate a forest where each node is a separate treeMake a sorted list of edges SFinding an MST: Kruskal’s AlgorithmCreate a forest where each node is a separate treeMake a sorted list of edges SWhile S is non-empty:Finding an MST: Kruskal’s AlgorithmCreate a forest where each node is a separate treeMake a sorted list of edges SWhile S is non-empty:Remove an edge with minimal weightFinding an MST: Kruskal’s AlgorithmCreate a forest where each node is a separate treeMake a sorted list of edges SWhile S is non-empty:Remove an edge with minimal weightIf it connects two different trees, add the edge. Otherwise discard it.18791035479Applying the Algorithm18791035479Applying the Algorithm18791035479Applying the Algorithm18791035479Applying the Algorithm18791035479Applying the Algorithm18791035479Applying the Algorithm18791035479Applying the AlgorithmAnalyzing the AlgorithmAnalyzing the AlgorithmThe algorithm outputs a spanning tree T.Analyzing the AlgorithmThe algorithm outputs a spanning tree T. Suppose that it’s not minimal. (For simplicity, assume all edge weights in graph are distinct)Analyzing the AlgorithmThe algorithm outputs a spanning tree T. Let M be a minimum spanning tree.Suppose that it’s not minimal. (For simplicity, assume all edge weights in graph are distinct)Analyzing the AlgorithmThe algorithm outputs a spanning tree T. Let M be a minimum spanning tree.Let e be the first edge chosen by the algorithm that is not in M. Suppose that it’s not minimal. (For simplicity, assume all edge weights in graph are distinct)Analyzing the AlgorithmThe algorithm outputs a spanning tree T. Let M be a minimum spanning tree.Let e be the first edge chosen by the algorithm that is not in M. Suppose that it’s not minimal. (For simplicity, assume all edge weights in graph are distinct)If we add e to M, it creates a cycle. Since this cycle isn’t fully contained in T, it has an edge f not in T.Analyzing the AlgorithmThe algorithm outputs a spanning tree T. Let M be a minimum spanning tree.Let e be the first edge chosen by the algorithm that is not in M. N = M+e-f is another spanning tree.Suppose that it’s not minimal. (For simplicity, assume all edge weights in graph are distinct)If we add e to M, it creates a cycle. Since this cycle isn’t fully contained in T, it has an edge f not in T.Analyzing the AlgorithmN = M+e-f is another spanning tree.Analyzing the AlgorithmN = M+e-f is another spanning tree.Claim: e < f, and therefore N < MAnalyzing the AlgorithmN = M+e-f is another spanning tree.Claim: e < f, and
View Full Document
Unlocking...