9.3-9.4

nullnull**CHAPTER 9 Graphs 9.1 Introduction to Graphs 9.2 Graph Terminology 9.3 Representing Graphs and Graph Isomorphism 图的示和同构 9.4 Connectivity 9.5 Euler and Hamilton Paths 9.6 Shortest Path Problems 9.7 Planar Graphs 9.8 Graph Coloring null**9.3 Representing Graphs and Graph Isomorphism Representing Graphs 图的表示Methods for representing graphs: Adjacency lists 邻接表 -- lists that specify all the vertices that are adjacent to each vertex该表规定与图的每个顶点邻接的顶点 Adjacency matrice 邻接矩阵 Incidence matrices 关联矩阵Adjacency lists邻接表**Adjacency lists邻接表例： 用邻接表描述所给的简单图Adjacency Matrices 邻接矩阵**若图里面有许多边，则把图表示成边表或邻接表，就不便于执行图的算法。为了简化计算，可用矩阵表示图。在这里将给出两种类型的常用的表示图的矩阵。一种类型是基于顶点的邻接关系，另一种类型是基于顶点与边的关联关系。Adjacency Matrices 邻接矩阵null**9.3 Representing Graphs and Graph Isomorphism 定义：假设 G = (V, E)是简单图 ，其中 |V|=n .假设把G的顶点任意地排列成 。对这个顶点表来说，G的邻接矩阵A是一个n×n的0－1矩阵，它满足这样的性质 aij = 1 if {vi, vj} is an edge of G, aij = 0 otherwise.null**〖Example 1〗 What is the adjacency matrix AG for the following graph G based on the order of vertices a, b, c, d ?Solution:Note: Adjacency matrices of undirected graphs are always symmetric.无向图的邻接矩阵总是对称的9.3 Representing Graphs and Graph Isomorphism null**注意： 1） 图的邻接矩阵依赖于所选择的顶点的顺序。因此带n个顶点的图有n!个不同的邻接矩阵，因为n个顶点有n!个不同的顺序。 2） 当图里的边相对少时，邻接矩阵是稀疏矩阵，即只有很少的非0项的矩阵。可以用特殊的方法来表示和计算这样的矩阵。null**9.3 Representing Graphs and Graph Isomorphism The adjacency matrix of a multigraph or pseudograph 伪图或多重图的邻接矩阵 邻接矩阵也可以表示带环和多重边的无向图.把顶点ai上的环表示成邻接矩阵（i,i）位置上的1。当出现多重边时候，邻接矩阵不再是0－1矩阵，这是因为邻接矩阵的第( i,j)项等于与{ai,aj}关联的边数。包括多重图与伪图在内的所有无向图都具有对称的邻接矩阵。 null**9.3 Representing Graphs and Graph Isomorphism 〖Example 2〗 What is the adjacency matrix AG for the following graph G based on the order of vertices a, b, c, d ?Solution:Note: For undirected multigraph or pseudograph , adjacency matrices are symmetric.无向多重图与伪图都具有对称的邻接矩阵null**9.3 Representing Graphs and Graph Isomorphism The adjacency matrix of a directed graph有向图的邻接矩阵 Let G = (V, E) be a directed graph with |V| = n. Suppose that the vertices of G are listed in arbitrary order as v1, v2, …, vn. 假设G=(V,E)是含n个顶点的有向图。若 是有向图任意的顶点序列。 The adjacency matrix A (or AG) of G, with respect to this listing of the vertices, is the nn zero-one matrix with 1 as its (i, j)th entry when there is an edge from vi to vj, and 0 otherwise.若有向图G=(V,E)从 有边，则它的矩阵在（i,j）位置上有1，否则为0 In other words, for an adjacency matrix A = [aij], aij = 1 if (vi, vj) is an edge of G, aij = 0 otherwise.null**9.3 Representing Graphs and Graph Isomorphism 〖Example 3〗 What is the adjacency matrix AG for the following graph G based on the order of vertices a, b, c, d ?Solution:null**9.3 Representing Graphs and Graph Isomorphism Question: What is the sum of the entries in a row of the adjacency matrix for an undirected graph? 对无向图来说，邻接矩阵每一行各个位置上数字之和代表什么？null**9.3 Representing Graphs and Graph Isomorphism Question: What is the sum of the entries in a row of the adjacency matrix for an undirected graph?对无向图来说，邻接矩阵每一行各个位置上数字之和代表什么？ The number of edges incident to the vertex i, which is the same as degree of i minus the number of loops at i. 与顶点i关联的边数等于顶点i的度减去在顶点i上的环数 For a directed graph?null**9.3 Representing Graphs and Graph Isomorphism Question: What is the sum of the entries in a row of the adjacency matrix for an undirected graph? The number of edges incident to the vertex i, which is the same as degree of i minus the number of loops at i. For a directed graph?对于有向图而言，邻接矩阵每一行各个位置上数字之和代表什么？代表该顶点的出度 deg+(vi) What is the sum of the entries in a column of the adjacency matrix for an undirected graph? The number of edges incident to the vertex i, which is the same as degree of i minus the number of loops at i. For a directed graph?对于有向图而言，邻接矩阵每一列各个位置上数字之和代表什么？代表该顶点的入度deg-(vi) null**9.3 Representing Graphs and Graph Isomorphism Incidence matrices 关联矩阵 设 G = (V, E) 是无向图.设. 是顶点而 是边。则相对于V和E的这个顺序的关联矩阵是n×m矩阵 null**9.3 Representing Graphs and Graph Isomorphism 〖Example 4〗 What is the incidence matrix M for the following graph G based on the order of vertices a, b, c, d and edges 1, 2, 3, 4, 5, 6?Solution:Note: Incidence matrices of undirected graphs contain two 1s per column for edges connecting two vertices and one 1 per column for loops. 在无向图中的关联矩阵中，每列中有两个1的表明这条边与这两个顶点相连接，每列有一个1的表明存在环null**9.3 Representing Graphs and Graph Isomorphism Isomorphism Of Graphs 图的同构定义：设G1= (V1, E1) 和G2= (V2, E2)是简单图，若存在一对一的和映上的从 V1 到V2 的函数f，且f具有这样的性质，对V1里所有的a 和 b来说，a和b在 G1里邻接，当且仅当 f(a)和 f(b)在 G2里邻接，就说G1和G2是同构的。这样的函数 f 称为同构. 换句话说，当两个简单图同构时，两个图的顶点之间具有保持邻接关系的一一对应。For example,null**9.3 Representing Graphs and Graph Isomorphism Question: 怎么判断两个简单图是否同构? 在两个带n个顶点的简单图顶点集之间有n！种可能的一一对应，通过检验每一种对应来看它是否保持邻接关系和不邻接关系是不可行的。 然而，可以通过说明两个简单图不具有同构的图所必须具有的性质来说明 它们不同构。把这样的性质称为对简单图的同构来说的不变量 invariants（不变量） -- things that G1 and G2 must have in common to be isomorphic.null**9.3 Representing Graphs and Graph Isomorphism Important invariants in isomorphic graphs:同构图中的重要不变量 相同的顶点数 有相同的边数 有相同的顶点度 if one is bipartite, the other must be if one is complete, the other must be if one is a wheel, the other must be etc. null**9.3 Representing Graphs and Graph Isomorphism 〖Example 5〗 Are the following two graphs isomorphic?Solution: They are isomorphic, because they can be arranged to look identical. You can see this if in the right graph you move vertex b to the left of the edge {a, c}. Then the isomorphism f from the left to the right graph is: f(a) = e, f(b) = a, f(c) = b, f(d) = c, f(e) = d. null**9.3 Representing Graphs and Graph Isomorphism 〖Example 6〗 Show that the following two graphs are isomorphic.Proof: Check invariants Try to find an isomorphism f Show that f preserves adjacency relationnull**9.3 Representing Graphs and Graph Isomorphism 〖Example 7〗 Determine whether the given pair of graphs is isomorphic?(1) (2) (3) null** 9.3 Representing Graphs and Graph Isomorphism Homework: null**CHAPTER 9 Graphs 9.1 Introduction to Graphs 9.2 Graph Terminology 9.3 Representing Graphs and Graph Isomorphism 9.4 Connectivity 连通性 9.5 Euler and Hamilton Paths 9.6 Shortest Path Problems 9.7 Planar Graphs 9.9 Graph Coloring null**9.4 Connectivity Paths 通路A path of length n in an undirected graph is a sequence of vertices v0, v1, . . . vn such that {v0, v1} , {v1, v2} , ..., {v n-1, vn} are n edges in the graph. The path is a circuit if the path begins and ends with the same vertex.一条通路在相同的顶点上开始和结束，则它是一条回路 A path is simple if it does not contain the same edge more than once.若通路中不重复地包含相同的边，则它是简单的 Note: There is nothing to prevent traversing an edge back and forth to produce arbitrarily long paths. This is usually not interesting which is why we define a simple path.null**9.4 Connectivity A path of length n in a directed graph is a sequence of vertices v0, v1, . . . vn such that (v0, v1) , (v1, v2) , ..., (vn-1, vn) are n directed edges in the graph. Circuit or cycle Simple pathCounting paths between vertices 统计顶点之间的通路 在一个图中两个顶点之间的通路的数目，可以用这个图的邻接矩阵来确定。null**9.4 Connectivity 【 Theorem 】设G是带有相对于顶点顺序v1, v2, . . . vn的邻接 矩阵A的图（允许带有向边或无向边，带多重边和环）。 从 vi到vj的长度为r的不同通路的数目等于Ar的第（i,j)项，其 中r是正整数。 Note: This is the standard power of A, not the Boolean product.Proof: Letbij: the number of different paths of length 2 from vi to vj (3) null**9.4 Connectivity〖Example 1〗How many paths of length 2 are there from v5 to v4? a54 in A2; 1 (2) The number of paths not exceeding 6 are there from v4 to v5? a45 in A+A2+A3+A4+A5+A6 ; 2 (3) The number of circuits starting at vertex v5 whose length is not exceeding 6?null**9.4 Connectivity Connectedness in undirected graphs 无向图的连通性 若无向图每一对不同的顶点之间都有通路，则该图称为连通的.  〖Example 2〗 Are the following graphs connected?Yes.No.null**9.4 Connectivity 【 Theorem 】 在连通无向图的每一对不同顶点之间都存在 简单通路Proof: Because the graph is connected there is a path between u and v. Throw out all redundant circuits to make the path simple. 因为图是连通的，所以u和v之间至少有1条通路。删除所有冗余的回路使得通路更短。 连通分支 For example,null**9.4 Connectivity 有时删除一个顶点和它所关联的边，就产生带有比原图更多的连通分支的子图。把这样的顶点称为割点（或节点）。从连通图里删除割点，就产生不连通的子图。 同理，把一旦删除就产生带有比原图更多的连通分支的子图的边称为割边或桥For example, （1）In the star network the center vertex is a cut vertex. All edges are cut edges.在星状网络中中心顶点是一个割点，其中所有的边都是割边null**9.4 Connectivity （2）There are no cut edges or vertices in the graph G above. Removal of any vertex or edge does not create additional components. null**9.4 Connectivity Connectedness in directed graphs 有向图的连通性强连通的：若每当a和b都是一个有向图里的顶点时，就有从a到b和从b到a的通路. 弱连通的：若在有向图的底图里，任何两个顶点之间都有通路 由定义可知：任何强连通有向图也是弱连通的。For example,Weakly connectedStrongly connectednull**9.4 Connectivity Paths and Isomorphism 通路与同构Idea: Some other invariants 一些其他的不变量 The number and size of connected components 连通分支的数目及其大小 Path Two graphs are isomorphic only if they have simple circuits of the same length. 两图同构只有当他们具有相同长度的简单回路。 Two graphs are isomorphic only if they contain paths that go through vertices so that the corresponding vertices in the two graphs have the same degree. 应用两图中相应顶点具有相同的度来判断两图的同构情况 We can also use paths to find mapping that are potential isomorphisms.null**9.4 Connectivity 〖Example 3〗 Are these two graphs isomorphic? Solution: No. Because the right graph contains circuits of length 3, while the left graph does not.null**HomeworkHomeworkP339 T10,T15**