图与网络分析课件

第四章图与网络分析图是最直观的模型图论是交通系统分析中的重要工具图论在交通系统规划、管理中作用大图论是对实际交通网络进行抽象分析的重要手段12苏州市规划公交线路网经过抽象后的城市道路网络图3567BACD图论GraphTheory哥尼斯堡七桥问题(欧拉回路)/环球旅行问题(哈密尔顿回路)/中国邮路问题欧拉Euler(1707-1783)在1736年发表第一篇图论方面的论文，奠基了图论中的一些基本定理很多问题都可以用点和线来表示，一般点表示实体，线表示实体间的关联9一、图与网络的基本概念

节点(Vertex)物理实体、事物、概念一般用vi

表示边(Edge)节点间的连线，表示有关系一般用eij

表示图(Graph)节点和边的集合一般用G(V,E)表示点集V={v1,v2,…,vn}边集E={eij}网络(Network)边上具有表示连接强度的权值，如wij又称加权图(Weightedgraph)10无向图与有向图边都没有方向的图称为无向图在无向图中eij=eji，或(vi,vj)=(vj,vi)当边都有方向时，称为有向图，用G(V,A)表示在有向图中，有向边又称为弧，用aij表示，i,j的顺序是不能颠倒的，图中弧的方向用箭头标识图中既有边又有弧，称为混合图11

端点，关联边，相邻，次有向图中，由节点指向外的弧的数目称为正次数，记为d+，指向该节点的弧的数目称为负次数，记为d–次数为0的点称为孤立点(isolatedvertex)

，次数为1的点称为悬挂点(pendantvertex)链，圈，路径，回路相邻节点的序列

{v1,v2,…,vn}构成一条链(link)，又称为行走(walk)；首尾相连的链称为圈(loop)，或闭行走在无向图中，节点不重复出现的链称为路径(path)；在有向图中，节点不重复出现且链中所有弧的方向一致，则称为有向路径(directedpath)首尾相连的路径称为回路(circuit)；13

连通图，子图，成分设有两个图G1(V1,E1),G2(V2,E2),若V2V1,E2

E1，则G2是G1的子图若V2V1，E2E1,称G2为G1的真子图若V2=V1，E2E1,称G2为G1的部分图无向图中，若任意两点间至少存在一条路径，则称为连通图(connectedgraph)，否则为非连通图(discon-nectedgraph)；非连通图中的每个连通子图称为成分(component)链，圈，路径(简称路)，回路都是原图的子图14V6V1V4V2V5V3V1V2V3V4V5V6V1（a）（b）V2V3V4V5（c）（d）V2V3V4V5V6b,c,d均为a的子图，b为a的部分图，c,d为a的真子图15树图与最小部分树一般研究无向图树图：倒置的树，根(root)在上，树叶(leaf)在下多级辐射制的电信网络、管理的指标体系、家谱、分类学、组织结构、路网布局等都是典型的树图17树的定义及其性质任两点之间有且只有一条路径的图（无圈的连通图）称为树(tree)，记为T树图G=（V,E）的点数记为p，边数记为q，则q=p-1。树的性质：最少边的连通子图，树中必不存在回路任意两节点之间必有一条且仅有一条链任何树必存在次数为1的点具有n个节点的树T的边恰好为n1条，反之，任何有n个节点，n1条边的连通图必是一棵树18路(通路)初等路初等回路链、路、树简单链初等链初等圈树19给图G中的每一条边[vi，vj]一个相应的数ij，则称G为赋权图。在赋权图G的所有支撑树中，必有某个支撑树，其所有边的和为最小，称为最小树。求赋权图G的最小支撑树的方法也有两种,“破圈法”和“避圈法”。655172344v1v2v3v4v5v6破圈法：任选一个圈，从圈中去掉权最大的一条边。在余下的图中重复这个步骤，直到得到一不含圈的图为止。最小部分树（支撑树）21v3v21v42v53v641v2v3v4v5v6避圈法：开始选一条权最小的边，以后每一步中，总从未被选取的边中选一条权尽可能小，且与已选边不构成圈的边。22归纳

G=（V，E）子图矩阵表示含元素的个数点的次边特殊的图点边关系简单图多重图空图连通图树部分树23点边关系真子图部分图子图各种链的概念通路树连通图

部分树有向、无向25两个主要定理定理1

图G中，所有顶点的次的和等于所有边数的2倍。即定理2在任一图中，奇点的个数必为偶数。证明要点：（V1、V2分别是图G中次为奇数和偶数的顶点集合）26三、网络的计算机表示大量的工程计算无法依靠手工完成交通工程中的网络计算必须依靠计算机

