离散数学13教案讲稿

教研室：数学教育 教师姓名：季丹丹 授课时间:第13次

课程名称 授课内容 教学目的 教学重点 教学难点 教具和媒体使用 教学方法 离散数学 授课专业和班级 09师范，信息与计算科学 授课学时 2学时 5.2 通路、回路与连通性 掌握图的通路和回路的概念、无向图和有向图的连通性Menger定理；知道什么是二部图 通路和回路的概念、无向图和有向图的连通性 图的连通性的判断 黑板 讲授法，练习法，讨论法 包括复习旧课、引入新课、重点难点讲授、作业和习题布置、问题讨论、归纳总结及课后辅导等内容 引入新课： 重点难点讲授： 时间分配(90分钟) 教 学 过 程 1通路和回路 2无向图的连通性 3、无向图的连通程度 4 有向图的连通性 5 Menger定理 6、二部图的概念 练习 作业和习题布置 归纳总结 板 书 设 计 讲授新 5.2 通路、回路与连通性 1通路和回路 4 有向图的连通性 2无向图的连通性 5 Menger定理 3、无向图的连通程度 6、二部图的概念 拓展内容 课后总结 教研室主任签字

讲 稿 备讲 授 内 容 注 5.2 通路、回路与连通性 1通路和回路 定义1（1）无向图G的一个有限非空序列=v0e1v1e2v2ekvk称为图G的一条从顶点v0到vk的通路（或途径）, 若的项交替地为顶点和边且满足，ei的端点是vi1和vi（1ik），并称v0和vk分别为通路的起点和终点，整数k称为的长度．特别当v0vk时，称为回路. （2）若通路的边e1e2,ek互不相同，则称为简单通路（或迹），若回路的边互不相同，则称为简单回路（或闭迹）. （3）若通路的顶点v0,v1,,vk互不相同（导致所有边互不相同），则此通路称为初级通路（或路径）．又若回路内部顶点互不相同（边相同？），则称回路为初级回路（或圈）．长为k的圈称为k圈（按k奇偶性分奇偶圈），3圈常称为三角形． 图5-2-1指出了一个图的一条通路、一条简单通路、初级通路、简单回路和一个圈． u 通路：uavfyfvgyhwbv a e f 简单通路：wcxdyhwbvgy y e9g 初级通路：xcwhyeuav b d h 简单回路：uavbwhyfvgyeu x c 图5-2-1 w 圈：uavbwhyeu 注 将初级回路看成初级通路的特殊情况，应用中要注意区分，长为1的圈只能由环生成，长为2的圈只能由平行边生成，故在简单无向图中，圈的长度至少为3． 定义2 有向图D的一个有限非空序列=v0e1v1e2v2ekvk称为D的一条从顶点v0到vk的有向通路（或途径）, 要求同无向通路。 同无向图，在有向图中，可以类似地定义有向路，有向回路，有向圈和有向环游等． 说明：回路为通路的特殊情况．说通路时，可能是回路．但初级通路一般不是初级回路的情况． 利用通路的概念容易解决一个古老的著名问题． 例1 渡河问题：一个摆渡人要把一只狼、一只羊和一捆菜运过河去．由于船很小，每次摆渡

