运筹学图与网络分析

图与网络分析(GraphTheoryandNetworkAnalysis)图与网络的基本知识最短路问题树及最小树问题最大流问题1可编辑ppt哥尼斯堡七桥问题哥尼斯堡（现名加里宁格勒）是欧洲一个城市，Pregei河把该城分成两部分，河中有两个小岛，十八世纪时，河两边及小岛之间共有七座桥，当时人们提出这样的问题：有没有办法从某处（如A）出发，经过各桥一次且仅一次最后回到原地呢？2可编辑pptBDACABCD哥尼斯堡七空桥一笔画问题3可编辑ppt哈密尔顿（Hamilton）回路是十九世纪英国数学家哈密顿提出，给出一个正12面体图形，共有20个顶点表示20个城市，要求从某个城市出发沿着棱线寻找一条经过每个城市一次而且仅一次，最后回到原处的周游世界线路（并不要求经过每条边）。4可编辑ppt5可编辑ppt6可编辑ppt7可编辑ppt8可编辑ppt9可编辑ppt10可编辑ppt11可编辑ppt12可编辑ppt13可编辑ppt14可编辑ppt15可编辑ppt16可编辑ppt17可编辑ppt18可编辑ppt19可编辑ppt20可编辑ppt21可编辑ppt有7个人围桌而坐，如果要求每次相邻的人都与以前完全不同，试问不同的就座方案共有多少种？用顶点表示人，用边表示两者相邻，因为最初任何两个人都允许相邻，所以任何两点都可以有边相连。22可编辑ppt123764523可编辑ppt123764524可编辑ppt123764525可编辑ppt123764526可编辑ppt123764527可编辑ppt123764528可编辑ppt123764529可编辑ppt123764530可编辑ppt得到第一次就座方案是（1，2，3，4，5，6，7，1），继续寻求第二次就座方案时就不允许这些顶点之间继续相邻，因此需要从图中删去这些边。31可编辑ppt123764532可编辑ppt123764533可编辑ppt123764534可编辑ppt123764535可编辑ppt123764536可编辑ppt123764537可编辑ppt123764538可编辑ppt123764539可编辑ppt得出第二次就座方案是（1，3，5，7，2，4，6，1），那么第三次就座方案就不允许这些顶点之间继续相邻，只能从图中删去这些边。40可编辑ppt123764541可编辑ppt123764542可编辑ppt123764543可编辑ppt123764544可编辑ppt123764545可编辑ppt123764546可编辑ppt123764547可编辑ppt123764548可编辑ppt得到第三次就座方案是（1，4，7，3，6，2，5，1），那么第四次就座方案就不允许这些顶点之间继续相邻，只能从图中删去这些边，只留下7点孤立点，所以该问题只有三个就座方案。49可编辑ppt123764550可编辑ppt引论图的用处某公司的组织机构设置图总公司分公司工厂或办事处51可编辑ppt一、图与网络的基本知识（一）、图与网络的基本概念

EADCB1、一个图是由点和连线组成。（连线可带箭头，也可不带，前者叫弧，后者叫边）52可编辑pptv1v2v3v4v5v6e1e2e3e4e5e6e7e8e9e10例图1一个图是由点集和中元素的无序对的一个集合构成的二元组，记为G=(V，E)，其中V中的元素

叫做顶点，V表示图G

的点集合；E中的元素叫做边，E表示图G的边集合。{}jvV=53可编辑ppt2、不带箭头的连线叫做边。如果一个图是由点和边所构成的，则称其为无向图，记作G=(V，E)，连接点的边记作[vi,vj]，或者[vj,vi]。3、若点与点之间的连线有方向，称为弧。如果一个图是由点和弧所构成的，那么称它为有向图，记作D=(V,A)，其中V表示有向图D的点集合，A表示有向图D的弧集合。一条方向从vi指向vj

的弧，记作(vi,vj)。v4v6v1v2v3v5V={v1,v2,v3,v4,v5,v6}，A={(v1,v3),(v2,v1),(v2,v3),(v2,v5),(v3,v5),(v4,v5),(v5,v4),(v5,v6)}图254可编辑ppt4、一条边的两个端点是相同的,那么称这条边是环。5、如果两个端点之间有两条以上的边，那么称它们为多重边。6、不含环和多重边的图称为简单图；有多重边的图称为多重图。7、每一对顶点间都有边相连的无向简单图称为完全图。有向完全图则是指任意两个顶点之间有且仅有一条有向边的简单图。55可编辑pptv1v2v3v4v5v6e1e2e3e4e5e6e7e8e9e10次为零的点称为弧立点，次为1的点称为悬挂点。悬挂点的关联边称为悬挂边。次为奇数的点称为奇点，次为偶数的点称为偶点。8、以点v为端点的边的个数称为点v的次，记作。图中

d(v1)=4，d(v6)=4（环计两次）56可编辑ppt定理1所有顶点次数之和等于所有边数的2倍。定理2在任一图中，奇点的个数必为偶数。

所有顶点的入次之和等于所有顶点的出次之和。有向图中，以

vi为始点的边数称为点vi的出次，用表示；以

