英语翻译Let G be a graph with vertices v1,v2,…,vm and edges e1,e

英语翻译
Let G be a graph with vertices v1,v2,…,vm and edges e1,e2,…,en.It is sometimes practical,especially for computational reasons,to represent G by a matrix.Note that the edges of G can be represented by an n×2 integer matrix B where each row of B denotes edge of G,e.g.the row (3 ,4) would denote the edge (v3,v4).This edge matrix B does not completely describe.G unless we are also given the number m of vertices of G..We discuss two other widely used matrix representations of G.
(1) Adjacency matrix.Let A = (aij) be the m×m matrix defined by
Then A is called the adjacency matrix of G..Observe that aij =aji; hence A is a symmetric matrix.(We define an adjacency matrix for a multigraph by letting aij denote the number of edges{ vi,vj}.)
(2) Incident matrix.Let M = (mij) be the m×n matrix defined by
Consider,for example,the graph in Fig.5-12.Its edge matrix B,adjacency matrix A,and incidence matrix M follow.For easy reading,we have labeled the rows and columns of A and M by the corresponding vertices and edges.
Although the edge matrix B of a graph G is the most compact representation,it is not always the most useful.In view of the following theorem,the adjacency matrix is very useful in deciding questions of connectivity.
Theorem:Let A be the adjacency matrix of a graph G with m vertices where m>1.Then the ij entry of the matrix An gives the number of walks of length n from the vertex vi to the vertex vj.
(An analogous theorem,for directed graphs (Theorem 7.8) is stated and proved in Chapter 7.)
Since G has m vertices,any path from vi to vj,must have length m-1 or less.Hence the matrix A+A2+...+Am-1 can have a zero ij entry only if there is no path from vi to vj.
By the connection matrix of a graph G with m vertices,we mean the m×m matrix C = (cij).where
Note that G is connected if and only if C has no zero entry.The above discussion shows that C and the matrix A+A2+...+Am-1 have the same zero entries off the main diagonal.

让G是与端点v1, v2, …, vm的一张图表并且渐近e1, e2, …, en. 它特别是为计算原因是有时实用的,由矩阵代表G. 注意G边缘可以由B每行表示G边缘的n×2整数矩阵B代表,即行(3, 4)将表示边缘(v3, v4). 这个边缘矩阵B不完全地描述. G,除非也给我们G.端点的数量m. 我们谈论G.的其他二个用途广泛的矩阵表示.
(1)毗邻物矩阵. 让A = (aij)是被定义的m×m矩阵
Then A称G.毗邻物矩阵. 观察那aij =aji; 因此A是一个对称矩阵. (我们通过让aij表示边缘{vi, vj的}数量定义了小型旋转式印刷机的毗邻物矩阵.)
(2)事件矩阵. 让M = (mij)是被定义的m×n矩阵
Consider,例如,在Fig.5-12的图表. 它的边缘矩阵B,毗邻物矩阵A和关联矩阵M跟随. 为容易的读书,我们由对应的端点和边缘标记了A和M的行和专栏.
图表G边缘矩阵B是最紧凑的表示法的Although,它总是不是最有用的. 由于以下定理,毗邻物矩阵是非常有用的在连通性的决定的问题.
Theorem ： 让A是一张图表G的毗邻物矩阵与m>1.Then的矩阵ij词条给长度n步行的数量从端点vi的端点vj的m端点的.
(一个近似定理,为了被指挥的图表(定理7.8)在第7.章)陈述并且被证明
Since G有m端点,所有道路从vi向vj,必须有长度m-1或较少. 因此矩阵A+A2+… 只有当没有道路从vi对vj, +Am-1可能有零的ij词条.
By一张图表G的连接矩阵与m端点的,我们意味m×m矩阵C = (cij). 那里
Note G被连接,如果,并且,只有当C没有零的词条. 上述讨论显示那C和矩阵A+A2+… +Am-1有同样零的词条主要对角线.