将它们运过河去？ 解 用F表示摆渡人，W表示狼，S表示羊，C表示菜． 若用FWSC表示人和其他三样东西在河的原岸的状态，这样原岸全部可能出现的状态为 以下16种： FWSC FWS FWC FSC WSC FW FS FC WS WC SC F W S C  这里表示原岸什么也没有，即人、狼、羊、菜都已运到对岸去了． WSC、FW、FC、WS、 根据题意我们知道，这16种情况中有6种是不允许的，它们是： SC、F．如FC表示人和菜在原岸，而狼和羊在对岸，这当然是不行的．因此，允许出现的 情况只有10种． 以这10种状态为顶点，以摆渡前原岸的一种状态与摆渡一次后仍在原岸的状态所对应的 顶点之间的连线为边做有向图G，如图5-2-2所示． W FWS FWSC WC FWC S FS C FSC 图5-2-2 图中给出了两种方案，方案为图5-2-2中的从FWSC到的不同的初级通路，它们的长 度均为7，按图中所指的方案，摆渡人只要摆渡7次就能将它们全部运到对岸，并且羊和菜完 好无损． 定理1 在n阶图G中，若从顶点vi到vj（vivj）存在通路，则从vi到vj存在长度小于或 等于n1的通路． 证明 设v0e1v1e2elvl(v0vi,vlvj)为G中一条长度为l的通路，若ln1，则 满足要求，否则必有l1n，即上的顶点数大于G中顶点数，于是必存在 k,s,0ksl，使得vsvk，即在上存在vs到自身的回路Csk，在上删除Csk上的一 切边及除vs外的一切顶点，得'v0e1v1e2vkes1elvl，'仍为vi到vj的通路，且长度至 少比减少1，若'还不满足要求，则重复上述过程，由于G是有限图，经过有限步后，必 得到vi到vj长度小于或等于n1的通路． 推论 在n阶图G中，若从顶点vi到vj（vivj）存在通路，则vi到vj一定存在长度小于或 等于n1的初级通路． 人至多只能带一样东西．另外，如果人不在旁时，狼就要吃羊，羊就要吃菜．问这人怎样才能

证明：由定理1，本推论显然成立． 类似可证明下面的定理和推论． 定理2 在n阶图G中，若存在vi到自身的回路，则一定存在vi到自身长度小于等于n的回路． 推论 一个n阶图G中，若存在vi到自身的简单回路，则一定存在长度小于等于n的初级回路． 例2 无向完全图K3的顶点依次为a,b,c，在定义意义下K3有多少个不同的圈？ 解 在同构意义下，K3中只有一个长为3的圈．但在定义意义下，不同起点（终点）的圈是不同的，顶点间排列顺序不同的圈也看成是不同的，因而K3中有6个不同长为3的圈，分别为：abca,acba,baca,bcab,cabc,cbac．如果只考虑起点（终点）的差异，而不考虑顺时针逆时针的差异，应该有3种不同的圈，当然它们的长度都是3． 2无向图的连通性 定义3 在无向图G中，对于它的两个顶点u和v，如果u和v之间存在通路，则称顶点u和v是连通的，记为u~v．对任意顶点u，规定u~u． 定理3 无向图中顶点之间的连通关系是等价关系． 证明 易，请同学们自证 定义4 若G的任意顶点u和v，都有u~v，称G是连通图，否则称G是非连通图（分离图）． 例 无向完全图Kn(n1)都是连通图，而多于一个顶点的零图都是非连通图． 定义5 设u,v为无向图G中任意两个顶点，若u~v，称u,v之间长度最短的通路为u,v之间的短程线，其长称u,v之间的距离，记作d(u,v)．当u,v之间不连通时，规定d(u,v)． 思考 考虑此距离是否具有正定性、对称性，三角不等式性质？ 例 在完全图Kn(n2)中，任两个顶点之间的距离是1，而在n零图Nn(n2)，任何两个顶点之间的距离都为． 3、无向图的连通程度． 等价关系可以导致集合的划分，无向图中连通关系是等价关系，因此任何无向图中顶点集都存在一种划分，使得每个划分块中的顶点都彼此连通，不同划分块中的顶点都不连通． 定义6（连通分支） 在一个无向图G中，存在V的一个分类，把V分成非空子集V1，V2，…，V, 使得两个顶点u和v是连通的当且仅当它们属于同一子集Vi．子图G[V1]，G[V2]，…，G[V]，称为G的连通分支．用(G)表示G中的连通分支个数． 说明 易见G是连通的当且仅当G只有一个分支． 图5-2-3画出了连通的和不连通的图．

