图与网络分析剖析课件

运筹学

OPERATIONSRESEARCH

2023/8/191运筹学

OPERATIONSRESEARCH

2023/8§1．图的基本概念与模型§2．树图和图的最小部分树§3．最短路问题§4．网络的最大流第六章图与网络分析（图论）GraphTheoryandNetworkAnalysis2023/8/192§1．图的基本概念与模型§2．树图和图的最小部分树§3图论是应用非常广泛的运筹学分支，它已经广泛地应用于物理学控制论、信息论、工程技术、交通运输、经济管理、电子计算机等各项领域。对于科学研究、市场和社会生活中的许多问题，可以用图论的理论和方法来加以解决。例如，各种通信线路的架设，输油管道的铺设，铁路或者公路交通网络的合理布局等问题，都可以应用图论的方法，简便、快捷地加以解决。随着科学技术的进步，特别是电子计算机技术的发展，图论的理论获得了更进一步的发展，应用更加广泛。如果将复杂的工程系统和管理问题用图的理论加以描述，可以解决许多工程项目和管理决策的最优问题。因此，图论越来越受到工程技术人员和经营管理人员的重视。引言2023/8/193图论是应用非常广泛的运筹学分支，它已经广泛地应用图论起源于一些游戏，最有代表性的是所谓的“七桥问题”，即一笔画问题。

德国的哥尼斯堡城有一条普雷格尔河，河中有两个岛屿，河的两岸和岛屿之间有七座桥相互连接，如下图所示。2023/8/194图论起源于一些游戏，最有代表性的是所谓的“七BACD

当地的居民热衷于这样一个问题：一个漫步者如何能够走过这七座桥，并且每座桥只能走过一次，最终回到原出发地。大家都没有成功，但不知道为什么。哥尼斯堡的七桥问题2023/8/195BACD当地的居民热衷于这样一个问题：一个漫步者如何

为了寻找答案，1736年欧拉把陆地缩为一点，把桥作为连接点的边，将这个问题抽象成图形的一笔画问题。即能否从某一点开始不重复地一笔画出这个图形，最终回到原点。这就是著名的Euler问题。

欧拉在他的论文中证明了这是不可能的，因为这个图形中每一个顶点都与奇数条边相连接，不可能将它一笔画出。（每个结点关联的边数要均为偶数）。欧拉的论文题目是“依据几何位置的解题方法”，欧拉被公认为图论的创始人。这就是古典图论中的第一个著名问题。BACD2023/8/196为了寻找答案，1736年欧拉把陆地缩为一点，把桥作为ACDB简捷表示事物之间的本质联系，归纳事物之间的一般规律。2023/8/197ACDB简捷表示事物之间的本质联系，归纳事物之间的一般规律。1857年，英国数学家哈密尔顿发明了一种游戏：给出一个正12面体图形，共有20个顶点表示20个城市，要求从某个城市出发沿着棱线寻找一条经过每个城市一次而且仅一次，最后回到原处的周游世界线路（注意：并不要求经过每条边，要求经过每一顶点）。也称旅行者“环球旅行问题”或哈密尔顿（Hamilton）回路。哈密尔顿（Hamilton）回路2023/8/1981857年，英国数学家哈密尔顿发明了一种游戏：给出一环球旅行问题：2023/8/199环球旅行问题：2023/8/592023/8/19102023/8/5102023/8/19112023/8/5112023/8/19122023/8/5122023/8/19132023/8/5132023/8/19142023/8/5142023/8/19152023/8/5152023/8/19162023/8/5162023/8/19172023/8/5172023/8/19182023/8/5182023/8/19192023/8/5192023/8/19202023/8/5202023/8/19212023/8/5212023/8/19222023/8/5222023/8/19232023/8/5232023/8/19242023/8/5242023/8/19252023/8/5252023/8/19262023/8/526环球旅行问题的另一解2023/8/1927环球旅行问题的另一解2023/8/527注意：欧拉回路：经过边一次，没有说顶点；（顶点没有要求，但可以理解为：顶点可以多次，而且必须经过每一个顶点，因为经过边必须经过顶点）哈密尔顿回路：经过顶点一次，没有说边。（边没有要求，不过可以理解为：边经过一次或者可以不经过）2023/8/1928注意：2023/8/528情侣问题：

已知有M个男士，N个女士。每个男（女）士都对一些女（男）士倾慕，现问在这群人士中如何搭配，使较多的有情人终成眷属。城市交通改善问题：

随着私家车的不断出现，城市交通状况越来越拥挤，虽然城市在不断改善，但堵车现象仍然越来越多，出行难已成为一个社会问题。假设你是该城市的交通局长，在投资最少（或有限）的条件下应采用何种方法使交通状况得到好转。（交通网络不做大的变化）（应从交通瓶颈入手）另外，这一时期，还有许多，诸如迷宫问题、博弈问题、棋盘上马的行走路线等问题，吸引了许多学者，这些看起来无足轻重的游戏引出了许多有实际意义的新问题，开辟了新的学科。2023/8/1929情侣问题：另外，这一时期，还有许多，诸如迷宫问题、博弈

在实际的生产和生活中，人们为了反映事物之间的关系，常常在纸上用点和线来画出各式各样的示意图。例：有六支球队进行足球比赛，我们分别用点v1…v6

表示这六支球队，它们之间的比赛情况，也可以用图反映出来，已知v1

队战胜v2

队，v2

队战胜v3队，v3

队战胜v5

队，如此等等。这个胜负情况，可以用下图所示的有向图反映出来。v3v1v2v4v6v52023/8/1930在实际的生产和生活中，人们为了反映事物之间的关系，常§6.1图的基本概念与模型