网络在计算机中的表示与存储29900多节点，3000多条边30构造VE阶矩阵A={aij}V1V3V2V4e1e2e3e4e6e51、关联矩阵法31V4V2V1V5V3563263542、邻接矩阵法D={dij}

32V4V2V1V5V356326354权重矩阵33V4V2V1V5V33、边目录法e1e6e7e4e5e2e3e1=(1,2)e2=(2,5)e3=(5,4)e4=(1,4)…344、邻接目录法（推荐）计算机存储利用率高12345635最短路问题（SP）

详见单独文件36最大流问题37AC(40)(10)(10)(20)(30)(30)(20)(20)(20)(30)(60)(40)(10)下图为某一城市道路网络，路段均为双向，图中数据（a）为道路通行能力（容量）。求：从A、C两点到B点的最大网络运输能力（最大流量）。B381网络与流网路流一般在有向图上讨论定义网路上支路的容量为其最大通过能力，记为cij，支路上的实际流量记为fij图中规定一个发点s，一个收点t节点没有容量限制，流在节点不会存储容量限制条件：0fijcij平衡条件：

满足上述条件的网路流称为可行流，总存在最大可行流当支路上fij

=cij

，称为饱和弧最大流问题也是一个线性规划问题viA(vi)B(vi)392截集与截集容量定义：把网路分割为两个成分的弧的最小集合，其中一个成分包含s点，另一个包含t点。一般包含s点的成分中的节点集合用V表示，包含t点的成分中的节点集合用V表示截集容量是指截集中正向弧的容量之和

福特-富克森定理：网路的最大流等于最小截集容量403确定网路最大流的标号法从任一个初始可行流出发，如0流基本算法：找一条从s到t点的增广链(augmentingpath)最大流充要条件：

当且仅当不存在增广链时，可行流为最大流。

增广链中与s到t方向一致的弧称为前向弧，反之后向弧

增广过程：前向弧fij=fij

+q,后向弧fij=fij

q

增广后仍是可行流

前向弧非饱和弧；后向弧非零流弧。41最大流最小截的标号法步骤第一步：标号过程，找一条增广链1、给源点s标号[s+,q(s)=]，表示从s点有无限流出潜力2、找出与已标号节点i相邻的所有未标号节点j，若(1)(i,j)是前向弧且饱和，则节点j

不标号；(2)(i,j)是前向弧且未饱和，则节点j

标号为[i+,q(j)]，表示从节点i正向流出，可增广q(j)=min[q(i),cijfij]；(3)(j,i)是后向弧，若fji=0，则节点j不标号；(4)(j,i)是后向弧，若fji>0，则节点j标号为[i,q(j)]，表示从节点j

流向i，可增广q(j)=min[q(i),fji]；3、重复步骤2，可能出现两种情况：(1)节点t尚未标号，但无法继续标记，说明网路中已不存在增广链，当前流v(f)就是最大流；所有获标号的节点在V中，未获标号节点在V中，V与V间的弧即为最小截集；算法结束(2)节点t获得标号，找到一条增广链，由节点t标号回溯可找出该增广链；到第二步42最大流最小截的标号法步骤第二步：增广过程1、对增广链中的前向弧，令f=f+q(t)，q(t)为节点t的标记值2、对增广链中的后向弧，令f=fq(t)3、非增广链上的所有支路流量保持不变第三步：抹除图上所有标号，回到第一步以上算法是按广探法描述的，但在实际图上作业时，按深探法进行更快捷一次只找一条增广链，增广一次换一张图最后一次用广探法，以便找出最小截集43最大流最小截集的标号法举例(s+,)(s+,6)(2,6)(3+,1)(4+,1)(s+,)(s+,5)(2+,2)(5,2)(4+,2)44最大流最小截集的标号法举例(s+,)(s+,3)(2,3)最小截集45多收发点的网络最大流网络中存在多个发点和收点时：虚拟发点和收点，虚拟发点和收点到各发点的弧的容量、各收点的弧的容量为无穷大（不破坏发点、收点产生、吸引流量能力无限的条件）46Vs3Vt3V2V3V4V6V513945655545104Vs1Vs2Vt2Vt147Vs3Vt3V2V3V4V6V5Vs1Vs2Vt2Vt1VsVt∞∞∞∞∞∞多收发点的最大流问题转化为单收发点的最大流问题48最大流问题作业VsV2V3V6V5(3,2)(5,1)(1,1)(4,2)(2,2)(1,1)(5,2)(2,1)Vt(3,0)弧旁注释（a,b）对应（弧容