（1） （2） 图5-2-3 （1）一个连通图 （2）有三个分支的不连通图 下面给出点割集和边割集的概念． 定义7（点割集） 设无向图GV,E， （1）若存在顶点子集V'V，使得删除V（将V中的顶点及其关联的边都删除）后，所得子图GV的连通分支数与G的连通分支数满足(GV)(G)，而删除V的任何真子集V后，(GV)(G)，则称V为G的一个点割集．特别地，只有一个顶点的点割集，称该点割集的顶点为割点． （2）若存在顶点集EE，使得删除E（将E中的边都删除）后，所得子图GE的连通分支数与G的连通分支数满足(GE)(G)，而删除E的任何真子集E后，都有(GE)(G)，则称E为G的一个边割集，同样对于一个边叫割边或桥． 例3 如在图5-2-4中， 割点：v2，v6； 点割集：{v3,v5} 边割集：{e3,e4}、{e4,e5}、 e1 v3 u e6 v1 v5e7 e9 v7e5v2 e2 e8 {e1,e2,e3}、{e1,e2,e4}、{e9}； 桥：{e9} e4ev4图5-2-4 定理4 无向图G的一条边e是割边当且仅当e不包含在G的任意圈中． 证明 设e是G的割边，由于(Ge)(G)，所以存在G的顶点u和v，它们在G中连通但在Ge中不连通．因此在G中必有某条(u,v)路p经过e．设x和y是e的端点，并且在p上x前于y，在Ge中，u被p的一节连到x,y被p的一节连到v．若e在某圈C中，则在Ge中x和y将被路C-e所连．于是，u和v在Ge中就连通了，导致矛盾． 反之，假设e=xy不是G的割边，则(Ge)=(G)．由于在G中存在一条(x,y)路（即，所以x和y都在G的同一个分支中．由此推知：x和y在Ge的同一个分支中，从xy）而在Ge中存在一条(x,y)路p，于是e就位于G的圈P+e中了． 定义8（连通度） 设无向图G为连通图, 定义

(G)=min{|V1|V1是G的点割集, 或使G-V1为平凡图} 称(G)是G的连通度 (或点连通度)．若G为非连通图，则规定(G)=0．对于任意图G，若有(G)k，则称G为k-连通的． 定义9（边连通度） 设无向图G是非平凡的连通图，令 (G) =min{|E1|E1是G的边割集} 则称(G)为G的边连通度．若G为平凡图或非连通图，则规定(G)=0．对于任意图G若有(G)r，则称G为r边-连通的． 例4（1）在图5-2-4中，它的点连通度为1，它是1-连通图，但不是2-连通图；它的边连通度为1，它是1边-连通图，但不是2边-连通图． （2）彼得森图的点连通度为3，它是1-连通图、2-连通图、3-连通图，但不是4-连通图；它的边连通度为3，它是1边-连通图、2边-连通图、3边-连通图，但不是4边-连通图． 定理5 对任何无向图G，均有(G)≤(G)≤(G)． 证明 若G是平凡的，则(G)0(G)．否则，与(G)度顶点相关联的连杆集构成了G的一个(G)边割集，由此推知：(G)≤(G)． 对(G)用归纳法来证明(G)≤(G)．当(G)=0时命题是正确的．现在假定命题对一切边连通度小于k的图均成立，并设G是(G)=k0的图。根据归纳法原理，结论成立． 注意：定理5中不等式常是严格成立的．例，图5-2-5中的图G有(G)=2, (G)=3, (G)=4． 4 有向图的连通性 图5-2-5 定义10若有向图D中存在有向通路(u,v)，则称u在D可达v．称它们在D中是双向连通的，若它们是互相可到达的，同无向图中连通，双向连通也是一个等价关系．根据此关系确定的V(D)的分类(V1,V2,,Vm)所导出的有向子图D[V1],D[V2],,D[Vm]，称D的强连通分支（或双向分支）．有向图D称为强连通的(或双向连通的)，如果D中任意两个顶点都是双向可达的（即恰有一个双向分支）；若D中任何一对顶点，至少有一个顶点是从另一个顶点可达的，则称该图为单向连通的（或单侧连通的）；如果D的基础图是连通的，则称该D是弱连通的．如图5-2-6（1）不是强连通的，因为它有如图5-2-6（2）所示的三个连通分支．图5-2-7给出．