图（graph）是由一些结点或顶点（nodes

orvertices）以及连接点的边（edges）构成。记做G={V,E}，其中V是顶点的集合，E是边的集合。一、基本概念

给图中的点和边赋以具体的含义和权值，我们称这样的图为网络图（赋权图），记作N。2023/8/1931§6.1图的基本概念与模型图（graph）是由

图中的点用

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}，2023/8/1932图中的点用v表示，边用e表示，对每条边(v1)赵(v2)钱孙(v3)李(v4)周(v5)吴(v6)陈(v7)e2e1e3e4e5(v1)赵(v2)钱(v3)孙(v4)李(v5)周(v6)吴(v7)陈e2e1e3e4e5可见图论中的图与几何图、工程图是不一样的。例如：在一个人群中，对相互认识这个关系我们可以用图来表示。2023/8/1933(v1)(v2)钱孙(v3)李(v4)周(v5)吴(v6)陈端点，关联边，相邻

若边e可表示为e

=[vi

,vj]，称vi

和vj是边

e

的端点(endvertex)

；同时称边

e

为点vi

和vj的关联边(incidentedge);若点vi

,vj与同一条边关联，称点vi

和vj相邻；若边ei与ej有公共端点，称边ei

和ej相邻点相邻：同一条边的两个端点称为相邻(adjacent)节点；边相邻：具有共同端点的边称为相邻边2023/8/1934端点，关联边，相邻若边e可表示为e=环,多重边,简单图如果边e的两个端点相重，称该边为环(loop)

。如右图中边e1为环。如果两个点之间多于一条，称为多重边(paralleledges)

，如右图中的e4和e5，对无环、无多重边的图称作简单图(simplegraph)

。含多重边的图称为多重图。v3e7e4e8e5e6e1e2e3v1v2v4v5简单图多重图环多重边2023/8/1935环,多重边,简单图如果边e的两个端点相重，称该边为环次，奇点，偶点，孤立点与某个点相关联的边的数目，称为该点的次（或度、线度，degree），记作

d(vi)。次为奇数的点称为奇点(odd),次为偶数的点称为偶点(even)；次为零的点称为孤立点

(isolatedvertex)；次数为1的点称为悬挂点(pendantvertex)，与悬挂点关联的边称为悬挂边。

图中可以只有点，而没有边；而有边必有点如图：奇点为v5，v3偶点为v1,v2,

v4,

v6孤立点为

v62023/8/1936次，奇点，偶点，孤立点与某个点相关联的边的数目，称为v2v1v5v3v4e2e1e3e4e5e6d(v1)=4d(v2)=3悬挂点孤立点悬挂边偶点奇点2023/8/1937v2v1v5v3v4e2e1e3e4e5e6d(v1)=4d图的基本性质：定理1任何图中，顶点次数之和等于所有边数的2倍。定理2任何图中，次为奇数的顶点必为偶数个。证明：由于每条边必与两个顶点关联，在计算点的次时，每条边均被计算了两次，所以顶点次数的总和等于边数的2倍。证明：设V1和V2分别为图G中奇点与偶点的集合。由定理1可得：2m为偶数，且偶点的次之和也为偶数，所以必为偶数，即奇数点的个数必为偶数。推论：图的各顶点的次的和是偶数。2023/8/1938图的基本性质：定理1任何图中，顶点次数之和等于所有边数的

例：以下各序列能不能是某个简单图的各顶点的次的序列？为什么？（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，22023/8/19392023/8/539（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不能。各点的次的和为奇数。2023/8/1940（a）7，6，5，4，3，3，22023/8/540链，圈，路，回路，连通图

图中存在点和边的交替序列μ={v0,e1,v1,e2,…,ek,vk}，点相邻,没有重复的边，只有重复的点

，称μ为链(link)，起点和终点重合的链称为圈(loop)；特殊的链，链中顶点不相同，边也不相同的交替序列称为路(path)；起点和终点重合的路称为回路(circuit)（此处链的定义即欧拉链；路为哈密尔顿问题）。

任意两点之间至少有一条链相连的图，称为连通图（没有孤立的点、边），否则称该图为不连通的。链路圈2023/8/1941链，圈，路，回路，连通图图中存在点和边的交替序列μ=说明：

一般来说，链和路的定义没有此要求（无向图来说，路与链、圈和回路意义相同）。此处链的定义应该叫简单链，即欧拉链；路的定义应该叫初等链，为哈密尔顿问题。2023/8/1942说明：2023/8/542完全图，偶图

一个简单图中若任意两点之间均有边相连，称这样的图为完全图，含有

n

个顶点的完全图，其边数有条。如果图的顶点能分成两个互不相交的非空集合V1和V2,使在同一集合中任意两个顶点均不相邻，称这样的图为偶图（也称二分图），如果偶图的顶点集合V1和V2

之间的每一对顶点都有一条边相连，称这样的图为完全偶图，完全偶图中V1含m

个顶点，V2含有n

个顶点，则其边数共m·n条。2023/8/1943完全图，偶图一个简单图中若任意两点之间均有边相连二分图（偶图）图G=(V,E)的点集V可以分为两个非空子集X，Y，集X∪Y=V,X∩Y=Ø,使得同一集合中任意两个顶点均不相邻，称这样的图为二分图（偶图）。v1v3v5v2v4v6v1v2v3v4v1v4v2v3(a)(b)(c)(a)明显为二分图，(b)也是二分图，但不明显，改画为(c)时可以清楚看出。2023/8/1944二分图（偶图）图G=(V,E)的点集V可以分为两个非空子

子图、部分图

设G1=｛V1,E1｝,G2=｛V2,E2｝

子图定义：如果V2

