离散数学 第八章 图论

离散数学西安交通大学电子与信息工程学院计算机软件所刘国荣2离散数学第八章图论（GraphTheory）3离散数学图论在计算机科学中的应用图论在计算机科学中扮演着重要的角色，为计算机科学中的形式语言、数据结构、分布式系统、操作系统、计算机网络等提供了有力的数学工具。特别是图论中的最小支撑树、最短通路、最大匹配、网络流、中国邮递员问题和旅行售货员问题在计算机科学中都有着广泛的应用。4无向图简单图多重图Euler图有向图Hamilton图补图子图完全图图二分图平面图自由树生成树最优树完全二分图货郎担问题中国邮路问题有根树有向Euler图有向Hamilton图连通图强连通分图单向连通分图弱连通分图匹配最大匹配完美匹配最优完美匹配问题m叉树5离散数学§1.图论朔源§2.图的基本概念§3.路与圈§4.图的矩阵表示§5.带权图的最短路径§6.Euler图§7.Hamilton图§8.二分图§9.平面图§10.树6离散数学§1.图论朔源图论的创始人图论应用的几个例子7离散数学§1.图论朔源图论最早处理的问题是哥尼斯堡（konigsberg）城普雷格尔(pregel)河上的七桥问题。1736年，瑞士数学家列昂哈德.欧拉(Leonhard.Euler)发表了他的著名论文“哥尼斯堡七座桥”。在这篇文章中他阐述了解决七桥问题的方法，引出了图论的观点，从而被誉为图论之父，成为图论的创始人。问题是这样的：在公元十八世纪的东普鲁士有个哥尼斯堡城（后属于前苏联的立陶宛苏维埃社会主义共和国，其名为加里宁格勒。现属于立陶宛共和国）。哥尼斯堡城位于普雷格尔河畔，河中有两个岛，城市中的各个部分由七座桥相连。当时，城中的居民热衷于这样一个问题，从四块陆地的任一块出发，怎样才能做到经过每座桥一次且仅一次，然后回到出发点。问题看来并不复杂，8离散数学但当地的居民和游人做了不少的尝试，却都没有取得成功。于是，有好事者便向当时居住在该城的大数学家欧拉请教。1736年，瑞士的数学家L.Euler解决了这个问题。他将四块陆地表示成四个结点，凡陆地间有桥相连的，便在两点间连一条线，这样图1就转化为图2了。此时，哥尼斯堡七桥问题归结为：在图2所示的图中，从A,B,C,D任一点出发，通过每条边一次且仅一次而返回出发点的回路是否存在？后人称如此的问题为Euler环游。欧拉断言这样的回路是不存在的。理由是：从图2中的任一结点出发，为了要回到原来的出发点，要求与每个结点相关联的边数均为偶数。这样才能保证从一条边进入某结点后，可从另一条边出去，而不经过已走过的注列昂哈德.欧拉Leonhard.Euler（1707-1783）瑞士数学家.后移居俄罗斯。27岁双目失明，主要靠秘书帮助工作。9离散数学边。从一个结点的不同的两条边一进一出才能回到原出发点。而图2中的A,B,C,D全是与奇数条边相连，由此可知所要求的回路是不可能存在的。10离散数学由此，欧拉给出了一个判定准则：若有Euler环游，则图中每个结点都必须是偶结点(与偶数条边相关联)；若不限定到回原出发点，则只能有两个奇结点(与奇数条边相关联)，一个起点，一个终点。这是图论的第一篇文献。时年欧拉22岁。有关这方面的内容，我们将在§6.Euler图来详细讨论。此图实际上是反映了客观事物之间的相互关系ADCB图211离散数学本世纪40年代，一个数学游戏也使用类似的方法得到了解决：某人挑一担菜、并带一只狗、一只羊，要从河的北岸到南岸。由于船小，只允许带狗、羊、菜三者中的一种过河；而由于明显的原因，当人不在场时狗与羊、羊与菜不能呆在一起。问此人应采取怎样的办法才能将这三样东西安全地带过河去？方法一：不对称状态空间法将人(person)、狗(dog)、羊(sheep)、菜(cabbage)中任意几种在一起的情况看作是一种状态，则北岸可能出现的状态共有十六种，其中安全状态有下面十种：(人，狗，羊，菜)，(空)；(P,D,S,C)，()；(人，狗，羊)，(菜)；(P,D,S,)，(C)；(人，狗，菜)，(羊)；(P,D,C)，(S)；12离散数学(人，羊，菜)，(狗)；(P,S,C)，(D)；(人，羊)，(狗，菜)；(P,S)，(D,C)。不安全的状态有如下六种：(人)，(狗，羊，菜)；(P)，(D,S,C)；(人，菜)，(狗，羊)；(P,C)，(D,S)；(人，狗)，(羊，菜)；(P,D)，(S,C)。可将十种安全状态表示成十个结点，而渡河的全过程则看作是状态间的转移。这样，上述问题就转化为求一条从(人，狗，羊，菜)或(P,D,S,C)状态到(空)或()状态的路径。图3中黑色箭头所表示的路径就是其中的一条。另一条从(P,D,S,C)到()状态的路径不同的部分由图3中红色箭头所示的路径给出。13离散数学方法二：对称状态空间法方法一仅考虑了河北岸的状态，没有考虑河南岸的状态。我们现在的方法是将用字符串表示的两岸状态放入一个二元组中，以表示两岸状态的变化，其前者表示河北岸的状态，后者表示河南岸的状态。其图示见下面图4。它具有对称性是明显的(状态的对称性，图的对称性，路径的对称性)。(P,D,S,C)()(P,D,S)(P,D,C)(C)(S)(D)(P,S,C)(P,S)(D,C)图314离散数学注：上述问题统称“渡河问题”。渡河问题很多，比如以下；“三对忌妒的夫妇渡河问题”参见《离散数学基础》[美]C.L.Liu著刘振宏译P162；“三个传教士与三个吃人肉的野人渡河问题”参见《Prolog高级程序设计》[美]L.斯特林E.夏皮罗著刘家佺邓佑译郑守淇校P197；渡河问题的条件也是可变的。比如夫妇的对数可以是四对，五对；渡河能力或渡河工具－小船的容量也是可变的。(PDC,S)(PDSC,)(DC,PS)(D,PSC)(PDS,C)(C,PDS)(PSC,D)(S,PDC)(PS,DC)(,PDSC)图415离散数学从上面的两上例子可以看到：对有些问题的研究可以归结为对图的研究，图是由点和线构成的。在图中我们感兴趣的事情是给定的两点间是否有连线，至于如何连结则是无关紧要的，这样的处理方式可以使问题变得简洁明了。下节，我们将给出图的正式定义。16离散数学§2.图的基本概念图的定义图论的概念术语子图与补图结点的度图的同构17离散数学由上节的例子，对什么是图我们有了初步的了解。我们看到：一个图有两个基本的成分——点与线，并且组成图的点与线之间有一定的联系。如在§1的图2中与点对(A,B)相联系的有一条边，与点对(A,D)相联系的有两条边，而点对(C,D)间却无边相联，作为图的定义，则需将点与边的关系描述清楚。下面，我们给出图的几种不同的定义。定义1.(图的定义一)图G=(V,E)是一个系统，其中(1)V是一个有限集合；V中的每一元素vV都称为图G的一个结点(node,vertex)；V称为图G的结点集；(2)E是一个有限集合；E中的每一元素eE都称为图G的一条边(edge)；E称为图G的边集。注：此定义的优点是简单，适应面广；缺点是没有规定清楚点、线之间的关系。图示：图与画的联系。18离散数学例1.有四个城市v1，v2，v3，v4，其中v1与v2间有公路e1相连，v1与v4间有公路e2相连，v2与v3间有公路e3相连。上述事实可用图G=(V,E)表示。图G中结点集V={v1,v2,v3,v4}，图G中边集E={e1,e2,e3}，它的图示如图1所示。定义2.(图的定义二)图G=(V,E)是一个系统，其中(1)V是一有限集合；V中的每一元素vV都称为图G的一个结点(node,vertex)；V称为图G的结点集；(2)EVV是一有限集合，一个V上的关系；E中的每一元素(u,v)E都称为图G的一条边(edge)(这里u,vV)；Ev1图1e2e3e1v2v4v319离散数学称为图G的边集。注：此定义的优点是简单，规定了清楚的点、线之间的关系，很适合简单图、特别是有向图（比如第二章的关系图、哈斯图）；缺点是无法表示平行边，因此不适合多重图（比如上节的七桥图）。根据这个定义，上面的例1可表示为：图G=(V,E)。图G中结点集合V={v1,v2,v3,v4}，图G中边的集合E={(v1,v2),(v1,v4),(v2,v3)}，它的图示仍如图1所示。例2.有四个程序，它们之间存在如下的调用关系：P1能调用P2，P2能调用P3，P2能调用P4。上述事实也可用一图G=(V,E)来表示。图中结点集V={v1,v2,v3,v4}v1(P1)图2v2(P2)v4(P4)v3(P3)20离散数学，图中边集E={(v1,v2),(v2,v3),(v2,v4)}，它的图示如图2所示。定义3.(图的定义三)图G=(V,,E)是一个系统，其中(1)V是一有限集合；V中的每一元素vV都称为图G的一个结点(node,vertex)；V称为图G的结点集；(2)是一有限集合；中的每一元素都称为图G中的一个标号(label)；称为图G的标号集；(3)EVV是一有限集合，一个三元关系；E中的每一元素(u,,v)E都称为图G的一条边(edge)或弧(arc),此边起自u而终于v；称u是此边的起点，称是此边的标号，称v是此边的终点，起点和终点统称为边的端点(这里u,vV,)；E称为图G的边集。21离散数学注：此定义是由美国哈佛大学爱伦堡教授给出的；此定义的优点是规定了严格的点、线之间的关系，适应面很广、特别适合多重图（比如上节的七桥图）；缺点是边表示比较复杂，简单图一般不采用。标号实际上是为了区别两点间的平行边而设的；标号集的大小一般就是图中平行边的最大条数(图的重数，参见下面概念)。当图的重数为1，即图无平行边时(简单图，参见下面概念)，有={1}，各边标号一样，全为1，这时可取掉各边标号及标号集，定义3就变成了定义2；所以定义3适合于图的一般情况，特别是(有平行边的)多重图，而定义2适合于(无平行边的)简单图。例3.七桥图(见图3),按定义3，可用一图G=(V,,E)来表示。图中结点集V={v1,v2,v3,v4}，22离散数学图中标号集={1,2}，图中边集E={(v1,1,v3),(v1,2,v3),(v1,1,v4),(v1,2,v4),(v1,1,v2),(v2,1,v3),(v2,1,v4)}，它的图示如图3所示。图论的基本概念性术语和一些特殊图：(1)(n,m)图:|V|=n,|E|=m，即有n个结点和m条边的图称为(n,m)图。(2)无向边：(undirectededges简edges)在定义3下，若边(u,,v)与边(v,,u)表示同一条边，则称此边为无向边。v1v41v3v2111122图323离散数学例如边(u,,v)就是一无向边。(3)无向图：(undirectedgraph简graph)所有的边都是无向边的图称为无向图。记为G。例如图1与七桥图(图3)都是无向图。(4)有向边：(directedarc简arc或arrow)在定义3下，若边(u,,v)与边(v,,u)表示不同的边，则称此边为有向边。例如边(u,,v)就是一有向边。(5)有向图：(directedgraph简digraph)所有的边都是有向边的图称为有向图。记为D。例如图2是有向图。半序关系的Hasse图是有向图。(6)混和图：(mixedgraph)既有有向边又有无向边的图称为混和图。uv无向边uv有向边24离散数学例如下边左图是一混和图。(7)空图：(emptygraph)V=(当然E=)，即没有一个结点的图称为空图。(8)零图：(nullgraph)E=，即没有一条边的图称为零图。v1v3v2图5.零图图4.混合图25离散数学例如上边右图是三个结点的零图。(9)平凡图：(trivialgraph)|V|=1，即只有一个结点的图称为平凡图。例如下边是三个不同的平凡图。(10)二边相邻：(adjacent)在图中，若两条边有一