离散数学讲义 Graphs (2).pptVIP

Graphs (2) Wu Gang School of Software, SJTU Representing Graphs Adjacency lists Simple graph Directed graph vertex Adjacency vertices a b c d e b,c,e a a,d,e c,e a,c,d a e b c d Representing Graphs Adjacency lists Simple graph Directed graph vertex Adjacency vertices a b c d e a,b,c,e d e c a e b c d Representing Graphs Adjacency Matrices Simple graphs (0-1 matrix, symmetric, diagonal?) Multigraph and pseudographs (symmetric) Representing Graphs Adjacency Matrices Directed graphs (0-1 matrix) Directed Multigraphs Representing graphs Incidence matrix (undirected graph) Connectivity Path Undirected graph G A path of length n from u to v in G is a sequence of n edges e1,…,en of G such that f(e1)={x0,x1}, f(e2)={x1,x2}, f(en)={xn-1,xn}, where u=x0,v=xn If G is simple, can be denoted as x0,x1,…,xn If u=v, the path is a circuit Simple path or circuit: if it does not contain the same edge more than once A path of length zero consists of a single vertex Connectivity (Path) Directed graph Directed multigraph A path of length n from u to v in G is a sequence of n edges e1,…,en of G such that f(e1)=(x0,x1), f(e2)=(x1,x2), f(en)=(xn-1,xn), where u=x0,v=xn If no mutliphe edges, can be denoted as x0,x1,…,xn If u=v, the path is a circuit Simple path or circuit: if it does not contain the same edge more than once Connectedness in undirected graph Definition An undirected graph is called connected if there is a path between every pair of distinct vertices of the graph Theorem There is a simple path between every pair of distinct vertices of a connected undirected graph Connectedness in undirected graph Connected component of the graph Disjoint connected subgraphs (has no vertex in common) Cut vertices (articulation points) Removal of such a vertex produces more connected components Cut edges (bridge) Connectedness in directed graph Definition 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 A direct