V1,E2

E1

称G2

是G1

的子图，也就是一个图里的部分边和点；

部分图（支撑子图）：如果V2=V1,E2

E1

称G2

是G1

的部分图；如果子图与原图中的点相同而边比原图少。（部分图也是子图，但子图不一定是部分图）2023/8/1945子图、部分图2023/8/545G1G1=[V1,E1]2023/8/1946G1G1=[V1,E1]2023/8/546G2=[V2,E2]子图

G22023/8/1947G2=[V2,E2]子图G22023/8/54部分图：V3

=V1,E3

E1

称G3

是G1

的部分图；G3子图

部分图

（支撑子图）G32023/8/1948部分图：V3=V1,E3E1称G3是G

G4

（部分图）2023/8/1949G4

（部分图）2023/8/549二、图的模型

对要研究的问题确定具体对象及这些对象间的性质联系并用图的形式表示出来，这就是对研究的问题建立图的模型。

2023/8/1950二、图的模型2023/8/550例1：有甲,乙,丙,丁,戊,己6名运动员报名参加A,B,C,D,E,F6个项目的比赛。下表中打√的是各运动员报告参加的比赛项目。问6个项目的比赛顺序应如何安排，做到每名运动员都不连续地参加两项比赛。ABCDEF甲√√√乙√√√丙√√丁√√戊√√√己√√√2023/8/1951例1：有甲,乙,丙,丁,戊,己6名运动员报名参加A,B,C解：用图来建模。把比赛项目作为研究对象，用点表示。如果2个项目有同一名运动员参加，在代表这两个项目的点之间连一条线，可得下图。ABCDEF书上例1问题是在图中寻找一条哈密尔顿道路。做图6-3的补图。2023/8/1952解：用图来建模。把比赛项目作为研究对象，用点表示。如果2个项ABCDEF在图中找到一个点序列，使得依次排列的两点不相邻，即能满足要求。如：1)A,C,B,F,E,D2)D,E,F,B,C,A2023/8/1953ABCDEF在图中找到一个点序列，使得依次排列的两点不相邻，例：一个班级的学生共计选修A、B、C、D、E、F六门课程，其中一部分人同时选修D、C、A，一部分人同时选修B、C、F，一部分人同时选修B、E，还有一部分人同时选修A、B，期终考试要求每天考一门课，六天内考完，为了减轻学生负担，要求每人都不会连续参加考试，试设计一个考试日程表。2023/8/1954例：一个班级的学生共计选修A、B、C、D、E、F六门课程，其AFEDCB解：以每门课程为一个顶点，共同被选修的课程之间用边相连，得图。2023/8/1955AFEDCB解：以每门课程为一个顶点，共同被选修的课程之间用按题意，相邻顶点对应课程不能连续考试，不相邻顶点对应课程允许连续考试，因此，作图的补图。2023/8/1956按题意，相邻顶点对应课程不能连续考试，不相邻顶点对应AFEDCB2023/8/1957AFEDCB2023/8/557AFEDCB2023/8/1958AFEDCB2023/8/558AFEDCB问题是在图中寻找一条哈密尔顿道路。2023/8/1959AFEDCB问题是在图中寻找一条哈密尔顿道路。2023/8AFEDCB2023/8/1960AFEDCB2023/8/560AFEDCB2023/8/1961AFEDCB2023/8/561AFEDCB2023/8/1962AFEDCB2023/8/562AFEDCB如C—E—A—F—D—B，就是一个符合要求的考试课程表。2023/8/1963AFEDCB如C—E—A—F—D—B，就是一个符合要求的考试例：有7个人围桌而坐，如果要求每次相邻的人都与以前完全不同，试问不同的就座方案共有多少种？

解：用顶点表示人，用边表示两者相邻，因为最初任何两个人都允许相邻，所以任何两点都可以有边相连。2023/8/1964例：有7个人围桌而坐，如果要求每次相邻的人都与以前完全不同，12376452023/8/196512376452023/8/565假定第一次就座方案是（1，2，3，4，5，6，7，1），那么第二次就座方案就不允许这些顶点之间继续相邻，只能从图中删去这些边。2023/8/1966假定第一次就座方案是2023/8/56612376452023/8/196712376452023/8/56712376452023/8/196812376452023/8/56812376452023/8/196912376452023/8/56912376452023/8/197012376452023/8/57012376452023/8/197112376452023/8/57112376452023/8/197212376452023/8/57212376452023/8/197312376452023/8/57312376452023/8/197412376452023/8/574假定第二次就座方案是（1，3，5，7，2，4，6，1），那么第三次就座方案就不允许这些顶点之间继续相邻，只能从图中删去这些边。2023/8/1975假定第二次就座方案是2023/8/57512376452023/8/197612376452023/8/57612376452023/8/197712376452023/8/57712376452023/8/197812376452023/8/57812376452023/8/197912376452023/8/57912376452023/8/198012376452023/8/58012376452023/8/198112376452023/8/58112376452023/8/198212376452023/8/58212376452023/8/198312376452023/8/583假定第三次就座方案是（1，4，7，3，6，2，5，1），那么第四次就座方案就不允许这些顶点之间继续相邻，只能从图中删去这些边，只留下7点孤立点，所以该问题只有三个就座方案。2023/8/1984假定第三次就座方案是2023/8/58412376452023/8/198512376452023/8/58512376452023/8/198612376452023/8/58612376452023/8/198712376452023/8/58712376452023/8/198812376452023/8/58812376452023/8/198912376452023/8/58912376452023/8/199012376452023/8/59012376452023/8/199112376452023/8/591课后习题1-3课后1：这一类求库存最少的问题称为染色问题，一般尚未解决。用图的观点分析实际问题，首先要认定点代表什么，边代表什么。注意一是要恰当反映实际问题，二是要尽量使后面的计算能够简便。思路：8个点代表8种药品，不能放一贮藏室内连一条边如果能在图中找出k个顶点的子图是完全图的话，那么这个子图的k个顶点对应的药品必须每种一室S:ABR:DP:CTASTPRDCB2023/8/1992课后习题1-3ASTPRDCB2023/8/592课后2：次、相邻。已知景点与几条边关联；与哪些点相邻思路：A.看图可知，两个景点之间若有路可通（于是他们相邻），则只有一条，这是旅行者往返此两点间的必由之路；B.又注意到不同景点的关联边条数不全相同，这是确定不同景点的相对位置的依据；C.此人从A开始先到的恰是16个不同景点，依次经过的两个景点间连上一条边（表示这两个景点间有一条路相连），即计算这两个点的“次”时，每个点的“次”都加上一个“1”，从17个景点开始，以后到达的景点此前已到达过，故只需在排成一行的16个点中相应两个点的上方或下方，记上相应景点记号，连上一条边来表示相应的道路。次为2的点：AHDE次为3的点：KOLPIMJN次为4的点：GBCF2023/8/1993课后2：次、相邻。已知景点与几条边关联；与哪些点相邻20232023/8/19942023/8/594课后3：做补图第一天：AE；第二天：CB；第三天：DF。2023/8/19952023/8/595§2．树图和图的最小部分树在各种各样的图中，有一类图是十分简单又非常具有应用价值的图，这就是树。树图：倒置的树，根(root)在上，树叶(leaf)在下。多级辐射制的电信网络、管理的指标体系、决策树、家谱、分类学、组织结构等都是典型的树图。