（1）有向图D （2）D的三个强连通分支 （1）弱连通 （2）单向连 （3）强连通 图5-2-7 图5-2-6 关于有向图的三种连通性，显然有下面的结论： 强连通有向图必是单向连通的，而单向连通有向图也一定是弱连通的．但结论的逆命题不成立． 定理6 一个有向图D是强连通的充要条件是D有一条有向回路，它经过每一顶点至少一次． 证明 充分性．如G中有一条有向回路，经过每一点至少一次，则G中任意两点u,vV，u可以沿着该有向回路的一部分的而到达v, 则G是强连通图． 必要性．设图G是强连通图, 任取u, vV，则u→v有有向路，v→u也有有向路，则u→v→u构成了一个有向回路，如果该有向回路没有包含w, 而u→w, w→u均有有向路，则u→v→u→w→u又是一个有向回路，如此一 直下去可以将图中所有的点均包含进去，进而得到一条遍历所有顶点的有向回路． 5 Menger定理 对于图G中的一族路，如果G中没有这样的顶点，使得它是这族路中一条以上的路的内部顶点，则称这族路为内部不相交的．下述定理是由Whitney(1932)提出的． 定理7 一个v3的无向图G是2-连通的，当且仅当G的任意两个顶点至少被两条内部不相交的路所连． 证明 若G的任意两个顶点至少被两条内部不相交的路所连，则显然，G是连通的，并且没有割点．因此G是2-连通的． 反之，设G是2-连通图．对u和v之间的距离d(u,v)用归纳法来证明：任意两个顶点u和v至少被两条内部不相交的路所连． 首先假设d(u,v)1．由于G是2-连通的，因此边uv不是割边，由定理5.2.4，它包括在某个圈中．由此推出：u和v被G中两条内部不相交的路所连． 现在假设对于距离小于k的任意两个顶点定理均成立，并且设d(u,v)k2．考察长为k的一条(u,v)路，并且设w是该路上v前面的那个顶点．因为d(u,w)k1，由归纳法假设可知：在G中有两条内部不相交的(u,w)路P和Q．又因为G是2-连通的，所以Gw是连通的，并且包含一条u,w路p'．设x是在p'中又在PQ中的最后一个顶点（见图5-2-8）．由于u在PQ中，这样的顶点x是存在的；我们不排除x=u的可能性． 不失一般性，可假定x在p中．于是G有两条内部不相交的(u,v)路，一条由p的一节（从u到x）和p的一节（由x到v）联合组成，另一条由Q和路wv组成． x （6） u w v

注：定理7可推广到k-连通图，即为著名的Menger定理：一个vk1的图G是k连通的当且仅当G的任意两个相异顶点至少被k条内部不相交的路所连． 对于边连通性也有类似的定理：图G是k边连通的当且仅当G的任意两个相异顶点至少由k条边不重的路所连． 6、二部图的概念． 定义11 设GV,E为一个无向图，若能将V分成V1和V2 (V1V2V,V1V2)，使得G中的每条边的两个端点都是一个属于V1，另一个属于V2，则称G为二部图（或称二分偶图或偶图等），称V1和V2为互补顶点子集．常将二部图G记为． 例如：n(n2)阶零图为二部图． 特别地，若G是简单二部图，V1中每个顶点均与V2中所有顶点相邻，则称G为完全二部图，记为Kr,s，其中r＝|V1|，s＝|V2|． 图5-2-9中所示各图都是二部图，其中（1），（2），（3）为K6的子图，（3）为完全二部图K3,3画成与其同构的形式（5），（4）是K5的子图，它是完全二部图K2,3，K2,3常画成（6）的形式． （4） （5） （6） （1） （2） （3） v 定理7 n(n2)阶无向图G是二部图当且仅当G中无奇圈． 证明留作练习。 36作业：P53 归纳总结：深刻理解通路与回路的定义及分类，掌握通路与回路的表示方法.深刻理解图的连通性的相关概念，能熟练的判断图的连通性. 参考书目： 1、离散数学。王岚主编。北京：清华大学出版社,2011 2、离散数学。耿素云，屈婉玲编著。高等教育出版社， 3、离散数学学习辅导，李树平主编。北京：清华大学出版社,2011。 4、离散数学（第五版）。Richard Johnsonbaugh著，石纯一，金涬译。人民邮电出版社，2003.