北京邮电大学计算机学院 离散数学 10.1~10.2 graphs.ppt

College of Computer Science Technology, BUPT -- ? Copyright Yang Juan Subgraphs A subgraph of a graph G=(V,E) is a graph H=(W,F) where W?V and F?E. A subgraph H of G is a proper subgraph of G if H ? G. G H College of Computer Science Technology, BUPT -- ? Copyright Yang Juan College of Computer Science Technology, BUPT -- ? Copyright Yang Juan Graph Unions The union G1?G2 of two simple graphs G1=(V1, E1) and G2=(V2,E2) is the simple graph (V1?V2, E1?E2). a b c d e a b c d f ? College of Computer Science Technology, BUPT -- ? Copyright Yang Juan Homework §10.2 12, 42, 64, 72 * College of Computer Science Technology, BUPT -- ? Copyright Yang Juan Homework §10.1 22,34 College of Computer Science Technology, BUPT -- ? Copyright Yang Juan §10.2 Graph Terminology You need to learn the following terms: Adjacent, connects, endpoints, degree, initial, terminal, in-degree, out-degree, complete, cycles, wheels, n-cubes, bipartite, subgraph, union. College of Computer Science Technology, BUPT -- ? Copyright Yang Juan Adjacency Let G be an undirected graph with edge set E. Let e?E be (or map to) the pair {u,v}. Then we say: u, v are adjacent / neighbors / connected. Edge e is incident with vertices u and v. Edge e connects u and v. Vertices u and v are endpoints of edge e. Neighborhood The set of all neighbors of a vertex v of G = (V ,E), denoted by N(v), is called the neighborhood of v. If A is a subset of V , we denote by N(A) the set of all vertices in G that are adjacent to at least one vertex in A. So, College of Computer Science Technology, BUPT -- ? Copyright Yang Juan College of Computer Science Technology, BUPT -- ? Copyright Yang Juan Degree of a Vertex Let G be an undirected graph, v?V a vertex. The degree of v, deg(v), is its number of incident edges. (Except that any self-loops are counted twice.) A vertex with degree 0 is called isolated. A vertex of degree 1 is called pendant. College of Computer Science Technology, BUP