树是图论中结构最简单但又十分重要的图。在自然和社会领域应用极为广泛。2023/8/1996§2．树图和图的最小部分树在各种各样的图中，有一类例：乒乓求单打比赛抽签后，可用图来表示相遇情况，如下图所示。ABCDEFGH运动员2023/8/1997例：乒乓求单打比赛抽签后，可用图来表示相遇情况，如下图所示。例：某企业的组织机构图也可用树图表示。厂长人事科财务科总工程师生产副厂长经营副厂长开发科技术科生产科设备科供应科销售科检验科动力科2023/8/1998例：某企业的组织机构图也可用树图表示。厂长人事科财务科总工生例：已知有六个城市，它们之间要架设电话线，要求任意两个城市均可以互相通话，并且电话线的总长度最短。如果用六个点v1…v6代表这六个城市，在任意两个城市之间架设电话线，即在相应的两个点之间连一条边。这样，六个城市的一个电话网就作成一个图。由于任意两个城市之间均可以通话，这个图必须是连通图。并且，这个图必须是无圈的。否则，从圈上任意去掉一条边，剩下的图仍然是六个城市的一个电话网。下图是一个不含圈的连通图，代表了一个电话线网。v6v3v4v2v5v12023/8/1999例：已知有六个城市，它们之间要架设电话线，要求任意

树图（简称树，记作T(V,E)）是无圈的连通图。（无圈，无多重边）

一.树的性质性质1.任何树中必存在次为1的点。（没有圈，没有回路）证明：反证法

性质2.具有

n

个顶点的树恰有（n-1）条边。证明：归纳法

性质3.任何具有n个点、(n-1)条边连通图是树。证明：反证法2023/8/19100树图（简称树，记作T(V,E)）是无圈的连通图以上性质说明：

1.树是边数最多的无圈的连通图，树中只要任意再加一条边，必出现圈。

2.树中任意两点之间有且只有一条通路以上7个命题都可以作为树的定义

3.从树中任意删掉一条边，就不再连通。（树是最脆弱的连通图）2023/8/19101以上性质说明：2.树中任意两点之间有且只有一条通路以上7二.图的最小部分树（最小支撑树）如果G1是G2的部分图，又是树图，则称G1是G2

的部分树（或支撑树）；树图的各条边称为树枝(假定各边均有权重)；树枝总长最小的部分树，称为该图的最小部分树(也称最小支撑树)。最小支撑树问题就是赋权图的最优化问题之一。如前所述，在已知的几个城市之间联结电话线网，要求总长度最短和总建设费用最少，这个问题的解决可以归结为最小支撑树问题。再如，城市间交通线的建造等，都可以归结为这一类问题。2023/8/19102二.图的最小部分树（最小支撑树）如果G1是

例如,图b是图a的一个支撑树。

v6v5v2v3v4v1v6v5v2v3v4v1ab2023/8/19103例如,图b是图a的一个支撑树。v6v5v2abcfedhgbfed2023/8/19104abcfedhgbfed2023/8/5104abcfedhgbfdg2023/8/19105abcfedhgbfdg2023/8/5105bcedabcfedhg2023/8/19106bcedabcfedhg2023/8/5106abchabcfedhg2023/8/19107abchabcfedhg2023/8/5107afdgabcfedhg2023/8/19108afdgabcfedhg2023/8/5108定理1.图中任一个点i，若j

是与i相邻点中距离最近的，则边[i,j]一定包含在该图的最小部分树中。证明：反证法推论：把图的所有点分成V和两个集合，则两集合之间连线的最短边一定包含在最小部分树内。2023/8/19109定理1.图中任一个点i，若j是与i相邻点中距离最三.求最小部分树：避圈法和破圈法

寻找最小部分树的方法主要有避圈法和破圈法两种。

避圈法步骤：1.从图中任选一点vi，让vi

∈V，图中其余点均包含在中；2.从V

