离散数学复件.pptVIP

第126页，共187页，星期日，2025年，2月5日设G为无向连通图，有n个结点和m条边。T为G的生成树，T有n个结点和n-1条边。所以要得到G的一棵生成树，必须删除G的m-(n-1)=m–n＋1条边。在树上的边枝n-1条不在树上的边弦m–n＋1条秩树换成森林余圈秩圈秩给定树基本回路第127页，共187页，星期日，2025年，2月5日有向树一个结点的入度为0，其余结点的入度均为1的弱连通有向图称为有向树。在有向树中，入度为0的结点称为根，出度为0的结点称为叶，出度大于0的结点称为分支结点，从根至任意结点的距离称为该结点的级，所有结点的级的最大值称为有向树的高度。第128页，共187页，星期日，2025年，2月5日有向树的归纳定义也可用归纳法定义有向树。定义7.6.9有向树归纳定义如下：i) ? ii) 第129页，共187页，星期日，2025年，2月5日有向森林每个弱分支都是有向树的有向图称为有向森林。第130页，共187页，星期日，2025年，2月5日m元有向树设m∈N，D为有向树。i)?如果D的所有结点出度的最大值为m，则称D为m元有向树。ii)如果对于m元有向树D的每个结点v皆有dＤ＋（v）＝m或dＤ＋（v）=0，则称D为完全m元有向树。第131页，共187页，星期日，2025年，2月5日定理7.4.2设G＝〈Ｖ，Ｅ，Ψ〉为连通无向图且v1，v2∈Ｖ，则G有一条从v1至v2的欧拉路径iffG恰有两个奇结点v1和v2。第94页，共187页，星期日，2025年，2月5日根据哥尼斯堡桥问题画出的图不是欧拉图，因此不存在欧拉闭路，即哥尼斯堡桥问题没有解。第95页，共187页，星期日，2025年，2月5日一笔画第96页，共187页，星期日，2025年，2月5日周游世界的数学游戏Hamilton(哈密顿)十九世纪 爱尔兰数学家 正十二面体， 二十个顶点， 三十条棱 城市 路问：找一条从某城市出发，经过每个城市恰好一次，并且最后回到出发点的路线。等价于：在图中找出一条包含所有结点的闭路，并且，除始点和终点重合外，这条闭路所含结点是互不相同的。根据定理7.3.6，这条闭路的所有结点和边组成了一个回路。第97页，共187页，星期日，2025年，2月5日Hamilton回路如果回路(有向回路)C是图G的生成子图，则称C为G的Hamilton回路（Hamilton有向回路）。图G中包含它的所有结点的基本路径称为G的Hamilton路径。有Hamilton回路（Hamilton有向回路）的图称为Hamilton图（Hamilton有向图）。第98页，共187页，星期日，2025年，2月5日4图的矩阵表示定义4.1设G=?V,E?是一个简单图，V=?v1,v2,…,vn?A(G)=(aij)n×n其中：i,j=1,…,n称A(G)为G的邻接矩阵。简记为A。第99页，共187页，星期日，2025年，2月5日例如图9.22的邻接矩阵为：第100页，共187页，星期日，2025年，2月5日又如图9.23(a)的邻接矩阵为：第101页，共187页，星期日，2025年，2月5日邻接矩阵具有以下性质：①邻接矩阵的元素全是0或1。这样的矩阵叫布尔矩阵。邻接矩阵是布尔矩阵。②无向图的邻接矩阵是对称阵，有向图的邻接矩阵不一定是对称阵。③邻接矩阵与结点在图中标定次序有关。例如图9.23(a)的邻接矩阵是A(G)，若将图9.23(a)中的接点v1和v2的标定次序调换，得到图9.23(b)，图9.23(b)的邻接矩阵是A′(G)。第102页，共187页，星期日，2025年，2月5日考察A(G)和A′(G)发现，先将A(G)的第一行与第二行对调，再将第一列与第二列对调可得到A′(G)。称A′(G)与A(G)是置换等价的。一般地说，把n阶方阵A的某些行对调，再把相应的列做同样的对调，得到一个新的n阶方阵A′，则称A′与A是置换等价的。可以证明置换等价是n阶布尔方阵集合上的等价关系。虽然，对于同一个图，由于结点的标定次序不同，而得到不同的邻接矩阵，但是这些邻接矩阵是置换等价的。今后略去结点标定次序的任意性，取任意一个邻接矩阵表示该图。