《一些特殊的图》由会员分享，可在线阅读，更多相关《一些特殊的图（38页珍藏版）》请在金锄头文库上搜索。
1、一些特殊的图一些特殊的图匹配匹配v设设G=是是简简单单无无向向图图，E* E，若若E*中中任任意意两两边边均均不不相相邻邻，则则称称E*为为G中中的的匹匹配配(或或边边独独立立集集)。若若在在E*上上再再加加任任意意一一条条边边，就就不不再再是是匹匹配配，则则称称E*为为极极大大匹匹配配，边边数数最最多多的的极极大大匹匹配配称称为为最最大大匹匹配配，其其边边数数称称为为匹匹配配数数(或或边边独立数独立数) )，记为，记为 1(G)，简记为，简记为 1 。v若若M是图是图G中的一个匹配，对任意中的一个匹配，对任意v VG, 若存在若存在M中的边中的边与与v关联，关联， 则称则称v为为M饱和点饱和
2、点，否则称，否则称v为为M非饱和点非饱和点。若。若G中每个点都是中每个点都是M饱和点，则称饱和点，则称M是是G中的中的完美匹配完美匹配。 8/1/20242第四部分：图论（授课教师：向胜军）v完备匹配完备匹配 设设G=是是二二部部图图，若若G中中的的匹匹配配M饱饱和和V1或或V2中中所所有有顶顶点点，则则称称M为为完备匹配完备匹配。 注意：注意：完备匹配一定是最大匹配，但仅当完备匹配一定是最大匹配，但仅当|V1|=|V2|才是完美匹配才是完美匹配。 此图无完备匹配此图无完备匹配V1到到V2的完备匹配的完备匹配8/1/20243第四部分：图论（授课教师：向胜军）存在完备匹配的充分必要条件存在完备
3、匹配的充分必要条件vHall定定理理：二二部部图图G=, |V1| |V2|, G中中存存在在V1到到V2的的完完备备匹匹配配当当且且仅仅当当V1中中任任意意k个顶点个顶点(k=1,2,|V1|)至少邻接至少邻接V2中中k个顶点。个顶点。 存在完备匹配的一个充分条件存在完备匹配的一个充分条件v二部图二部图G=，若，若V1中每个顶点至少关中每个顶点至少关联联t条边，而条边，而V2中每个顶点至多关联中每个顶点至多关联t条边，则条边，则G中存在中存在V1到到V2的完备匹配。的完备匹配。证明：证明：任取任取V1中的中的k(k=1,2,|V1|)个顶点，他们关联的边个顶点，他们关联的边至少为至少为kt条
4、，但条，但V2中每个顶点至多为中每个顶点至多为t度，所以这度，所以这kt条条边至少关联边至少关联V2中的中的k个顶点。这满足个顶点。这满足Hall定理要求的定理要求的前提，所以，前提，所以，G中存在中存在V1到到V2的完备匹配。的完备匹配。8/1/20244第四部分：图论（授课教师：向胜军）求最大匹配的一个例子求最大匹配的一个例子x1 x2 x3 x4 x5y1 y2 y3 y4 y5v已知已知5个职员个职员x1, x2, x3, x4, x5和和5项工作项工作y1, y2, y3, y4, y5的匹配如图所示，求其最大匹配。的匹配如图所示，求其最大匹配。求解过程：求解过程：(1)取一初始匹配
5、取一初始匹配M.(2)分析分析M非饱和顶点，调整匹配方案。非饱和顶点，调整匹配方案。8/1/20245第四部分：图论（授课教师：向胜军）Leonhard Euler(1707-1783)vSwiss mathematician, who studied at the Univ. of Basel under the Swiss mathematician Johann Bernoulli, obtaining his masters degree at the age of 16. He worked as a member of the faculty of the Academy of S
6、cience in Saint Pertersburg, Russia for more than 30 years.v“欧拉计算毫不费力，就象人呼吸，或者鹰在风欧拉计算毫不费力，就象人呼吸，或者鹰在风 中保持平衡一样中保持平衡一样”(阿拉戈语阿拉戈语), 这不是对欧拉无这不是对欧拉无 与伦比的数学才能的夸大，欧拉是与伦比的数学才能的夸大，欧拉是历史上著作最历史上著作最 多的数学家多的数学家，被他的同代人称为，被他的同代人称为“分析的化身分析的化身”。 甚至在他生命的最后十年中的完全失明，也没有甚至在他生命的最后十年中的完全失明，也没有 妨碍他的无与伦比的多产；事实上，失去视力有妨碍他的无与伦
7、比的多产；事实上，失去视力有 什么影响的话，那就是使欧拉对他想象中的内部什么影响的话，那就是使欧拉对他想象中的内部 世界的洞察力更加敏锐。世界的洞察力更加敏锐。 摘自贝尔：摘自贝尔：数学精英数学精英2 欧拉图欧拉图8/1/20246第四部分：图论（授课教师：向胜军）Knigsberg七桥问题七桥问题v问题的抽象：问题的抽象：用顶点表示对象用顶点表示对象-“地块地块”用边表示对象之间的关系用边表示对象之间的关系-“有桥相连有桥相连”能否从河岸或小岛出发，通过每一座桥，而且仅仅通能否从河岸或小岛出发，通过每一座桥，而且仅仅通过一次回到原地。过一次回到原地。v Euler(欧拉欧拉)1736年对这个
8、问题，给出了否定的回答。将年对这个问题，给出了否定的回答。将河岸和小岛作为图的顶点，七座桥为边，构成一个无向重河岸和小岛作为图的顶点，七座桥为边，构成一个无向重图，问题化为图论中简单通路的问题。图，问题化为图论中简单通路的问题。8/1/20247第四部分：图论（授课教师：向胜军）欧拉通路和欧拉回路欧拉通路和欧拉回路 v包含图中每条边的包含图中每条边的简单通路简单通路称为称为欧拉通路欧拉通路。v包包含含图图中中每每条条边边的的简简单单回回路路称称为为欧欧拉拉回回路路。如如果果图图G中含欧拉回路，则图中含欧拉回路，则图G称为称为欧拉图欧拉图。v如果图如果图G中有欧拉通路，但没有欧拉回路，则图中有欧
9、拉通路，但没有欧拉回路，则图G称为称为半欧拉图半欧拉图。 欧拉欧拉图图半欧拉图半欧拉图无欧无欧拉通拉通路路8/1/20248第四部分：图论（授课教师：向胜军）欧拉图的判定欧拉图的判定 v连连通通无无向向图图G是是欧欧拉拉图图当当且且仅仅当当G中中每每个个顶顶点点的的度度均为偶数。均为偶数。v连连通通无无向向图图G具具有有欧欧拉拉通通路路当当且且仅仅当当G有有零零个个或或两两个奇度顶点。个奇度顶点。v连连通通有有向向图图D是是欧欧拉拉图图当当且且仅仅当当D中中每每个个顶顶点点的的入入度等于出度。度等于出度。v连连通通有有向向图图D具具有有欧欧拉拉通通路路当当且且仅仅当当D中中除除了了两两个个顶顶
10、点点外外，其其余余顶顶点点的的入入度度均均等等于于出出度度。这这两两个个特特殊殊的的顶顶点点中中，一一个个顶顶点点的的入入度度比比出出度度大大1，另另一一个个顶点的入度比出度小顶点的入度比出度小1。8/1/20249第四部分：图论（授课教师：向胜军）中国邮递员问题中国邮递员问题(欧拉通路的应用欧拉通路的应用)()(加权图加权图) )问题问题: 邮邮递递员员从从邮邮局局出出发发，走走遍遍投投递递区区域域的的所所有有街街道道，送送完完邮邮件件后后回回到到邮邮局局，怎怎样样使使所所走走的的路路线线全全程最短。程最短。 若若街街道道图图（街街道道的的交交叉叉口口为为顶顶点点）存存在在欧欧拉拉通路，显然
11、此路是全程最短。通路，显然此路是全程最短。 8/1/202410第四部分：图论（授课教师：向胜军）v每转一个触点，信号每转一个触点，信号 1 2 3 4变成变成 2 3 4 5，前者后三位决定了后者的前三位。因此，可把所前者后三位决定了后者的前三位。因此，可把所有三位二进制数作顶点，从每一个顶点有三位二进制数作顶点，从每一个顶点 1 2 3到到 2 3 4引一条有向边表示引一条有向边表示 1 2 3 4这个这个4位二进位二进制数，做出表示所有可能的码变换的有向图。于制数，做出表示所有可能的码变换的有向图。于是问题转化为在这个有向图上求一条欧拉回路。是问题转化为在这个有向图上求一条欧拉回路。该图
12、中的该图中的8个顶点的次数都个顶点的次数都为出度、入度均为为出度、入度均为2，由，由定理知，欧拉回路存在。定理知，欧拉回路存在。求出一条欧拉回路对应求出一条欧拉回路对应的布鲁英序列是：的布鲁英序列是：0111100101101000有向欧拉图的例子有向欧拉图的例子v一个模数转换中的应用举例：一个模数转换中的应用举例：旋转鼓设计：只需要旋转鼓设计：只需要16个物理触点便可以表示个物理触点便可以表示0-15总共总共16个不同的状态。个不同的状态。如何安排这如何安排这16个触点使每转过一个触点都得到一个不同的二进制信号。个触点使每转过一个触点都得到一个不同的二进制信号。（求布鲁英序列）（求布鲁英序列
13、）8/1/202411第四部分：图论（授课教师：向胜军）3 哈密尔顿图哈密尔顿图v1859年英国数学家哈密尔顿提出了一种名为年英国数学家哈密尔顿提出了一种名为“周游世界周游世界”的游戏：的游戏： 用一个正十二面体的二十用一个正十二面体的二十 个顶点代表二十个大城市，个顶点代表二十个大城市， 要求游戏者从某一城市出要求游戏者从某一城市出 发，遍历各城市一次，最发，遍历各城市一次，最 后回到原地。后回到原地。 这就是这就是“绕行世界绕行世界”问题。即找一条经过所有问题。即找一条经过所有顶点（城市）的基本通路（回路）。顶点（城市）的基本通路（回路）。8/1/202412第四部分：图论（授课教师：向胜
14、军）Sir William Hamilton(1805-1865)v爱尔兰历史上最伟大的科学家。爱尔兰历史上最伟大的科学家。v关于哈密尔顿早期的才能的传说，读起来象一篇拙劣的虚构的故事，但关于哈密尔顿早期的才能的传说，读起来象一篇拙劣的虚构的故事，但它是真实的。它是真实的。(例如，在十岁时，他差不多掌握了大多数主要东方语言例如，在十岁时，他差不多掌握了大多数主要东方语言) 哈密尔顿在进大学以前从未上过学哈密尔顿在进大学以前从未上过学(他他)轻而易举地取得第一名，进入轻而易举地取得第一名，进入三一学院。三一学院。大学生涯的结束，比它开始还要更令人惊奇；大学生涯的结束，比它开始还要更令人惊奇；都柏
15、林大都柏林大学理事会一致选举当时学理事会一致选举当时22岁的大学生哈密尔顿为教授。岁的大学生哈密尔顿为教授。 在在23岁时，他发表了他还是一个岁时，他发表了他还是一个17岁的孩子时作出的岁的孩子时作出的“奇怪的发现奇怪的发现”，即即光线系统理论光线系统理论第一部分，这是一篇伟大的杰作，它对于光学，第一部分，这是一篇伟大的杰作，它对于光学，就象拉格朗日的就象拉格朗日的分析力学分析力学之于力学。之于力学。 哈密尔顿最深刻的悲剧既不是酒精，也不是他的婚姻，而是他顽固地相哈密尔顿最深刻的悲剧既不是酒精，也不是他的婚姻，而是他顽固地相信，四元数是解决物质宇宙的数学关键。信，四元数是解决物质宇宙的数学关键
16、。从来没有一个伟大的数学家从来没有一个伟大的数学家这样毫无希望地错误过。这样毫无希望地错误过。 摘自摘自 贝尔：贝尔：数学精英数学精英v“我长期以来欣赏托勒密对他伟大的天文学大师希巴克斯的描绘：我长期以来欣赏托勒密对他伟大的天文学大师希巴克斯的描绘：一一个热爱劳动和热爱真理的人个热爱劳动和热爱真理的人。但愿我的墓志铭也如此但愿我的墓志铭也如此。” -威廉威廉哈密哈密尔顿尔顿8/1/202413第四部分：图论（授课教师：向胜军）哈密尔顿回路和哈密尔顿通路哈密尔顿回路和哈密尔顿通路 v经经过过图图G中中所所有有顶顶点点的的基基本本回回路路称称为为哈哈密密尔尔顿顿回回路路，若若G中中含含哈哈密密尔尔
17、顿顿回回路路，则则称称G为为哈哈密密尔顿图尔顿图。v经过图经过图G中所有顶点的中所有顶点的基本通路基本通路 称为称为哈密尔顿通路哈密尔顿通路，若，若G 中含哈密尔顿通路，中含哈密尔顿通路，但不含但不含 哈密尔顿回路，则称哈密尔顿回路，则称G为为 半哈密尔顿图半哈密尔顿图。 半哈密尔顿图半哈密尔顿图8/1/202414第四部分：图论（授课教师：向胜军）哈密尔顿图的必要条件哈密尔顿图的必要条件 v注意：注意：任任何何一一个个哈哈密密尔尔顿顿图图都都可可以以看看成成是是一一个个基基本本回回路路再再加加上连接该回路上顶点对的其他若干条边。上连接该回路上顶点对的其他若干条边。从从一一个个基基本本回回路路
18、上上删删除除k个个顶顶点点，最最多多形形成成k个个连连通通分分支支。向一个图中已有的顶点之间加边向一个图中已有的顶点之间加边不会增加不会增加连通分支连通分支。v因此：因此：若若G是哈密尔顿图，则对是哈密尔顿图，则对VG的任意非空真子集的任意非空真子集V1，p(G-V1)|V1|。 8/1/202415第四部分：图论（授课教师：向胜军）必要条件的应用必要条件的应用v必要条件一般只能判定一个图不是哈密尔顿图。必要条件一般只能判定一个图不是哈密尔顿图。如右图如右图(Petersen图图)满足上述满足上述 必要条件。但必要条件。但Petersen图不是图不是 哈密尔顿图。哈密尔顿图。均不满足必要均不满
19、足必要条件，所以都条件，所以都不是哈密尔顿不是哈密尔顿图。图。8/1/202416第四部分：图论（授课教师：向胜军）半哈密尔顿图的充分条件半哈密尔顿图的充分条件 v设设G是是n(n3)阶阶无无向向简简单单图图，若若G中中任任意不相邻的顶点对意不相邻的顶点对u,v均满足：均满足： d(u)+d(v)n-1 则则G是半哈密尔顿图。是半哈密尔顿图。注意注意: 此定理条件显然不是必要条件，如此定理条件显然不是必要条件，如n6的的n边形，对于边形，对于任意任意不相邻的顶点不相邻的顶点u, v, d(u)+d(v)=4，43, 设设该该面面的的边边界界上上顶顶点点依依次次是是v1, v2, v3, v4,
20、vt(t 4)，必必有有v1v3 EG, v2v4 EG，且且v1v3, v2v4只只能能在在Ri以以外外(否否则则在在该该面面内内部部加加一一条条边边，仍仍旧旧是是平平面面图图，与与G的的极极大大性性矛矛盾盾)，而而此此时这两边必相交，与时这两边必相交，与G是平面图矛盾。是平面图矛盾。不存在次数大于不存在次数大于3的面。的面。 假设假设G中每个面均是中每个面均是3次，则次，则2m=3r(这里这里m是是G中边数，中边数，r是面是面数数)，G连通，可以将上述等式代入欧拉公式连通，可以将上述等式代入欧拉公式n-m+r=2(n是是G中顶中顶点数点数)，得：，得：m=3n-6。假设。假设G不是极大平面
21、图，一定可以找到一对不是极大平面图，一定可以找到一对不相邻的顶点不相邻的顶点u,v, 使得使得G=G+uv仍是简单平面图，但在仍是简单平面图，但在G中：中：m3n-6，这与欧拉公式的推论矛盾，这与欧拉公式的推论矛盾，G是极大平面图。是极大平面图。 v1v3v2vtv4Ri面的边界面的边界内部没有边内部没有边8/1/202428第四部分：图论（授课教师：向胜军）同胚图同胚图 v基本动作：基本动作：二次顶点的插入和消去二次顶点的插入和消去v如如果果图图G1和和G2经经过过反反复复的的插插入入和和消消去去二二次次顶顶点点，可可达达到到同同构构，则则G1和和G2是是同同胚胚图图(homeomorphi
22、c Graph)。 uuvvw8/1/202429第四部分：图论（授课教师：向胜军）图的收缩图的收缩 v基本动作：基本动作：v图的收缩：图的收缩： uvuve w(u,v)8/1/202430第四部分：图论（授课教师：向胜军）平面图的充分必要条件平面图的充分必要条件v库拉图斯基库拉图斯基(Kuratowski)定理定理图图G是是平平面面图图当当且且仅仅当当G中中不不含含与与K5或者或者K3,3同胚的子图。同胚的子图。图图G是平面图是平面图当且仅当当且仅当G中不含可以中不含可以收缩到收缩到K5或者或者K3,3的子图。的子图。 8/1/202431第四部分：图论（授课教师：向胜军）Kuratows
23、ki定理的应用定理的应用 (1)vPetersen图不是平面图图不是平面图它可以收缩到它可以收缩到K58/1/202432第四部分：图论（授课教师：向胜军）Kuratowski定理的应用定理的应用 (2)v左图的一个子图与左图的一个子图与K3,3同胚。因此它是同胚。因此它是非非平面图平面图。hcghcbdefgaadbfe8/1/202433第四部分：图论（授课教师：向胜军）Kuratowski定理的应用定理的应用 (3)v左图含有与左图含有与K5同胚的子图，因此它也是同胚的子图，因此它也是非平面图。非平面图。bdefaacdefbc8/1/202434第四部分：图论（授课教师：向胜军）Kur
24、atowsky定理的应用定理的应用 (4) 消去二次顶点消去二次顶点删除边删除边收缩边收缩边8/1/202435第四部分：图论（授课教师：向胜军）对偶图对偶图(Dual Graph) 每一个面表示一个顶点，若两个面有每一个面表示一个顶点，若两个面有公共边界，则对应有一条边。按这种方公共边界，则对应有一条边。按这种方法画出的图法画出的图G*称为图称为图G的的对偶图对偶图。8/1/202436第四部分：图论（授课教师：向胜军）一个对偶图的例子一个对偶图的例子vG的对偶图为的对偶图为G*。v从图中可以看出，从图中可以看出， n*=r, m*=m, r*=n.8/1/202437第四部分：图论（授课教师：向胜军）