与的连线中找出最小边，这条边一定包含在最小部分树中，不妨设这条边为[vi,vj]将其加粗，标记为最小部分树中的边。3.令V∪vj→V，-vj→；4.重复2、3两步，一直到图中所有点均包含在V中。2023/8/19110三.求最小部分树：避圈法和破圈法寻找最小部分树的方法主要避圈法v1v2v3v4v5v6v1v3v1v3v2v1v3v2v5v6v1v3v2v5v6v4v1v3v2v52023/8/19111避圈法v1v2v3v4v5v6v1v3v1v3v2v1v3v

书上方法：

任选一点vi。找出与其相连的最小边，设为[vi,vj],找出与vi,vj点相连的最小边，设为[vj,vj+1],接下来找出与（vi,vj，,vj+1）相连的最小边，如果有两个相等的最小边，只要不构成圈都可以选。以此类推，直到所有的点选完为止。

特点：从任一顶点开始

2023/8/19112书上方法：2023/8/5112例：分别用两种避圈法构造下图的最小部分树。第一种解法：1.在点集中任选一点，不妨取S，令V={S}

2.找到和S

相邻的边中，权值最小的[S,A]。2023/8/19113例：分别用两种避圈法构造下图的最小部分树。第一种解法：1.3.V={S,A}4.重复第2，3步，找到下一个点。2023/8/191143.V={S,A}4.重复第2，3步，找到下一个首先从图中选一条权最小的边，然后连续从未被选取的边中选一条权最小的边，并使其与已选取的边不构成圈。在此过程中，如果有多条边的权都最小，则全选。当所选的边的数目等于n-1条为止，算法结束，则得到最小树。特点：从最小权的边开始

