图论讲义2012

2020/1/31§1．图的基本概念与模型§2．图的最小生成树§3．最短路问题§4．网络的最大流§5．最小费用流第六章图与网络分析2020/1/32BACD当地的居民热衷于这样一个问题：一个漫步者如何能够走过这七座桥，并且每座桥只能走过一次，最终回到原出发地。尽管试验者很多，但是都没有成功。哥尼斯堡的七桥问题2020/1/33为了寻找答案，1736年欧拉把陆地缩为一点，把桥作为连接点的边，将这个问题抽象成图形的一笔画问题。即能否从某一点开始不重复地一笔画出这个图形，最终回到原点。欧拉在他的论文中证明了这是不可能的，因为这个图形中每一个顶点都与奇数条边相连接，不可能将它一笔画出，这就是古典图论中的第一个著名问题。ABCDBACD2020/1/34在实际的生产和生活中，人们为了反映事物之间的关系，常常在纸上用点和线来画出各式各样的示意图。例有六支球队进行足球比赛，我们分别用点v1…v6表示这六支球队，它们之间的比赛情况，也可以用图反映出来，已知v1队战胜v2队，v2队战胜v3队，v3队战胜v5队，如此等等。这个胜负情况，可以用下图所示的有向图反映出来。v3v1v2v4v6v52020/1/35“巧渡河”问题问题：人、狼、羊、菜用一条只能同时载两位的小船渡河，“狼羊”、“羊菜”不能在无人在场时共处，当然只有人能架船。图模型：顶点表示“原岸的状态”，两点之间有边当且仅当一次合理的渡河“操作”能够实现该状态的转变。起始状态是“人狼羊菜”，结束状态是“空”。问题的解：找到一条从起始状态到结束状态的尽可能短的通路。2020/1/36“巧渡河”问题的解注意：在“人狼羊菜”的16种组合中允许出现的只有10种。空(成功)人羊狼菜人狼菜人羊狼人羊菜狼菜狼菜人羊羊2020/1/37(1,1,1,1)(1,1,1,0)(1,1,0,1)(1,0,1,1)(1,0,1,0)(0,0,0,0)(0,0,0,1)(0,0,1,0)(0,1,0,0)(0,1,0,1)(0,1,0,1)(0,1,0,0)(0,0,1,0)(0,0,0,1)(0,0,0,0)(1,0,1,0)(1,0,1,1)(1,1,0,1)(1,1,1,0)(1,1,1,1)河西=(人,狼,羊,菜)河东=(人,狼,羊,菜)将10个顶点分别记为A1,A2,…,A10,则渡河问题化为在该图中求一条从A1到A10的路.从图中易得到两条路：A1A6A3A7A2A8A5A10;A1A6A3A9A4A8A5A10.2020/1/38其他模型网络流问题全一问题最短网络问题……2020/1/39网络流问题随着中国经济快速的增长，城市化是未来中国的发展方向。人大通过的“十五”规划，把物流业作为战略重点列入要大力发展的新兴服务产业。如何制定一个运输计划使生产地到销售地的产品输送量最大。这就是一个网络最大流问题。2020/1/310网络流问题1956年Ford和Fulkerson提出了关于网络流问题的一个重要定理。最大流最小割定理：在任何网络中，最大流的值等于最小割的容量。由这个定理可以引出求网络最大流的一个算法——标号法。1970年，Edmonds和Karp对标号程序加以改进，使之成为一个好的算法。2020/1/311全一问题假设博物馆里有若干个房间，每个房间里有一盏灯和一个开关，每次按下某个房间的开关，可以改变这个房间以及它相邻的房间的灯的状态。2020/1/312全一问题问是否可以找到一种开灯的方案，使得所有房间的灯由全亮变为全灭？这就是Sutner于1989年提出的“全一问题”（All-OnesProblem)。2020/1/313最短网络问题如何用最短的线路将三部电话连起来？此问题可抽象为设△ABC为等边三角形，，连接三顶点的路线（称为网络）。这种网络有许多个，其中最短路线者显然是二边之和（如AB∪AC）。ABC2020/1/314最短网络问题但若增加一个周转站（新点P），连接4点的新网络的最短路线为PA＋PB＋PC。最短新路径之长N比原来只连三点的最短路径O要短。这样得到的网络不仅比原来节省材料，而且稳定性也更好。ABCP2020/1/315Pollak－Gilbert猜想由于最短网络在运输、通讯和计算机等现代经济与科技领域中都有重要的应用，对这个问题的研究也越来越深入。问题的对象已由三个点扩展到任意有限个点集。2020/1/316Pollak－Gilbert猜想斯坦纳（Steiner）最小树是可以在给定的点之外再增加若干个点(称为斯坦纳点)，然后将所有这些点连起来。如果不允许增加任何额外的点作为网络的顶点，这种最短网络称为最小生成树。在前面的例子中Steiner最小树的长为而最小生成树的长为2。32020/1/317Pollak－Gilbert猜想1968年贝尔实验室数学中心主任波雷克(Pollak)和研究员吉尔伯特(Gilbert)提出如下猜想：平面上任意n点集，斯坦纳最小树长与最小生成树之长的比值的最小值是。这个猜想又被称为斯坦纳比猜想。232020/1/318Pollak－Gilbert猜想1990年，中科院应用数学所研究员堵丁柱与美籍华人黄光明合作，证明了Pollak－Gilbert猜想。在美国离散数学界引起轰动，被列为1989—1990年度美国离散数学界与理论计算机科学界的两项重大成果之一。在《不列颠百科全书1992年鉴》的数学评论中，该成果被列为世界上当年六项数学成果首项。该成果被我国列为1992年十大科技成就之一。2020/1/319§6.1．图的基本概念与模型图（graph）是由一些结点或顶点（nodesorvertices）以及连接点的边（edges）构成。记做G={V,E}，其中V是顶点的集合，E是边的集合。给图中的点和边赋以具体的含义和权值，我们称这样的图为网络图（赋权图）一、基本概念2020/1/320图中的点用v表示，边用e表示，对每条边可用它所联结的点表示，如图，则有：e1=[v1,v1]，e2=[v1,v2]或e2=[v2,v1]用点和点之间的线所构成的图，反映实际生产和生活中的某些特定对象之间的特定关系。通常用点表示研究对象,用点与点之间的线表示研究对象之间的特定关系。一般情况下，图中点的相对位置如何，点与点之间线的长短曲直，对于反映研究对象之间的关系，显的并不重要，因此，图论中的图与几何图，工程图等本质上是不同的。2020/1/321端点，关联边，相邻若边e可表示为e=[vi,vj]，称vi和vj是边e的端点，同时称边e为点vi和vj的关联边，若点vi,vj与同一条边关联，称点vi和vj相邻；若边ei与ej有公共端点，称边ei和ej相邻；如果边e的两个端点相重，称该边为环，如果两个点之间的边多于一条，称为具有多重边，对无环、无多重边的图称为简单图。环，多重边，简单图2020/1/322[定义]孤立点若a∈V，a不与其他顶点相邻，称a为孤立点(isolatedvertex)。[定义]顶点的度在无向图G中，与a相邻的顶点的数目称为a的度(degree)。记为deg(a)或d(a)。在有向图D中，以a为终点的边的条数称为a的入度(in-degree)。记为deg–(a)或d–(a)。以a为始点的边的条数称为a的出度(out-degree)。记为deg+(a)或d+(a)。2020/1/323[定理1(握手定理Handshaking)]设无向图G=V,E有n个顶点，m条边，则G中所有顶点的度之和等于m的两倍。即证明思路：利用数学归纳法。[定理2]无向图中度为奇数的顶点个数恰有偶数个。证明思路：将图中顶点的度分类，再利用定理1。n1iim2vd.)(2020/1/324[定理3]设有向图D=V,E有n个顶点，m条边，则G中所有顶点的入度之和等于所有顶点的出度之和，也等于m。即：证明思路：利用数学归纳法。n1in1iiimvdvd.)()(2020/1/325一些特殊的简单图：(1)无向完全图Kn(CompleteGraphs)(2)有向完全图(3)零图：E=.(4)平凡图：E=且|V|=1.(5)正则图：若图G＝V,E中每个顶点的度均为n，称此图G是n-正则图(n-regulargraph)。2020/1/326完全图(n=1,2,3,4,5)K1K2K3K5K42020/1/327[定理4]设无向完全图G有n个顶点，则G有n(n-1)/2条边。证明：每一顶点都与其余的n-1个顶点相邻，即每一顶点的度为n-1，共有n个顶点，则图G的度为n(n-1)，由握手定理，得边数m=n(n-1)/2.2020/1/328正则图（各顶点的度相同）3-正则图3-正则图2020/1/329[定义]子图设G=V,E，G’=V’,E’是两个图，若V’V，且E’E，则称G’为G的子图(subgraph)。注：当V’=V时，称G’为G的生成子图。当E’E，或V’V时，称G’为G的真子图。2020/1/330[定义]补图设G=V,E是n阶无向简单图，以V为顶点集，以所有能使G成为完全图Kn的添加边组成的集合为边集的图，称为G相对于完全图Kn的补图，简称G的补图，记为。G图G与其补图G’具有相同的顶点集，其边集不相交，构成相应完全图边集的划分。2020/1/331aedcbedcba图A图Bdbaecedcb图C图Daedcbdb图E图F2020/1/332图Ａ是一个无向完全图图Ｂ，Ｃ，Ｄ，Ｅ，Ｆ均是Ａ的子图图Ｃ的顶点ａ是孤立顶点图Ｂ的边(ａ，ｂ)是孤立边图Ｄ是图Ｃ的子图图Ｅ是图Ｃ的补图2020/1/333[定义]图的同构图G1＝V1,E1，G2＝V2,E2，如果能建立V1与V2间的一一对应，在此对应下，E1与E2中的边也一一对应，对有向图还保持关联方向的对应，则称图G1与G2同构，记作G1G2。2020/1/334acde无向图bfghij例：1(a)3(c)4(h)6(e)2(b)5(f)8(g)10(i)9(d)7(j)2020/1/335有向图例：abcde2(a)1(b)3(d)4(c)5(e)2020/1/336例：(1)画出4个顶点3条边的所有可能非同构的无向简单图。(2)画出3个顶点2条边的所有可能非同构的有向简单图。•(1)(2)2020/1/337连通性(Connectivity)[定义]通路(path)给定图G=V,E，设图G中顶点和边的交替序列为T=v0e1v1e2…ekvk，若T满足如下条件：vi-1和vi是ei的端点(当G为有向图时，vi-1是ei的始点，vi是ei的终点)，i=1,2,…,k，则称T为顶点v0到vk的通路。此通路的长度为k。也可以用v0,v1,…,vk表示通路，v0为始点，vk为终点。当v0=vk时，该通路称为回路(circuit)。2020/1/338[定义]简单通路(SimplePath)若通路中所有边互不相同，称此道路为简单通路。若回路中的所有边互不相同，称为简单回路(SimpleCircuit)。[定义]基本通路(ElementPath)一条通路中，除了始点和终点可以相同，其余顶点均互不相同，称此通路为基本通路(初级通路)。当其是回路时，称为基本回路(ElementCircuit初级回路或圈)。2020/1/339e3e5e2e1dcbae4e5,e1,e2,e3,e4是简单通路，不是基本通路，因为c,a,b,c,d,b中b,c均出现了两次。但c,d,b,c是基本通路，也是基本回路。2020/1/340[定理]在一个n阶图中，若从顶点u到v(uv)存在通路，则从u到v存在长度小于等于n-1的基本通路。若存在v到自身的简单回路，则从v到自身存在长度不超过n的基本回路。证明：设T=v0e1v1…ekvk(v0=u,vk=v)为u到v的通路，若T上无重复出现的顶点，则T为基本通路。否则必存在ts，vt=vs，在T中去掉vt到vs的一段，所得通路仍为u到v的通路，不妨仍记为T。若T上还有重复出现的顶点，就做同样的