vi为终点的边数称为点vi的入次，用表示；vi点的出次和入次之和就是该点的次。57可编辑ppt9、设G=（V，E），G′=（V′,E′）如果V′

V,E′

E，称G′是G的子图；如果V′=V,E′

E，称G′是G的生成子图或支撑子图。v1v2v3v4v5v6v7e1e2e3e4e5e6e7e8e9e10e11(a)e5e7v1v2v5v6v7e1e6e8(b)子图v1v2v3v4v5v6v7e1e6e7e9e10e11(c)支撑子图58可编辑ppt在实际应用中，给定图中每条边，对应一个数，称之为“权”。通常把这种赋权的图称为网络。10、由两两相邻的点及其相关联的边构成的点边序列称为链。如:v0，e1，v1，e2，v2，e3，v3,…,vn-1,en

，vn，

e3v1v2v3v4v5v6e7e8e1e2e4e5e6e9e1059可编辑ppt11、图中任意两点之间均至少有一条链相连，则称此图为连通图。其链长为n

，其中v0，vn分别称为链的起点和终点。所含的点、边均不相同的链称为初等链。起点和终点是同一个点的链称为圈。60可编辑ppt（二）、图的矩阵表示对于网络（赋权图）G=（V，E），其中边有权，构造矩阵，其中：称矩阵A为网络G的权矩阵。设图G=（V，E）中顶点的个数为n，构造一个矩阵，其中：称矩阵A为网络G的邻接矩阵。61可编辑ppt例权矩阵为：邻接矩阵为：v5v1v2v3v4v6433225643762可编辑ppt

二、树及最小树问题

已知有六个城市，它们之间要架设电话线，要求任意两个城市均可以互相通话，并且电话线的总长度最短。v1v2v3v4v5v61、一个连通的无圈的无向图叫做树。树中次为1的点称为树叶，次大于1的点称为分支点。63可编辑ppt树

的性质：（1）数必连通，但无回路（圈）。（2）n个顶点的树必有n-1条边。（3）树

中任意两个顶点之间，恰有且仅有一条链（初等链）。（4）树

连通，但去掉任一条边，必变为不连通。（5）树无回路（圈），但不相邻的两个点之间加一条边，恰得到一个回路（圈）。v1v2v3v4v5v664可编辑ppt2、若图G=(V,E)的生成子图是一个树,那么称该树

是G的一个生成树（支撑树），或简称为图G的树。图G中属于生成树的边称为树枝，不在生成树中的边称为弦。一个图G有生成树的充要条件是G

是连通图。v1v2v3v4v5v1v2v3v4v565可编辑ppt（一）破圈法：在图中任选一个圈，从这个圈中去掉一条边。在余下的图中重复这个步骤，直到得到一不含圈的图为止。66可编辑ppt67可编辑ppt用破圈法求出下图的一个生成树。v1v2v3v4v5e1e2e3e4e5e6e7e8v1v2v3v4v5e2e4e6e8v1v2v3v4v5e1e2e3e4e5e6e7e868可编辑ppt（二）避圈法：开始选一条边，以后每一步中，总从未被选取的边中选出一条与已选边不构成圈的边，重复这个过程，直到不能进行为止。69可编辑pptv1v2v3v4v5v6v1v3v1v3v2v1v3v2v5v6v1v3v2v5v6v4v1v3v2v570可编辑ppt根据破圈法和避圈法两种方式得到了图的两个不同的生成树，由此可以看到连通图的生成树不是唯一的。71可编辑ppt3、最小生成树问题

一棵生成树所有树枝上权的总和为这个生成树的权。具有最小权的生成树，称为最小生成树。求赋权图G的最小支撑树的方法也有两种，“破圈法”和“避圈法”。

破圈法：在原图中，任选一个圈，从圈中去掉权最大的一条边。在余下的图中重复这个步骤，直到得到一不含圈的图为止。655172344v1v2v3v4v5v672可编辑pptv1v7v4v3v2v5v62015916253281741233673可编辑pptv1v7v4v3v2v5v62015916253281741233674可编辑pptv1v7v4v3v2v5v620159162532817412375可编辑pptv1v7v4v3v2v5v620159162532817412376可编辑pptv1v7v4v3v2v5v6159162532817412377可编辑pptv1v7v4v3v2v5v6159162532817412378可编辑pptv1v7v4v3v2v5v692532817412379可编辑pptv1v7v4v3v2v5v692532817412380可编辑pptv1v7v4v3v2v5v6932817412381可编辑pptv1v7v4v3v2v5v6932817412382可编辑pptv1v7v4v3v2v5v693174123总造价=1+4+9+3+17+23=5783可编辑pptv1v2v3v4v514231352

避圈法：开始选一条权最小的边，以后每一步中，总从未被选取的边中选一条权尽可能小，且与已选边不构成圈的边。84可编辑ppt某六个城市之间的道路网如图

