第十二周-图与网络分析-基本知识

1、第五章 图与网络分析线性规划问题的引出 | 线性规划问题的概念和模型 | 线性规划的标准型 | 线性规划模型的标准化 第五章 图与网络分析 图与网络的基本知识1树2最短路问题3最大流问题4第一节 图与网络的基本知识 图论概述p 图论是运筹学中应用非常广泛的一个重要分支，它已经广泛地应用于物理学控制论，信息论，工程技术，交通运输，经济管理，电子计算机等各项领域。p 经济和社会生活中的许多问题，可以同图论的理论和方法来加以解决。如：通信线路的架设，输油管道的铺设，铁路或者公路交通网络的合理布局等问题，都可以应用图论的方法，简便、快捷地加以解决。2022-4-27西南财经大学统计学院p 图论的起源可

2、以追溯到18世纪，早期的图论主要研究一些游戏或纯理论问题，诸如：四色问题（1840）、哈密尔顿问题（1859）、哥尼斯堡七桥问题（1736） 。p哥尼斯堡七桥问题（1736） ：18世纪的普鲁士哥尼斯堡城中有一条河，河的两岸与河中的两个小岛有7座桥彼此联接，问一个步行者能否通过每座桥一次且仅一次就能返回原出发地？2022-4-27西南财经大学统计学院问题：能否从任一块陆地出发，走过七座桥，且每座桥只走过一次，最后回到出发点？欧拉将哥尼斯堡七桥问题转化为仅包含点、线的拓扑结构。2022-4-27西南财经大学统计学院哥尼斯堡七桥问题可简化为如此图形：A AB BC CD D2022-4-27西南财

3、经大学统计学院C CA AD DB B问题简化为：在该图中，从任一点出发，能否通过每条线段一次且仅仅一次后又回到原来的出发点。天才在于勤奋，天才在于勤奋，数学家欧数学家欧拉：所有人的拉：所有人的老师老师http:/ store: 7 Bridges master 一笔画问题一笔画问题 2022-4-27西南财经大学统计学院2022-4-27西南财经大学统计学院 一、图的基本概念 在生产和日常生活中，人们常用点和线画出的示意图来反映一些对象之间的关系。铁路交通图铁路交通图比赛关系图比赛关系图v1v2v3v4v5v6v32022-4-27西南财经大学统计学院美国航空网美国航空网城市公共交通网城市公

4、共交通网2022-4-27西南财经大学统计学院人类传染病网络人类传染病网络万维网万维网wwwwww2022-4-27西南财经大学统计学院Company LogoE 在图中，以点代表研究的对象，点与点之间的连线表示这两个对象之间的特定关系。它不同与通常的几何图和函数图，特点如下：u 点只是某种事物的一种抽象；u 连线代表某些事物之间的关系。u 这种图是一种关系示意图，点与连线的画法具有随意性，连线的方式不重要。u 在保持相对位置与关系不变的前提下，点的位置、线的长度不一定要按照实际位置和实际长度来表示。图是反映对象之间关系的一种工具2022-4-27西南财经大学统计学院 定义：图由有限个顶点的集

