离散数学第14章——图论.ppt

1．9阶无向图G中，每个顶点的度数不是5就是6. 证明G中至少有5个6度顶点或至少有6个5度顶点. 证 关键是利用握手定理的推论. 方法一：穷举法 设G中有x个5度顶点，则必有(9?x)个6度顶点，由握手定理推论可知，(x,9?x)只有5种可能：(0,9), (2,7), (4,5), (6,3), (8,1）它们都满足要求. 方法二：反证法 否则，由握手定理推论可知，“G至多有4个5度顶点并且至多有4个6度顶点”，这与G是 9 阶图矛盾. 2．数组2, 2, 2, 2, 3, 3能简单图化吗？若能，画出尽可能多的非同构的图来. 只要能画出6 阶无向简单图，就说明它可简单图化. 下图的4个图都以此数列为度数列，请证明它们彼此不同构，都是K6的子图. 用扩大路径法证明. 情况一：?? ? ?+. 证明D中存在长度 ? ??+1的圈. 设 ? = v0v1…vl为极大路径，则l ? ??(为什么?).由于d?(v0)? ??，所以在 ? 上存在 3．设D=V,E为有向简单图，已知 ?(D) ? 2，?+(D)0，??(D)0，证明D中存在长度 ? max{?+,??}+1的圈. 为D中长度 ? ??+1的有向圈 邻接到v0，于是 情况二：?+ ? ??，只需注意d+(vl) ? ? + . 4．有向图D如图所示，回答下列诸问： (1) D中有几种非同构的圈？ (2) D中有几种非圈非同构的简单回路？ (3) D是哪类连通图? (4) D中v1到v4长度为1,2,3,4的通路各多少条？其中几条是非初级的简单通路？ (5) D中v1到v1长度为1,2,3,4的回路各多少条？讨论它们的类型. (6) D中长度为4的通路（不含回路）有多少条？ (7) D中长度为4的回路有多少条？ (8) D中长度?4的通路有多少条？其中有几条是回路？ (9) 写出D的可达矩阵. (1) D中有3种非同构的圈，长度分别为1,2,3，请画出它们的图形. (2) D中有3种非圈的非同构的简单回路，它们的长度分别为 4,5,6. 请画出它们的图形来. (3) D是强连通的（为什么？） 为解(4)—(8)，只需先求D的邻接矩阵的前4次幂. (4) v1到v4长度为1,2,3,4的通路数分别为0,0,2,2. 其中只有长度为4的两条是非初级的简单通路（定义意义下），见下图所示. (5) v1到v1长度为1,2,3,4的回路数分别为1,1,3,5. 其中长度为1的是初级的(环)；长度为2的是复杂的；长度为3的中有1条是复杂的，2条是初级的；长度为4的有1条是复杂的，有4条是非初级的简单回路. 请在图中行遍以上各回路. (6) 长度为4的通路(不含回路)为33条. (7) 长度为4的回路为11条. (8) 长度?4的通路88条，其中22条为回路. (9) 4?4的全1矩阵. 推论 在一个n 阶图G中，若存在 vi 到自身的简单回路，则一定存在长度小于或等于n 的初级回路. 1.无向图的连通性 (1) 顶点之间的连通关系：G=V,E为无向图 ① 若 vi 与 vj 之间有通路，则 vi?vj ② ?是V上的等价关系 R={u,v| u,v ?V且u?v} (2) G的连通性与连通分支 ① 若?u,v?V，u?v，则称G连通 ② V/R={V1,V2,…,Vk}，称G[V1], G[V2], …,G[Vk]为连通分支，其个数 p(G)=k (k?1)； k=1，G连通 第三节 图的连通性 (3) 短程线与距离 ① u与v之间的短程线：u?v，u与v之间长度最短的通路 ② u与v之间的距离：d(u,v)——短程线的长度 ③ d(u,v)的性质： d(u,v)?0, u?v时d(u,v)=? d(u,v)=d(v,u) d(u,v)+d(v,w)?d(u,w) 2. 无向图的连通图 （1）删除顶点及删除边 G?v ——从G中将v及关联的边去掉 G?V?——从G中删除V?中所有的顶点 G?e ——将e从G中去掉 G?E?——删除E?中所有边 （2）点割集与边割集 点割集与割点 定义14.16 G=V,E, V??V V?为点割集——p(G?V?)p(G)且有极小性 v为割点——{v}为点割集 定义14.17 G=V,E, E??E E?是边割集——p(G?E?)p(G)且有极小性 e是割边（桥）——{e}为边割集 例3 {v1,v4}，{v6}是点割集，v6是割点. {v2,v5}是点割集吗？{e1,e