所示，要求沿着已知长度的道路联结六个城市的电话线网，使电话线的总长度最短。v1v2v3v4v5v66515723445v1v2v3v4v5v6123485可编辑ppt最短路的一般提法为：设为连通图，图中各边有权（表示之间没有边），为图中任意两点，求一条路，使它从到的所有路中总权最短。即：最小。(一)、狄克斯彻(Dijkstra)算法适用于wij≥0，给出了从vs到任意一个点vj的最短路。三、最短路问题86可编辑ppt算法步骤：1.给始点vs以P标号，这表示从vs到vs的最短距离为0，其余节点均给T标号，。2.设节点vi为刚得到P标号的点，考虑点vj，其中，且vj为T标号。对vj的T标号进行如下修改：3.比较所有具有T标号的节点，把最小者改为P标号，即：当存在两个以上最小者时，可同时改为P标号。若全部节点均为P标号则停止，否则用代替vi，返回步骤（2）。87可编辑ppt例一：用Dijkstra算法求下图从v1到v6的最短路。

v1v2v3v4v6v5352242421

解：（1）首先给v1以P标号，给其余所有点T标号。（2）（3）（4）88可编辑ppt（5）（6）（7）（8）（9）（10）反向追踪得v1到v6的最短路为：v1v2v3v4v6v535224242189可编辑ppt（二）、逐次逼近法首先设任一点vi到任一点vj都有一条弧。显然，从v1到vj的最短路是从v1出发，沿着这条路到某个点vi再沿弧(vi,vj)到vj。则v1到vi的这条路必然也是v1到vi的所有路中的最短路。设P1j表示从v1到vj的最短路长，P1i表示从v1到vi的最短路长，则有下列方程：

开始时，令即用v1到vj的直接距离做初始解。90可编辑ppt从第二步起，使用递推公式：求，当进行到第t步，若出现则停止计算，即为v1到各点的最短路长。91可编辑ppt例二、

－18v1v2v3v4v5－26－3－5－1－3－521－1211v6v7v83766

0-5

-3

v8-5-55

0

-1

v7-1-1-1

7101

v6-3-31

0

-1

v5-7-7-73

2

0

8v4-2-2-2-2

1

-50-3

v3-5-5-5-1

2

06v20000

3-2-10v1P(4)P(3)P(2)P(1)v8v7v6v5v4v3v2v1求图中v1到各点的最短路92可编辑ppt

－18v1v2v3v4v5－26－3－5－1－3－521－1211v6v7v837（0，0）（v3，-5）（v1，-2）（v3，-7）（v2，-3）（v4，-5）（v3，-1）（v6，6）93可编辑ppt例、求：5年内，哪些年初购置新设备，使5年内的总费用最小。

第i年度

12345购置费1111121213设备役龄0-11-22-33-44-5维修费用

568111894可编辑ppt解：（1）分析：可行的购置方案（更新计划）是很多的，如：1）每年购置一台新的，则对应的费用为：

11+11+12+12+13+5+5+5+5+5=842)第一年购置新的，一直用到第五年年底，则总费用为：11+5+6+8+11+18=59

显然不同的方案对应不同的费用。95可编辑ppt（2）方法：将此问题用一个赋权有向图来描述，然后求这个赋权有向图的最短路。求解步骤：1）画赋权有向图：设Vi

表示第i年初，(Vi,Vj)表示第i年初购买新设备用到第j年初（j-1年底），而Wij

表示相应费用，则5年的一个更新计划相当于从V1

到V6的一条路。2）求解（标号法）96可编辑pptW12=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=41W45=12+5=17W46=12+5+6=23W56=13+5=18W34=12+5=17W35=12+5+6=23W36=12+5+6+8=31v1v2v3v4v5v616221817171630415931234130222397可编辑pptv1v2v3v4v5v616221817171630415931234130222398可编辑ppt四、最大流问题（一）基本概念1、设一个赋权有向图G=（V,E）,在V中指定一个发点vs和一个收点vt

,其它的点叫做中间点。对于D中的每一个弧（vi

,vj）∈E,都有一个非负数cij,叫做弧的容量。我们把这样的图G叫做容量网络，简称网络，记做G=（V，E，C）。网络G上的流，是指定义在弧集合E上的一个函数其中f(vi

,vj)=fij

叫做弧(vi，vj)上的流量。

99可编辑ppt2、称满足下列条件的流为可行流：（1）容量条件：对于每一个弧（vi,vj）∈E 有 0≤

fij

≤

cij

。（2）平衡条件：对于发点vs，有对于收点vt

，有对于中间点，有可行流中fij＝cij

的弧叫做饱和弧，fij＜cij的弧叫做非饱和弧。100可编辑pptvsv1v2v4v3vt374556378S

3、容量网络G=（V，E，C），vs为始点，vt为终点。如果把V分成两个非空集合使，则所有一点属于，而另一点属于的弧的集合，称为由

决定的割集,记作。割集中所有始点在

，终点在的弧的容量之和，称为这个割集的容量，记为。101可编辑ppt关于最大流问题的定理：最大流最小割定理：任一网络中，最大流的流量等于最小割集的容量。102可编辑ppt

4、容量网络G，若为网络中从vs到vt的一条链，给定向为从vs到vt，上的弧凡与方向相同的称为前向弧，凡与方向相反的称为后向弧，其