06图与网络分析剖析.

2020/4/301运筹学OPERATIONSRESEARCH2020/4/302§1．图的基本概念与模型§2．树图和图的最小部分树§3．最短路问题§4．网络的最大流第六章图与网络分析（图论）GraphTheoryandNetworkAnalysis2020/4/303图论是应用非常广泛的运筹学分支，它已经广泛地应用于物理学控制论、信息论、工程技术、交通运输、经济管理、电子计算机等各项领域。对于科学研究、市场和社会生活中的许多问题，可以用图论的理论和方法来加以解决。例如，各种通信线路的架设，输油管道的铺设，铁路或者公路交通网络的合理布局等问题，都可以应用图论的方法，简便、快捷地加以解决。随着科学技术的进步，特别是电子计算机技术的发展，图论的理论获得了更进一步的发展，应用更加广泛。如果将复杂的工程系统和管理问题用图的理论加以描述，可以解决许多工程项目和管理决策的最优问题。因此，图论越来越受到工程技术人员和经营管理人员的重视。引言2020/4/304图论起源于一些游戏，最有代表性的是所谓的“七桥问题”，即一笔画问题。德国的哥尼斯堡城有一条普雷格尔河，河中有两个岛屿，河的两岸和岛屿之间有七座桥相互连接，如下图所示。2020/4/305BACD当地的居民热衷于这样一个问题：一个漫步者如何能够走过这七座桥，并且每座桥只能走过一次，最终回到原出发地。大家都没有成功，但不知道为什么。哥尼斯堡的七桥问题2020/4/306为了寻找答案，1736年欧拉把陆地缩为一点，把桥作为连接点的边，将这个问题抽象成图形的一笔画问题。即能否从某一点开始不重复地一笔画出这个图形，最终回到原点。这就是著名的Euler问题。欧拉在他的论文中证明了这是不可能的，因为这个图形中每一个顶点都与奇数条边相连接，不可能将它一笔画出。（每个结点关联的边数要均为偶数）。欧拉的论文题目是“依据几何位置的解题方法”，欧拉被公认为图论的创始人。这就是古典图论中的第一个著名问题。ABCDBACD2020/4/307ACDB简捷表示事物之间的本质联系，归纳事物之间的一般规律。ABCD2020/4/3081857年，英国数学家哈密尔顿发明了一种游戏：给出一个正12面体图形，共有20个顶点表示20个城市，要求从某个城市出发沿着棱线寻找一条经过每个城市一次而且仅一次，最后回到原处的周游世界线路（注意：并不要求经过每条边，要求经过每一顶点）。也称旅行者“环球旅行问题”或哈密尔顿（Hamilton）回路。哈密尔顿（Hamilton）回路2020/4/309环球旅行问题：2020/4/30102020/4/30112020/4/30122020/4/30132020/4/30142020/4/30152020/4/30162020/4/30172020/4/30182020/4/30192020/4/30202020/4/30212020/4/30222020/4/30232020/4/30242020/4/30252020/4/30262020/4/3027环球旅行问题的另一解2020/4/3028注意：欧拉回路：经过边一次，没有说顶点；（顶点没有要求，但可以理解为：顶点可以多次，而且必须经过每一个顶点，因为经过边必须经过顶点）哈密尔顿回路：经过顶点一次，没有说边。（边没有要求，不过可以理解为：边经过一次或者可以不经过）2020/4/3029•情侣问题：已知有M个男士，N个女士。每个男（女）士都对一些女（男）士倾慕，现问在这群人士中如何搭配，使较多的有情人终成眷属。•城市交通改善问题：随着私家车的不断出现，城市交通状况越来越拥挤，虽然城市在不断改善，但堵车现象仍然越来越多，出行难已成为一个社会问题。假设你是该城市的交通局长，在投资最少（或有限）的条件下应采用何种方法使交通状况得到好转。（交通网络不做大的变化）（应从交通瓶颈入手）•另外，这一时期，还有许多，诸如迷宫问题、博弈问题、棋盘上马的行走路线等问题，吸引了许多学者，这些看起来无足轻重的游戏引出了许多有实际意义的新问题，开辟了新的学科。2020/4/3030在实际的生产和生活中，人们为了反映事物之间的关系，常常在纸上用点和线来画出各式各样的示意图。例：有六支球队进行足球比赛，我们分别用点v1…v6表示这六支球队，它们之间的比赛情况，也可以用图反映出来，已知v1队战胜v2队，v2队战胜v3队，v3队战胜v5队，如此等等。这个胜负情况，可以用下图所示的有向图反映出来。v3v1v2v4v6v52020/4/3031§6.1图的基本概念与模型图（graph）是由一些结点或顶点（nodesorvertices）以及连接点的边（edges）构成。记做G={V,E}，其中V是顶点的集合，E是边的集合。一、基本概念给图中的点和边赋以具体的含义和权值，我们称这样的图为网络图（赋权图），记作N。2020/4/3032图中的点用v表示，边用e表示，对每条边可用它所联结的点表示，如图，则有：e1=[v1,v1]，e2=[v1,v2]或e2=[v2,v1]用点和点之间的线所构成的图，反映实际生产和生活中的某些特定对象之间的特定关系。通常用点表示研究对象,用点与点之间的线表示研究对象之间的特定关系。一般情况下，图中点的相对位置如何，点与点之间线的长短曲直，对于反映研究对象之间的关系，显的并不重要，因此，图论中的图与几何图，工程图等本质上是不同的。※图G区别于几何学中的图。这里只关心图中有多少个点以及哪些点之间有连线。V={v1,v2,v3,v4,v5}，E={e1,e2,e3,e4,e5,e6,e7,e8}，2020/4/3033(v1)赵(v2)钱孙(v3)李(v4)周(v5)吴(v6)陈(v7)e2e1e3e4e5(v1)赵(v2)钱(v3)孙(v4)李(v5)周(v6)吴(v7)陈e2e1e3e4e5可见图论中的图与几何图、工程图是不一样的。例如：在一个人群中，对相互认识这个关系我们可以用图来表示。2020/4/3034端点，关联边，相邻若边e可表示为e=[vi,vj]，称vi和vj是边e的端点(endvertex)；同时称边e为点vi和vj的关联边(incidentedge);若点vi,vj与同一条边关联，称点vi和vj相邻；若边ei与ej有公共端点，称边ei和ej相邻•点相邻：同一条边的两个端点称为相邻(adjacent)节点；•边相邻：具有共同端点的边称为相邻边2020/4/3035环,多重边,简单图如果边e的两个端点相重，称该边为环(loop)。如右图中边e1为环。如果两个点之间多于一条，称为多重边(paralleledges)，如右图中的e4和e5，对无环、无多重边的图称作简单图(simplegraph)。含多重边的图称为多重图。v3e7e4e8e5e6e1e2e3v1v2v4v5简单图多重图环多重边2020/4/3036次，奇点，偶点，孤立点与某个点相关联的边的数目，称为该点的次（或度、线度，degree），记作d(vi)。次为奇数的点称为奇点(odd),次为偶数的点称为偶点(even)；次为零的点称为孤立点(isolatedvertex)；次数为1的点称为悬挂点(pendantvertex)，与悬挂点关联的边称为悬挂边。图中可以只有点，而没有边；而有边必有点如图：奇点为v5，v3偶点为v1,v2,v4,v6孤立点为v62020/4/3037v2v1v5v3v4e2e1e3e4e5e6d(v1)=4d(v2)=3悬挂点孤立点悬挂边偶点奇点2020/4/3038图的基本性质：定理1任何图中，顶点次数之和等于所有边数的2倍。定理2任何图中，次为奇数的顶点必为偶数个。证明：由于每条边必与两个顶点关联，在计算点的次时，每条边均被计算了两次，所以顶点次数的总和等于边数的2倍。证明：设V1和V2分别为图G中奇点与偶点的集合。由定理1可得：mvdvdvdVvVvVv2)()()(212m为偶数，且偶点的次之和也为偶数，所以必为偶数，即奇数点的个数必为偶数。2)(Vvvd1)(Vvvd推论：图的各顶点的次的和是偶数。2020/4/3039例：以下各序列能不能是某个简单图的各顶点的次的序列？为什么？（a）7，6，5，4，3，3，2（b）6，6，5，4，3，3，1（c）6，5，5，4，3，2，1（b）1，1，2，3，22020/4/3040（a）7，6，5，4，3，3，2不能。7个顶点的简单图，每个顶点的次不会超过6；（b）6，6，5，4，3，3，1不能。若有两个次为6的点，则其中的每一个必定都与其余的6个点相邻，因此除这两个为6的点以外的5个点，每个点的次都至少是2，而不会有次为1的点（c）6，5，5，4，3，2，1不能。若去掉次为1的点及其关联边，剩下的图有6个顶点，次的序列为5，5，5，4，3，2，类似上题，是不可能的。（d）1，1，2，3，2不能。各点的次的和为奇数。2020/4/3041链，圈，路，回路，连通图图中存在点和边的交替序列μ={v0,e1,v1,e2,…,ek,vk}，点相邻,没有重复的边，只有重复的点，称μ为链(link)，起点和终点重合的链称为圈(loop)；特殊的链，链中顶点不相同，边也不相同的交替序列称为路(path)；起点和终点重合的路称为回路(circuit)（此处链的定义即欧拉链；路为哈密尔顿问题）。任意两点之间至少有一条链相连的图，称为连通图（没有孤立的点、边），否则称该图为不连通的。35264734221,,,,,,,,,,vevevevevev链4734221,,,,,,vevevev路,,,,,,,,,,,,,1335264734221vevevevevevev圈2020/4/3042说明：一般来说，链和路的定义没有此要求（无向图来说，路与链、圈和回路意义相同）。此处链的定义应该叫简单链，即欧拉链；路的定义应该叫初等链，为哈密尔顿问题。2020/4/3043完全图，偶图一个简单图中若任意两点之间均有边相连，称这样的图为完全图，含有n个顶点的完全图，其边数有条。如果图的顶点能分成两个互不相交的非空集合V1和V2,使在同一集合中任意两个顶点均不相邻，称这样的图为偶图（也称二分图），如果偶图的顶点集合V1和V2之间的每一对顶点都有一条边相连，称这样的图为完全偶图，完全偶图中V1含m个顶点，V2含有n个顶点，则其边数共m·n条。2)1(nn2020/4/3044二分图（偶图）图G=(V,E)的点集V可以分为两个非空子集X，Y，集X∪Y=V,X∩Y=Ø,使得同一集合中任意两个顶点均不相邻，称这样的图为二分图（偶图）。v1v3v5v2v4v6v1v2v3v4v1v4v2v3(a)(b)(c)(a)明显为二分图，(b)也是二分图，但不明显，改画为(c)时可以清楚看出。2020/4/3045子图、部分图设G1=｛V1,E1｝,G2=｛V2,E2｝子图定义：如果V2V1,E2E1称G2是G1的子图，也就是一个图里的部分边和点；部分图（支撑子图）：如果V2=V1,E2E1称G2是G1的部分图；如果子图与原图中的点相同而边比原图少。（部分图也是子图，但子图不一定是部分图）2020/4/3046G1G1=[V1,E1]2020/4/3047G2=[V2,E2]子图G22020/4/3048部分图：V3=V1,E3E1称G3是G1的部分图；G3子图部分图（支撑子图）G32020/4/3049G4（部分图）2020/4/3050二、图的模型对要研究的问题确定具体对象及这些对象间的性质联系并用图的形式表示出来，这就是对研究的问题建立图的模型。2020/4/3051例1：有甲,乙,丙,丁,戊,己6名运动员报名参加A,B,C,D,E,F6个项目的比赛。下表中打√的是各运动员报告参加的比赛项目。问6个项目的比赛顺序应如何安排，做到每名运动员都不连续地参加两项比赛。ABCDEF甲√√√乙√√√丙√√丁√√戊√√√己√√√2020/4/3052解：用图来建模。把比赛项目作为研究对象，用点表示。如果