避圈法另一种做法：2023/8/19115首先从图中选一条权最小的边，然后连续从未被选取的边第二种做法求解过程：2023/8/19116第二种做法求解过程：2023/8/5116避圈法:原则为：从最短边开始添加，加边的过程中不能形成圈，直到点点连通(即:n-1条边)。5v1v2v3v4v5v68437526182023/8/19117避圈法:5v1v2v3v4v5v68437526182023树与图的最小树v1v2v3v4v5v6435215v1v2v3v4v5v6843752618MinC(T)=152023/8/19118树与图的最小树v1v2v3v4v5v6435215v1v2vv1v7v4v3v2v5v620159162532817412336避圈法2023/8/19119v1v7v4v3v2v5v62015916253281741v1v7v4v3v2v5v6201591625328174123362023/8/19120v1v7v4v3v2v5v62015916253281741v1v7v4v3v2v5v6201591625328174123362023/8/19121v1v7v4v3v2v5v62015916253281741v1v7v4v3v2v5v6201591625328174123362023/8/19122v1v7v4v3v2v5v62015916253281741v1v7v4v3v2v5v6201591625328174123362023/8/19123v1v7v4v3v2v5v62015916253281741v1v7v4v3v2v5v6201591625328174123362023/8/19124v1v7v4v3v2v5v62015916253281741v1v7v4v3v2v5v6201591625328174123362023/8/19125v1v7v4v3v2v5v62015916253281741破圈法求解步骤：①在网络图中寻找一个圈。若不存在圈，则已经得到最小树；②去掉该圈中权数最大的边；（如果有相同的几条边都是权最大的，任去其一）反复重复①②两步，直到最小树。特点：从任意一个圈开始2023/8/19126破圈法求解步骤：①在网络图中寻找一个圈。若不存在圈，则已经破圈法2023/8/19127破圈法2023/8/5127部分树2023/8/19128部分树2023/8/5128用破圈法求解上例：1.任意找到一回路，不妨取DETD，去掉边权最大的边[T,E];2023/8/19129用破圈法求解上例：1.任意找到一回路，不妨取DETD，2.从剩余的子图中任找一回路，同样去掉回路中边权最大的一条边，得一新的子图；依次类推。2023/8/191302.从剩余的子图中任找一回路，同样去掉回路中边权最大的一破圈法：任取一圈，去掉圈中最长边，直到无圈。5v1v2v3v4v5v6843752618v1v2v3v4v5v643521边数＝n-1=52023/8/19131破圈法：任取一圈，去掉圈中最长边，直到无圈。5v1v2v3vv1v2v3v4v5v643521得到最小树：MinC(T)=152023/8/19132v1v2v3v4v5v643521得到最小树：MinC(v1v7v4v3v2v5v6201591625328174123362023/8/19133v1v7v4v3v2v5v62015916253281741v1v7v4v3v2v5v6201591625328174123362023/8/19134v1v7v4v3v2v5v62015916253281741v1v7v4v3v2v5v62015916253281741232023/8/19135v1v7v4v3v2v5v62015916253281741v1v7v4v3v2v5v62015916253281741232023/8/19136v1v7v4v3v2v5v62015916253281741v1v7v4v3v2v5v615916253281741232023/8/19137v1v7v4v3v2v5v61591625328174123v1v7v4v3v2v5v615916253281741232023/8/19138v1v7v4v3v2v5v61591625328174123v1v7v4v3v2v5v69253281741232023/8/19139v1v7v4v3v2v5v69253281741232023v1v7v4v3v2v5v69253281741232023/8/19140v1v7v4v3v2v5v69253281741232023v1v7v4v3v2v5v693281741232023/8/19141v1v7v4v3v2v5v693281741232023/8v1v7v4v3v2v5v693281741232023/8/19142v1v7v4v3v2v5v693281741232023/8v1v7v4v3v2v5v6931741232023/8/19143v1v7v4v3v2v5v6931741232023/8/5v6v5v2v3v4图av162753544v3v2v1v4v6v5513142图b某六个城市之间的道路网如图a所示，要求沿着已知长度的道路联结六个城市的电话线网，使得电话线的总长度最短。2023/8/19144v6v5v2v3v4图av162753544v3v2v1v4解：这个问题的解决就是要求所示赋权图a中的最小支撑树。用破圈法求解。任取一个圈，例如（v1,v2,v3,v1

），去掉这个圈中权最大的边[v1,v3]。再取一个圈（v3,v5,v2,v3），去掉边[v2,v5]。再取一个圈（v3,v5,v4,v2,v3），去掉边[v3,v5]。再取一个圈（v5,v6,v4,v5），这个圈中，有两条权最大的边[v5,v6]和[v4,v6]。任意去掉其中的一条，例如[v5,v6]。这时得到一个不含圈的图，如图b所示，即是最小支撑树。

2023/8/19145解：这个问题的解决就是要求所示赋权图a中的最小支撑破圈法的另一种解法：1.从剩余图中找到权最大的一条边，如果将其删除后图仍然是连通的，则删除此边，否则不再考虑此边；2.重复上述步骤，直到剩余边数为

n-1为止。

特点：从最大权的边开始

用此法求解上述问题：2023/8/19146破圈法的另一种解法：1.从剩余图中找到权最大的一条边，如果将注意：1.一个图的最小部分树不唯一，该题中用几种解法得到的结果都是相同的，是特殊情况；2.不同解法得到的最小部分树所包含的边虽然可能不相同，但是，每个最小部分树中所有边权的总和一定都是相同的，即都达到了最小。2023/8/19147注意：1.一个图的最小部分树不唯一，该题中用几种解法得到的结课堂练习：3749346321MinC(T)=12MinC(T)=15254173314475答案：2023/8/19148课堂练习：3749346321MinC(T)=12Min34122323242MinC(T)=12213638534567454321MinC(T)=182023/8/1914934122323242MinC(T)=12213638536.4、做一道，熟悉一下各种方法6.5、最小部分树避圈法破圈法6.6、树是边数比顶点少1，而且无圈的连通图2023/8/191506.4、做一道，熟悉一下各种方法2023/8/5150§3．最短路问题如何用最短的线路将三部电话连起来？此问题可抽象为设△ABC为等边三角形，连接三顶点的路线（称为网络）。这种网络有许多个，其中最短路线者显然是二边之和（如AB∪AC）。ABC2023/8/19151§3．最短路问题如何用最短的线路将三部电话连起来？ABC20最短路问题ABCP但若增加一个周转站（新点P），连接4点的新网络的最短路线为PA＋PB＋PC。最短新路径之长N比原来只连三点的最短路径O要短。这样得到的网络不仅比原来节省材料，而且稳定性也更好。2023/8/19152最短路问题ABCP但若增加一个周转站（新点P），连接4点的新最短路问题是指从给定的网络图中找出任意两点之间距离最短（权值和最小）的一条路。

最短路问题是图论中十分重要的最优化问题之一，它作为一个经常被用到的基本工具，可以解决生产实际中的许多问题，比如城市中的管道铺设、线路安排、工厂布局、设备更新、投资、某些整数规划和动态规划等等。2023/8/19153最短路问题是指从给定的网络图中找出任意两点之间距最短路的求法：1.从某一点至其它各点之间最短距离的狄克斯屈拉(Dijksrta

)算法；2.求网络图中任意两点之间的最短距离的矩阵算法。2023/8/19154最短路的求法：2023/8/5154

Dijkstra算法（重点内容）在一个赋权无向图中寻求最短路的方法——Dijkstra算法，它是在1959年提出来的。目前公认，在所有的权wij

0时，这个算法是寻求最短路问题最好的算法。并且，这个算法实际上也给出了寻求从一个始点vs到任意一个点vj的最短路。

学习方法：第一次完整看一下方法，以后不用这么多理论了，直接在图上算就可以了。2023/8/19155Dijkstra算法（重点内容）学习方法：第

一.Dijkstra算法1.设

dij

表示图中两相邻点

i

与j

的距离，若i

与j

不相邻，令dij

=∞，显然dii=0。

Dijkstra算法假设：基本思路：如果v1→v2→v3→v4是v1→v4

的最短路径，则v1→v2→v3

一定是v1→v3

的最短路径。v2→v3→v4

一定是v2→v4的最短路径。设Lsi表示从s点到i

点的最短距离。2023/8/19156一.Dijkstra算法1.设dij表示图中两相Dijkstra算法步骤：1.对起始点s，因Lss=0，将0标注在s旁的小方框内，表示s点已标号；2.从点s

出发，找出与s相邻的点中距离最小的一个，设为

r，将Lsr=Lss+dsr的值标注在r

旁的小方框内（也即将起点与该点距离标在该点处），表明点r

也已标号；3.从已标号的点出发，找出与这些点相邻的所有未标号点p，若有Lsp=min{Lss+dsp,Lsr+drp}（注意：s、r为已经标号的点，p为未标号点）,

则对p点标号，并将Lsp的值标注在p点旁的小方框内。此步骤也即从所有已经标号的点的所有相邻点中找出Lsp（方框中的值加相邻边的值）最小的一个（注：如果有两个或两个以上相等同为最小的，都标）；4.重复第3步，直到

t

点得到标号为止。求从起始点s

到终止点t的最短路径。2023/8/19157Dijkstra算法步骤：1.对起始点s，因Lss=0，将例.求下图中从v1到v7的最短路。解：(1)

从v1点出发，对v1点标号，将L11=0标注在旁的小方框内，令v1∈V，其余点属于；2023/8/19158例.求下图中从v1到v7的最短路。解：(1)L1r=min{0+d12

,0+d13

}=min{5,2}=2=L13(2)

同v1相邻的未标号点有v2、v3，2023/8/19159L1r=min{0+d12,0+d13}(2对

v3

标号，将L13的值标注在v3旁的小方框内；将(v1,v3)加粗，并令V∪v3→V，。2023/8/19160对v3标号，将L13的值标注在v3旁的小方框内；将L1p=min{L11+d12

,L13+d34,L13+d36

}=min{0+5,2+7,2+4}=5=L12(3)

同v1,v3相邻的未标号点有v2、v4、v6，2023/8/19161L1p=min{L11+d12,L13+d34对

v2

标号，将L12的值标注在v2旁的小方框内；将(v1,v2)加粗，并令V∪v2→V，2023/8/19162对v2标号，将L12的值标注在v2旁的小方框内；L1p=min{L12+d25

,L12+d24,

L13+d34

,L13+d36

}=min{5+7,5+2,2+7,2+4}=6=L16。(4)

同v1,v2

,v3相邻的未标号点有v4、v5、v6，2023/8/19163L1p=min{L12+d25,L12+d2对

v6

标号，将L16的值标注在v6旁的小方框内；将(v3,v6)加粗，并令V∪v6→V，2023/8/19164对v6标号，将L16的值标注在v6旁的小方框内；L1p=min{L12+d25

,L12+d24,L13+d34

,L16+d64,L16+d65,L16+d67

}=min{5+7,5+2,2+7,6+2,6+1,6+6}=7=L14=L15(5)

同v1,v2

,v3,

v6相邻的未标号点有v4、v5、v7，2023/8/19165L1p=min{L12+d25,L12+d2对

v4,v5同时标号，将L14=L15的值标注在v4,v5旁的小方框内；将(v2,v4),(v6,v5)加粗，并令V∪v4∪v5→V，2023/8/19166对v4,v5同时标号，将L14=L15的值标L1p=min{L15+d57

,L16+d67

}=min{7+3,6+6}=10=L17(6)

同v1,v2

,v3,v4,v5,

v6相邻的未标号点只有v7，2023/8/19167L1p=min{L15+d57,L16+d67

对

v7

标号，将L17的值标注在v7旁的小方框内；将(v5,v7)加粗。图中绿色线表明从点v1到网络中其它各点的最短路，各点旁的数字就是点v1到各点的最短距离。2023/8/19168对v7标号，将L17的值标注在v7例：求下图v1到各点的最短距离及最短路线。①②③④⑤⑥⑦⑧45261783932612161804522310396126411661881224824182023/8/19169例：求下图v1到各点的最短距离及最短路线。①②③④⑤⑥⑦⑧4v1到各点的最短距离及最短路线如图所示：①②③④⑤⑥⑦⑧45261783932612161802618所有点都已标号，点上的标号就是v1到该点的最短距离，最短路线就是红色的链。2023/8/19170v1到各点的最短距离及最短路线如图所示：①②③④⑤⑥⑦⑧45例：求v1到v8的最短路6623643241102213v1V2V3V4V5V6V7V8V92023/8/19171例：求v1到v8的最短路6623643241102213v1最短路问题算法适用条件：Dijkstra算法只适用于全部权为非负情况，如果某边上权为负的，算法失效。此时可采用逐次逼近算法。例：如右图所示中按dijkstra算法可得P(v1)=5为从vs→v1的最短路长显然是错误的，从vs→v2→v1路长只有3。v2vsv15-582023/8/19172最短路问题算法适用条件：例：如右图所示中按dijkstra算二.求任意两点间最短距离的矩阵算法用Dijkstra

算法只能计算从图中某一点到其他点的最短距离，如果要计算各点之间的最短距离就需要对每个点分别计算，而用矩阵算法则可以同时求出所有各点间的最短距离。

思路：vi到vj的最短路可能中间要经过若干个点（若干步）。基本思想是在最短路线上任意两点间路线也是最短路线。利用vi到vj的一步距离求出vi到vj的两步距离，再求出vi到vj的四步距离、八步距离……经有限次迭代可求出vi到vj的最短距离。

2023/8/19173二.求任意两点间最短距离的矩阵算法用Dijks解.设

dij

表示图中两相邻点i

与j

的距离，若i

与j

不相邻，令dij

=∞，显然dii=0。建立距离矩阵：例.利用矩阵算法求上述网络图中各点间的最短距离。=D（0）2023/8/19174解.设dij表示图中两相邻点i与j的距离，若从上述距离矩阵可以看出从i点到

j点的直接距离，但从i到j的最短距离不一定就是从i点直接到

j点。如上述问题中，从v1→v2的最短距离应该是min{d11+d12,d12+d22,d13+d32,d14+d42,d15+d52,d16+d62,d17+d72}即min{d1r+dr2}。因此可以构造一个新的矩阵D(1)，令D(1)中每一个元素为：dij(1)=min{dir（0）

+drj（0）

}，则矩阵D(1)给出了网络中任意两点之间直接到达及经由一个中间点时的最短距离。元素为∞，说明两点之间不能一步到达。

2023/8/19175从上述距离矩阵可以看出从i点到j点的直接距离，但从2023/8/191762023/8/5176再构造矩阵D(2)，

dij(2)=min{dir(1)

+drj(1)}。依次类推构造矩阵D(k)，

dij(k)=min{dir(k-1)

+drj(k-1)}

计算停止的控制：

p是图中顶点数。给出了任意两点直接到达，及包括经过一个、两个、三个中间点时的最短距离到D(m+1)=D(m)时，计算也可结束，矩阵中各个元素值即为所求2023/8/19177再构造矩阵D(2)，dij(2)=min{dir(该例中k=32023/8/19178该例中k=32023/8/5178

上述D(2)

中的元素给出了各点间的最短距离，但是并没有给出具体是经过了哪些中间点才得到的这个最短距离，如果要知道中间点具体是什么，需要在计算过程中进行记录。教材178页例52023/8/19179上述D(2)中的元素给出了各点间的最短距参考内容：1.狄克斯屈拉方法

适用于满足所有权系数大于等于0（lij≥0）的网络最短路问题，能求出起点v1到所有其他点vj的最短距离；2.海斯方法(矩阵算法）

基本思想是在最短路线上任意两点间路线也是最短路线。利用vi到vj的一步距离求出vi到vj的两步距离再求出vi到vj的四步距离……经有限次迭代可求出vi到vj的最短距离；3.福德方法（逐次逼近算法）适用于有负权系数，但无负回路的有向或无向网络的最短路问题，能求出起点v1到所有其它点vj的最短距离。2023/8/19180参考内容：2023/8/51806.7、练习6.8、实验课6.9、课后有答案6.10、练习6.11、13、14课下6.12构造有向图，以①、②、③、④、⑤表示各年初（同时也是上年末），弧旁的数字表示第i年初（即第j-1年末）买新车用到第j年初卖掉时的总支出费用，记作dij2023/8/191816.7、练习2023/8/5181例：设备更新问题。某公司使用一台设备，在每年年初，公司就要决定是购买新的设备还是继续使用旧设备。如果购置新设备，就要支付一定的购置费，当然新设备的维修费用就低。如果继续使用旧设备，可以省去购置费，但维修费用就高了。请设计一个五年之内的更新设备的计划，使得五年内购置费用和维修费用总的支付费用最小。已知：设备每年年初的价格表年份12345年初价格11111212132023/8/19182例：设备更新问题。某公司使用一台设备，在每年年初，公司就要决设备维修费如下表使用年数0-11-22-33-44-5每年维修费用5681118解：将问题转化为最短路问题，如下图：用vi表示“第i年年初购进一台新设备”,弧（vi,vj）表示第i年年初购进的设备一直使用到第j年年初。v1v2v3v4v5v62023/8/19183设备维修费如下表使用年数0-11-22-33-44-5每年维把所有弧的权数计算如下表，把权数赋到图中，再用Dijkstra算法求最短路。123456116223041592162230413172331417235186v1v2v3v4v5v6162230415916223041312317181723W12=11+5=16W13=11+5+6=22W14=11+5+6+8=30W15=11+5+6+8+11=41W16=11+5+6++8+11+18=59W23=11+5=16W24=11+5+6=22W25=11+5+6+8=30W26=11+5+6+8+11=41W34=12+5=17W35=12+5+6=23W36=12+5+6+8=31W45=12+5=17W46=12+5+6=23W56=13+5=182023/8/19184把所有弧的权数计算如下表，把权数赋到图中，再用Dijkstr最短路问题最终得到下图，可知，v1到v6的距离是53，最短路径有两条：v1→v3→v6和v1→v4→v6

V1（0,s）v3v4(41,1)v5v62230415916(22,1)3041312317181723

V2（16,1）16(30,1)(53,3)(53,4)2023/8/19185最短路问题最终得到下图，可知，v1到v6的距离是53，最短§4．网络的最大流在许多实际的网络系统中都存在着流量和最大流问题。例如铁路运输系统中的车辆流、城市给排水系统的水流问题、金融系统的现金流、通讯系统的信息流、物流等等。而网络系统的最大流问题是图与网络理论中十分重要的最优化问题，它对于解决有关生产实际问题起着十分重要的作用。2023/8/19186§4．网络的最大流在许多实际的网络系统中都存在着例：如何制定一个运输计划使生产地到销售地的产品输送量最大。这就是一个网络最大流问题。2023/8/19187例：如何制定一个运输计划使生产地到销售地的产品输送量最大。这一.网络最大流的有关概念1.有向图与容量网络图中每条边有规定指向的图称为有向图，有向图的边称为弧，记作(vi,vj)，表示方向从点vi指向点vj。有向图是点与弧的集合，记作D(V,A)。弧(vi,vj)的最大通过能力，称为该弧的容量，记为c(vi,vj)，或简记为cij。定义了弧容量的网络称为容量网络。2023/8/19188一.网络最大流的有关概念1.有向图与容量网络图中每条边容量网络通常规定一个发点(源点，记为s)一个收点(汇点，记为t)，网络中其余的点称为中间点。从发点到收点之间允许通过的最大流量称为最大流。多个收(发)点的网络可以转换为只含一个收(发)点。2.流与可行流流是指加在网络各条弧上的一组负载量，对加在弧(vi,vj)上的负载量记作f(vi,vj)，或简记作

fij，若网络上所有的fij=0，这个流称为零流。2023/8/19189容量网络通常规定一个发点(源点，记为s)一个收点(汇点，记为以v(f)表示网络中从s→t

的流量，则称网络上满足下述条件(1)、(2)的流为可行流：(1)容量限制条件:对所有弧有0≤f(vi,vj)

≤c(vi,vj)（6.6）(2)中间点平衡条件：∑f(vi,vj)-∑f(vj,vi)

=0(i≠s,t)（6.7）即每一个弧上的流量不能超过它的最大通过能力（即容量）。对于中间点，每一个中间点的流入量与流出量的代数和等于零；（节点没有容量限制，流在节点不会存储）其中发点的总流出量（或收点的总流入量）v(f)

叫做这个可行流的流量，发点的总流出量和收点的总流入量必相等。（6.8）2023/8/19190以v(f)表示网络中从s→t的流量，则称网络