欢迎来到天天文库
浏览记录
ID：44938257
大小：208.50 KB
页数：16页
时间：2019-11-05
《离散数学图论2》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、二、图的矩阵表示、欧拉图1．（无向图)关联矩阵M(G)=其中mij=vi与ej的关联次数(行为结点，列为边).(列元素之和为2)；,若,表明vi是孤立点;,即所有元素之和等于边数的2倍;设G=,具有性质：①②③④平行边的列的元素完全对应相同.2．(无向图)相邻矩阵A(G)=其中aij=vi与vj相关联的边的条数(行、列均为结点).；，表明vi是孤立点;设G＝,具有性质:①A(G)是对称矩阵；②3．(有向图)关联矩阵M(D)=其中(结点为行，边为列).(列元素之和为0）；③设D＝,具有性质：①②4．(有向图)邻接矩阵A(
2、D)=其中aij=邻接vi与vj的边的条数(与A(G)类似)(以行和列均为结点)设D=,具有性质：5．(有向图)可达矩阵P(D)=其中设D=，6．欧拉通路(回路)与欧拉图通过图G的每条边一次且仅一次，而且走遍每个结点的通路(回路)，就是欧拉通路(回路).存在欧拉回路的图就是欧拉图.注：（1）欧拉回路要求边不能重复，结点可以重复.笔不离开纸，不重复地走完所有的边，且走过所有结点，就是所谓的一笔画.（2）欧拉图或通路的判定1)无向连通图G是欧拉图G不含奇数度结点(G的所有结点度数为偶数):(定理1)2)非平凡连通图G含有欧拉通路
3、G最多有两个奇数度的结点；(定理1的推论)3)连通有向图D含有有向欧拉回路(即欧拉图)D中每个结点的入度＝出度4）连通有向图D含有有向欧拉通路D中除两个结点外，其余每个结点的入度＝出度，且此两点满足deg－(u)－deg＋(v)＝1.(定理2)
此文档下载收益归作者所有