5、合V和表达顶点之间关系的边集E所组成。l G=（ V，E） 其中V=v1，v2， ，vn为点集合，表示n个事物，vi 叫做顶点。 l E为边集合，反映事物之间的联系，E= e1,e2，em，ek叫做边。l 连接点vi , vjV 的边记作vi , vj，或者vj , vi。(1) 图的定义与表示v1v2v3v4v5e1e2e3e4e5e6),(),(65432154321eeeeeeE 图的表示,111 e,212 e,313 e,324 e,325 e,436 e2022-4-27西南财经大学统计学院(2) 图的分类图无向图，记作G=(V，E )有向图，记作D=(V，A)有向图的边称为弧。v

6、4v6v1v2v3v5V = v1 , v2 , v3 , v4 , v5 , v6 ，A = (v1 , v3 ) , (v2 , v1) , (v2 , v3 ) ,(v2 , v5 ) , (v3 , v5 ) , (v4 , v5 ) , (v5 , v4 ) , (v5 , v6 ) 2022-4-27西南财经大学统计学院v1v2v3v4v5e1e2e3e4e5e6u 端点和关联边 的的关关联联边边和和是是点点边边的的端端点点，是是边边、则则称称点点若若jikkjijikvveevvEvve, u 相邻点和相邻边u 多重边与环点点的的边边称称为为环环。两两个个端端点点落落在在同同一一

7、个个顶顶多多重重边边或或平平行行边边；具具有有相相同同端端点点的的边边称称为为边边边称为相邻边，简称邻边称为相邻边，简称邻端点落在同一个顶点的端点落在同一个顶点的相邻点，简称邻点，相邻点，简称邻点，一条边的两个端点称为一条边的两个端点称为(3) 图的基本概念2022-4-27西南财经大学统计学院u多重图和简单图为为简简单单图图。无无环环也也无无多多重重边边的的图图称称重重图图；含含有有多多重重边边的的图图称称为为多多v1v2v3v4v5e1e2e3e4e5e62022-4-27西南财经大学统计学院u 完全图u二部图（偶图）若能将若能将G=G=（V,EV,E） 的顶点集的顶点集V V划分成两个子

8、划分成两个子集集 X X和和Y Y（X X交交Y Y为空集），使得为空集），使得G G中任何一条中任何一条边的两个端点一个属于边的两个端点一个属于X X，另一个属于，另一个属于Y Y，则，则称称G G为二部图（也称偶图），为二部图（也称偶图），X X、Y Y称为互补顶称为互补顶点子集，此时可将点子集，此时可将G G记成记成G=G= (X,Y,E). (X,Y,E). v1v3v5v2v4v6 每一对顶点间都有边相连的无向简单图称为完全图。每一对顶点间都有边相连的无向简单图称为完全图。 有有向完全图则是指任意两个顶点之间有且仅有一条有向边的简单图。向完全图则是指任意两个顶点之间有且仅有一条有向边

9、的简单图。2022-4-27西南财经大学统计学院v1v7v6v5v4v3v2V=v1 , v2 , v3 , v4 , v5 ,v6 , v7 d(v1)=3 ; d(v2)=5 ;d(v3)=4 ; d(v4)=4 ;d(v5)=1 ; d(v6)=3;d(v7)=0其中其中 v5 为悬挂点，为悬挂点， v7 为孤立点。为孤立点。2022-4-27西南财经大学统计学院 定理1. 所有顶点度数之和等于所有边数的2倍。 定理2. 在任一图中，奇点的个数必为偶数。 有向图中，所有顶点的入次之和等于所有顶点的出次之和。 有向图中，以 vi 为始点的边数称为点vi 的出次，用 表示； 以vi 为终点的

10、边数称为点vi 的入次，用 表示； vi 点的出次和入次之和就是该点的次。)(ivd )(ivd l 顶点的度（次）的性质v1v2v3v4v5图的连通性：链与路、圈与回路链 点边交错的序列圈起点=终点的链路点弧交错的序列回路起点=终点的路v1v2v3v4v5无向图：有向图：l 链中的点均不相同，则称为初等链。l 链中的边均不相同，则称为简单链。2022-4-27西南财经大学统计学院44322112vevevevQ 初等链初等链路路v3v1e1v2e2e4v4e5v5e6e7e9e8初等链-无重边、无重点2022-4-27西南财经大学统计学院1956452113vevevevevQ 初等圈初等圈

11、回路v3v1e1v2e2e4v4e5v5e6e7e9e8初等圈初等圈-无重边、无重边、无重点，起点除外无重点，起点除外2022-4-27西南财经大学统计学院4528572111vevevevevQ 简单链简单链v3v1e1v2e2e4v4e5v5e6e7e9e8e4无重边无重边任何两点之间至少存在一条链的图称为连通图，否则称为不连通图。G1G2G1为不连通图， G2为连通图例 ：连通图图G=(V，E)和G=(V ,E )，若V V 且E E ，则称G 为G的子图。 子 图 v1v2v3v4v5v6v7e1e2e3e4e5e6e7e8e9e10e11(a)e5e7v1v2v5v6v7e1e6e8

12、(b)子图子图v1v2v3v4v5v6v7e1e2e3e4e5e6e7e8e9e10e11(a)图G=(V，E)和G=(V ，E )，若V =V 且E E ，则称G 为G的支撑子图。 支撑子图v1v2v3v4v5v6v7e1e2e3e4e5e6e7e8e9e10e11(a)e5e7v1v2v5v6v7e1e6e8(b)子图子图v1v2v3v4v5v6v7e1e6e7e9e10e11(c)支撑子图支撑子图v1v2v3v4v5v6v7e1e2e3e4e5e6e7e8e9e10e11(a)网络（或赋权图）l 网络图：给图中反映联系的边赋一数值，称为权，来表明一定的含义。赋有权的图称为网络图。v2v3

13、4v1v4v5v6v7221255253367无向网络图l 图只能用来研究事物之间有没有某种关系，而不能研究这种关系的强弱程度。2022-4-27西南财经大学统计学院总结：无向图的基本概念v 点与边 每一条边和两个节点关联，一条边可以用两个节点的标号表示（i，j）ji4231v链 前后相继的点边序列 P=(1,2),(2,3),(3,4)4231v圈 起点和终点重合的链称为圈 p=(1,2),(2,4),(4,3),(3,1) 圈中各条边方向不一定相同42312022-4-27西南财经大学统计学院总结：有向图的基本概念v 点与弧（有向边) 每一条弧和两个节点关联，一条弧可以用两个节点的标号表示

