10 几种特殊的图.ppt

几种特殊的图 何英华 hyh@tju.edu.cn 目录 二部图 欧拉图 哈密顿图 平面图 二部图 设G=V,E为一个无向图，若能将V分成V1和V2（V1∪V2=V,V1∩V2=?），使得G中的每条边的两个端点都是一个属于V1，另一个属于V2，则称G为二部图（或称二分图，偶图等），称V1和V2为互补顶点子集，常将二部图G记为V1 ,V2 ,E。 注意，n阶零图为二部图。 完全二部图 若G是简单二部图，V1中每个顶点均与V2中所有顶点相邻，则称G为完全二部图，记为Kr,s，其中r=|V1|,s=|V2|。 在完全二部图Kr,s中，它的顶点数n=r+s，边数m=r·s。 二部图的判别 定理：一个无向图G=V,E是二部图当且仅当G中无奇数长度的回路。 必要性。若G中无回路，结论显然成立。若G中有回路，只需证明G中无奇圈。 充分性。不妨设G为连通图，否则可对每个连通分支进行讨论。设v0为G中任意一个顶点，令 V1={v|v∈V(G)∧d(v0,v)为偶数} V2={v|v∈V(G)∧d(v0,v)为奇数} 　易知，V1≠?,V2≠?,V1∩V2=?，V1∪V2=V(G)。下面只要证明V1中任意两顶点不相邻，V2中任意两点也不相邻。 例题 判别以下图中哪些是二部图 例题 今有a,b,c,d,e,f,g等7个人，已知a会讲英语， b会讲英语和汉语，c会讲英语、意大利语和俄语，d会讲日语和汉语，e会讲德语和意大利语，f会讲法语、日语和俄语，g会讲法语和德语，试问能否从这7个人中找出7名翻译，使得每人翻译一种语言？ 例题 今有a,b,c,d,e,f,g等7个人，已知a会讲英语， b会讲英语和汉语，c会讲英语、意大利语和俄语，d会讲日语和汉语，e会讲德语和意大利语，f会讲法语、日语和俄语，g会讲法语和德语，试问能否从这7个人中找出7名翻译，使得每人翻译一种语言？ a b c d e f g 英 汉 意 俄 日 德 法 例题 a b c d e f g 英 汉 意 俄 日 德 法 目录 二部图 欧拉图 哈密顿图 平面图 七桥问题 1736年，欧拉提出“七桥问题”，图论诞生 一笔画 欧拉图 欧拉通路: 经过图中所有边的简单通路 欧拉回路: 经过图中所有边的简单回路 欧拉图: 有欧拉回路的图 在下面各图中， 哪些存在欧拉回路？ 哪些存在欧拉通路？ 在下面各图中，图1,4中存在欧拉回路，是欧拉图，图2中存在欧拉通路，但不存在欧拉回路，不是欧拉图。图3,5,6中既没有欧拉回路，也没有欧拉通路，不是欧拉图。 无向欧拉图的判别 定理：无向图G具有欧拉通路，当且仅当G是连通图且无奇度顶点或有两个奇度顶点。若无奇度顶点，则通路为回路，若有两个奇度顶点，则它们是每条欧拉通路的端点。 推论：无向图G是欧拉图当且仅当G是连通图，且G中没有奇度顶点。 有向欧拉图的判别 定理：有向图D具有欧拉通路，当且仅当D是连通图且D中除了两个例外顶点之外，其余顶点的入度都等于出度，这两个例外顶点中，一个的入度比出度大1，另一个的出度比入度大1。 推论：有向图D是欧拉图当且仅当D是连通图，且D中所有顶点的入度都等于出度。 例题 目录 二部图 欧拉图 哈密顿图 平面图 周游世界问题 1859年，数学家哈密顿将正十二面体的每个顶点比作一个城市，连接两个顶点之间的边看作城市之间的交通线，提出周游世界问题：能否从某个城市出发沿交通线经过每个城市一次并且仅一次，最后回到出发点？ 哈密顿图 哈密顿通路: 经过图中所有顶点的初级通路 哈密顿回路: 经过图中所有顶点的初级回路 哈密顿图: 有哈密顿回路的图 在下面各图中， 哪些是哈密顿图？哪些具有哈密顿通路？ 在下面各图中，图1，2，3都有哈密顿回路，是哈密顿图。图4具有哈密顿回路，是哈密顿图。图5只有哈密顿通路，但无哈密顿回路，不是哈密顿图，图6中既无哈密顿回路，也没有哈密顿通路，不是哈密顿图。 无向哈密顿图的必要条件 定理: 设G=V,E是无向哈密顿图，则对V的任意非空真子集V1有p(G-V1)?|V1|。 证明: 设C是G中任意哈密顿回路，则V1中的顶点在C中有些相邻，有些不相邻，p(C-V1)?|V1|。因为C是G的生成子图, 所以p(G-V1