离散数学图论2

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,二、图的矩阵表示、欧拉图,1,（无向图,),关联矩阵,M,(,G,)=,其中,m,ij,=,v,i,与,e,j,的关联次数,(,行为结点，列为边,).,(,列元素之和为,2),；,若,表明,v,i,是孤立点,;,即所有元素之和等于边数的,2,倍,;,设,G,=,具有性质：,平行边的列的元素完全对应相同,.,2,(,无向图,),相邻矩阵,A,(,G,)=,其中,a,ij,=,v,i,与,v,j,相关联的边的条数,(,行、列均为结点,).,；,，表明,v,i,是孤立点,;,设,G,具有性质,:,A,(,G,),是对称矩阵；,3,(,有向图,),关联矩阵,M,(,D,)=,其中,(,结点为行，边为列,).,(,列元素之和为,0,）；,设,D,具有性质：,4,(,有向图,),邻接矩阵,A,(,D,)=,其中,a,ij,=,邻接,v,i,与,v,j,的边的条数,(,与,A,(,G,),类似,),(,以行和列均为结点,),设,D,=,具有性质：,5,(,有向图,),可达矩阵,P,(,D,)=,其中,设,D,=,，,6,欧拉通路,(,回路,),与欧拉图,通过图,G,的每条边一次且仅一次，而且走遍每个结点的通路,(,回路,),，就是欧拉通路,(,回路,).,存在欧拉回路的图就是,欧拉图,.,注：,（,1,）欧拉回路要求边不能重复，结点可以重复,.,笔不离开纸，不重复地走完所有的边，,且走过所有结点，就是所谓的,一笔画,.,（,2,）,欧拉图或通路的判定,1),无向连通图,G,是,欧拉图,G,不含奇数度结点,(,G,的所有结点度数为偶数,):(,定理,1),2),非平凡连通图,G,含有,欧拉通路,G,最多有两个奇数度的结点；,(,定理,1,的推论,),3),连通有向图,D,含有有向欧拉回路,(,即欧拉图,),D,中每个结点的入度出度,4,）连通有向图,D,含有有向欧拉通路,D,中除两个结点外，其余每个结点的入度出度，,且此两点满足,deg,(,u,),deg,(,v,),1.(,定理,2),