14、（i，j）jiv路径 前后相继并且方向相同的弧序列 P=(1,3),(3,2),(2,4)423142312022-4-27西南财经大学统计学院v 回路（Circuit） 起点和终点重合的路径称为回路 =(1,2),(2,4),(4,1) 回路中各条边方向相同4231v 链（Chain） 前后相继但是方向不一定相同的边的序列称为链 C=(1,2),(3,2),(3,4)4231总结：有向图的基本概念（4）图的矩阵表示Company Logo 对于网络（赋权图）G=（V，E），其中边有权 ，构造矩阵 ，其中： 称矩阵A为网络G的权矩阵。),(jivvjiw EvvEvvwajijijiji),(

15、0),(nnjiaA )(权矩阵权矩阵3v5v2v3v4v147569248 06507608445803204309742905432154321vvvvvAvvvvv nnjiaA )( EvvEvvajijiji),(0),(1 设图G=（V，E）中顶点的个数为n，构造一个矩阵 ， 其中： 称矩阵A为网络G的邻接矩阵。 邻接矩阵 邻接矩阵的行和列都与图的顶点相对应。 对无向图G，令 aij =顶点vi与顶点vj关联的边数，若点vi与点vj不关联则有aij =0，得到AG=（aij）p*q为G的邻接矩阵。 对有向图D，令 aij =以顶点vi为起点vj为终点的弧数，则得到AD=（aij）p

16、*q为D的邻接矩阵。2022-4-27西南财经大学统计学院v1v2v4v3e1e2e3e4e5e6v1v2v4AG =v1v2v3v4v30 1 0 1 1 0 1 1 0 1 0 2 1 1 2 0 v3a1v1v2v4a2a4a3a5a6RD =v1v2v3v4 0 0 1 0 1 0 0 1 1 0 0 0 0 1 1v1v2v3v4 02022-4-27西南财经大学统计学院邻接矩阵的特点 在相邻矩阵中，对无向图每一行或每一列元素之和， 等于相应顶点相关联的边数，且为对称矩阵。 对有向图，其每一行元素之和等于由该顶点射出的弧数，每列元素之和等于射入该顶点的弧数。2022-4-27西南财经

17、大学统计学院654321654321 010101101001010111101010001101111010vvvvvvvvvvvvB 权矩阵为：邻接矩阵为：v5v1v2v3v4v6433225643712345612345604643402720536750242033330 vvvAvvvvvvvvv2022-4-27西南财经大学统计学院运筹学中研究的图具有下列特征：（1）用点表示研究对象，用边（有方向或无方向）表示对象之间某种关系。（2）强调点与点之间的关联关系，不讲究图的比例大小与形状。（3）每条边上都赋有一个权，其图称为赋权图。实际中权可以代表两点之间的距离、费用、利润、时间、容量

18、等不同的含义。（4）建立一个网络模型，求最大值或最小值。（二）欧拉回路与中国邮路问题Company Logo1. 欧拉道路（一笔画问题）道道路路，则则称称这这条条道道路路为为欧欧拉拉每每一一条条边边一一次次且且仅仅一一次次中中的的存存在在一一条条道道路路，经经过过是是一一个个无无向向连连通通图图，若若设设GG一一条条欧欧拉拉道道路路：的的到到存存在在42vv一一条条欧欧拉拉道道路路：的的到到存存在在43vv,441122433vevevevev1e2e3e4e1v2v3v4v1e2e3e4e5e6e1v2v3v4v5v1e3e2e1v2v3v4v存存在在条条欧欧拉拉道道路路任任两两点点之之间间

19、都都不不,4456223345112vevevevevevev（2）欧拉回路Company Logo回路回路，则称这个回路为欧拉，则称这个回路为欧拉每一条边一次且仅一次每一条边一次且仅一次中的中的存在一个回路，经过存在一个回路，经过是一个无向连通图，若是一个无向连通图，若设设GG,164455274332211vevevevevevevev存在欧拉回路：该图特点：该图特点：均均为为偶偶数数)(ivd该图不存在欧拉回路 存存在在奇奇点点1v2v1e2e3e4e5e3v4v5v6e7e1e2e3e4e5e1v2v3v4v具有欧拉回路的图具有欧拉回路的图为欧拉图为欧拉图定理3：无向连通图G为欧拉图的

20、充要条件是，当且仅当G中无奇点。推论1：无向连通图G为欧拉图，当且仅当G的边集可划分为若干个初等回路。推论2：无向连通图G有欧拉道路的充要条件是G中恰有两个奇点。定理4：有向连通图G为欧拉图的充要条件是，当且仅当它每个顶点的出次等于入次。一笔画问题：1. 一个连通图的顶点都是偶点，没有奇点，则该图 可以一笔画出（从任一点出发均可）。2. 一个连通图的顶点恰有两个奇点，其余均为偶点， 则从任一奇点出发，可以一笔画出该图，而终点 则是另一个奇点。3. 一个连通图的顶点有两个以上的奇点，则该图 不能一笔画出。邮递员送信邮递员邮递员从邮局出发，要把信送往从邮局出发，要把信送往各个地点，由于送信地点各个

21、地点，由于送信地点多，多，(“”代表送信地点代表送信地点)，道路不好走，道路不好走，(两个送信地两个送信地点之间必须要经过一个空点之间必须要经过一个空白方格白方格“”“”，而且不能走，而且不能走对角对角)，还要绕过房子，出，还要绕过房子，出发前他要设计了发前他要设计了一条一条送信送信路线，从邮局出发不但把路线，从邮局出发不但把信送到了每一个地点，信送到了每一个地点，而而且路线且路线不重复，最后回到不重复，最后回到邮局。在图中画出邮递员邮局。在图中画出邮递员的行走路线。的行走路线。（3）中国邮路问题管梅谷教授（1962）提出提出的问题：一个邮递员从邮局出发分送邮件，要走完他负责投递的所有街道，最

22、后再返回邮局，应如何选择投递路线，才能使所走的路线最短？邮路问题的图论描述：取一无向赋权连通图G=（V，E）E中的每一条边对应一条街道每条边的非负权=街道的长度V中某一个顶点为邮局，其余为街道的交叉点在G上找一个圈，该圈过每边至少一次，且圈上所有边的权和最小。1. 若G中的顶点均为偶点 ，即G中存在欧拉回路，则该回路过每条边一次且仅一次，此回路即为所求的投递路线2. G中有奇点：不存在欧拉回路投递路线：有街道要重复走一次或多次为为邮邮局局为为邮邮路路图图，其其中中例例：设设1vG不不是是欧欧拉拉图图为为奇奇数数Gvdvd,)(),(43不不存存在在欧欧拉拉回回路路，G即不存在每条街道走一次且只

23、走一次的投递路线14253214563211vvvvvvvvvvvvvC ：路路线线12权和1232563542412vvvvvvvvvvvvC ：路路线线11权和12CC 优优于于路路线线路路线线分析：），），（，），（，重重复复走走过过边边：（路路线线4132211vvvvvvC），），（，重重复复走走过过边边：（路路线线32422vvvvC2 重重复复边边的的权权和和结论：选择最佳投递路线=选择重复边的权和最小的路线3 重重复复边边的的权权和和1v2v3v4v5v6v1111111111v2v3v4v5v6v11111111114253214563211vvvvvvvvvvvvvC ：对

24、对路路线线），），（，），（，重重复复边边：（413221vvvvvv1G为欧拉图，1G的的一一条条欧欧拉拉回回路路为为且且11GC1232563542412vvvvvvvvvvvvC ：对对路路线线），），（，重重复复边边：（3242vvvv1v2v3v4v5v6v1111111112G为欧拉图，2G的的一一条条欧欧拉拉回回路路为为且且22GC欧拉图欧拉图一条投递路线对应一个一条投递路线对应一个条条欧欧拉拉回回路路且且投投递递路路线线为为该该图图的的一一对对邮路图邮路图G，的的一一条条链链到到任任取取奇奇点点34vv3654,vvvv如如：对该链上的每一条边增加一条重复边对该链上的每一条边增

25、加一条重复边G为为欧欧拉拉图图G 存存在在欧欧拉拉回回路路即即G ,CG 对对应应一一条条投投递递路路线线即即 1v2v3v4v5v6v111111111G1v2v3v4v5v6v111111111投递路线欧拉图1454256536321vvvvvvvvvvvvvC：Company Logo如上分析结论：l 对任意一个含奇点的邮路图G，由于奇点的个数为偶数个，把每两个配成一对，由于G为连通图，每对奇点之间至少存在一条链，对该条链上的每一条边增加一条重复边，可得一欧拉图，该欧拉图对应一条投递路线。寻找最佳投递路线方法：l 在原邮路图上增加一些重复边得一个欧拉图，在所得欧拉图上找出一条欧拉回路。计

26、算重复边的权和，重复边权和最小欧拉回路即为所求的最佳投递路线。中国邮路问题求解方法奇偶点图上作业法第一步：确定一个初始可行方案方法：检查图G中是否有奇点无奇点：图G已是欧拉图 ，找出一条以v1为起点的欧拉回路，该回路就是最佳投递路线。 有奇点：把所有奇点两两配成一对，每对奇点找一条链，在该条链上的每一条边增加一条重复边，得一个欧拉图G1， 由G1所确定的欧拉回路即为一个可行方案例：求解右图所示的邮路问题v v2 2，v v8 8，v v4 4，v v6 6G G中有奇点：中有奇点：取取v v2 2到到v v4 4的一条链：的一条链：v v2 2v v1 1v v6 6v v7 7v v8 8v

27、 v9 9v v4 4取取v v6 6到到v v8 8的一条链：的一条链：v v6 6v v1 1v v2 2v v3 3v v4 4v v9 9v v8 8V V1 1是邮局是邮局G G1v2v3v6v4v5v24346957v8v9v44354G1显然G1不是最佳方案G1是欧拉图，第二步：调整可行方案， 使重复边权和下降重复边权和=51若图中某条边有两条或多于两条的重复边同时去掉偶数条，使图中每一条边最多有一条重复边G2的重复边权和=211v2v3v6v4v5v24346957v8v9v4435步骤1.可得到重复边权和较小的欧拉图。4G21v2v3v6v4v5v24346957v8v9v4

28、43542. 使图中每个初等圈重复边的 权和不大于该圈权和的一半13个初等圈1v2v3v6v4v5v24346957v8v9v4435G34G3是欧拉图，重复边权和=17G31v2v3v6v4v5v24346957v8v9v443546（1）v1v2v5v6v1167（2）v6v5v8v7v61410（3）v2v3v4v5v2244（4）v5v4v9v8v516G3的初等圈的初等圈权和权和重复边权和重复边权和13（5）v1v2v5v8v7v6v124G41v2v3v6v4v5v24346957v8v9v44354G42v3v6v4v5v24346957v8v9v443547（1）v1v2v5v6v1164（2）v6v5v8v7v6144（3）v2v3v4v5v2248（4）v5v4v9v8v51