connectivity.ppt

Yang Juan jyang@tseg.org College of Computer Science Technology Beijing University of Posts Telecommunications College of Computer Science Technology, BUPT -- ? Copyright Yang Juan §9.4: Connectivity In an undirected graph, a path of length n from u to v is a sequence of adjacent edges going from vertex u to vertex v. A path is a circuit if u=v. A path pass through the vertices or traverses the edges. A path is simple if it contains no edge more than once. College of Computer Science Technology, BUPT -- ? Copyright Yang Juan Paths in Directed Graphs Same as in undirected graphs, but the path must go in the direction of the arrows. College of Computer Science Technology, BUPT -- ? Copyright Yang Juan Example College of Computer Science Technology, BUPT -- ? Copyright Yang Juan Paths in Acquaintanceship Graphs Paths in Collaboration Graphs Paths in the Hollywood Graph College of Computer Science Technology, BUPT -- ? Copyright Yang Juan Connectedness An undirected graph is connected if there is a path between every pair of distinct vertices in the graph. Example 5, p624 College of Computer Science Technology, BUPT -- ? Copyright Yang Juan Theorem: There is a simple path between every pair of distinct vertices of a connected undirected graph. College of Computer Science Technology, BUPT -- ? Copyright Yang Juan Connected component: connected subgraph Example 6, p625 Connected Components of Call Graph College of Computer Science Technology, BUPT -- ? Copyright Yang Juan A cut vertex or cut edge (bridge) separates 1 connected component into 2 if removed. Example 8,P626 College of Computer Science Technology, BUPT -- ? Copyright Yang Juan Directed Connectedness A directed graph is strongly connected if there is a path from a to b and from b to a whenever a and b are vertices in the graph. It is weakly connected if there is a path between every two vertices in the underlying undirected graph. Note strongly implies weakly but not