第五章图与网络分析PPT课件

1、1苏州市规划公交线路网经过抽象后的城市道路网络图经过抽象后的城市道路网络图第1页/共49页2第2页/共49页3第3页/共49页4第4页/共49页5第5页/共49页6大量的工程对象无法研究实物 只能进行抽象 道路网、公交线网等第6页/共49页7BACD图论 Graph Theory 哥尼斯堡七桥问题 (欧拉回路)/环球旅行问题(哈密尔顿回路) /中国邮路问题 欧拉Euler (1707-1783) 在1736年发表第一篇图论方面的论文，奠基了图论中的一些基本定理 很多问题都可以用点和线来表示，一般点表示实体，线表示实体间的关联ABCD第7页/共49页8一、图与网络的基本概念 节点 (Vertex

2、) 物理实体、事物、概念 一般用 vi 表示 边 (Edge) 节点间的连线，表示有关系 一般用 eij 表示 图 (Graph) 节点和边的集合 一般用 G(V,E) 表示 点集 V=v1,v2, vn 边集E=eij v1v5v4v3v2e12e34e13e24e22e13e45图 4 4.1网络网络 (Network)边上具有表示连接强度边上具有表示连接强度的权值，如的权值，如 wij又称又称加权图加权图(Weighted graph)第8页/共49页9无向图与有向图无向图与有向图 边都没有方向的图称为无向图 在无向图中 eij=eji，或 (vi, vj)=(vj, vi) 当边都有方

3、向时，称为有向图，用G(V,A)表示 在有向图中，有向边又称为弧，用 aij表示，i, j 的顺序是不能颠倒的，图中弧的方向用箭头标识 图中既有边又有弧，称为混合图第9页/共49页端点，关联边，相邻，次端点，关联边，相邻，次 图中可以只有点，而没有边；而有边必有点 若节点vi, vj 之间有一条边 eij，则称 vi, vj 是 eij 的端点(end vertex)，而 eij 是节点 vi, vj 的关联边(incident edge) 同一条边的两个端点称为相邻(adjacent)节点，具有共同端点的边称为相邻边 一条边的两个端点相同，称为自环(self-loop)；具有两个共同端点的两

4、条边称为平行边(parallel edges) 既没有自环也没有多重边的图称为简单图(simple graph) 在无向图中，与节点相关联边的数目，称为该节点的“次”(degree)，记为 d ；次数为奇数的点称为奇点(odd),次数为偶数的点称为偶点(even)；图中都是偶点的图称为偶图(even graph)第10页/共49页11 端点，关联边，相邻，次端点，关联边，相邻，次 有向图中，由节点指向外的弧的数目称为正次数，记为 d+，指向该节点的弧的数目称为负次数，记为 d 次数为 0 的点称为孤立点(isolated vertex) ，次数为 1 的点称为悬挂点(pendant verte

5、x)链，圈，路径，回路相邻节点的序列相邻节点的序列 v1 ,v2 , vn 构成一条构成一条链链(link)，又称为，又称为行走行走(walk)；首尾相连的链称为首尾相连的链称为圈圈(loop)，或，或闭行走闭行走在无向图中，节点不重复出现的链称为在无向图中，节点不重复出现的链称为路径路径(path)；在有向图中，节点不；在有向图中，节点不重复出现且链中所有弧的方向一致，则称为有重复出现且链中所有弧的方向一致，则称为有向路径向路径(directed path)首尾相连的路径称为首尾相连的路径称为回路回路(circuit)；第11页/共49页12 连通图，子图，成分 设有两个图 G1(V1, E

6、1), G2(V2, E2), 若V2 V1, E2 E1， 则 G2 是 G1 的子图 若V2V1， E2 E1,称G2为G1的真子图 若V2=V1， E2 E1,称G2为G1的部分图 无向图中，若任意两点间至少存在一条路径，则称为连通图(connected graph)，否则为非连通图( discon-nected graph)；非连通图中的每个连通子图称为成分 (component) 链，圈，路径(简称路)，回路都是原图的子图第12页/共49页13V6V1V4V2V5V3V1V2V3V4V5V6V1（a）（b）V2V3V4V5（c）（d）V2V3V4V5V6b,c,d均为a的子图，b为a

7、的部分图，c,d 为a的真子图第13页/共49页14基础图(母图)真子图部分图 真子 图第14页/共49页15 树图与最小部分树 一般研究无向图 树图：倒置的树，根(root)在上，树叶(leaf)在下 多级辐射制的电信网络、管理的指标体系、家谱、分类学、组织结构、路网布局等都是典型的树图C1C2C3C4根根叶叶第15页/共49页16树的定义及其性质树的定义及其性质 任两点之间有且只有一条路径的图（无圈的连通图）称为树(tree)，记为T 树图G=（V,E）的点数记为p，边数记为q，则q=p-1。 树的性质： 最少边的连通子图，树中必不存在回路 任意两节点之间必有一条且仅有一条链 任何树必存在

8、次数为 1 的点 具有 n 个节点的树 T 的边恰好为 n1 条，反之，任何有n 个节点， n1 条边的连通图必是一棵树第16页/共49页17路(通路)初等路初等回路4528572111vevevevevQ 44322112vevevevQ 1956452113vevevevevQ 简单链初等链初等圈树第17页/共49页18图的部分树（支撑树）图的部分树（支撑树）图图T=（V，E）是图）是图G=（V，E）的支撑子图，）的支撑子图，若图若图T是一个树，则称是一个树，则称T是是G的一个支撑树的一个支撑树 ；部分树一定是部分图，但部分图不一定是部分部分树一定是部分图，但部分图不一定是部分树。树。v1

9、v2v3v5e2e3e5e1e6e7e8破圈法v1v2e1v3e2e4e4v4v4v5e6避圈法v2e2e3e5e4v4v1v3v5e1e6e7e8第18页/共49页19 给图G中的每一条边vi，vj一个相应的数 ij，则称G为赋权图。在赋权图G的所有支撑树中，必有某个支撑树，其所有边的和为最小，称为最小树。求赋权图G的最小支撑树的方法也有两种,“破圈法”和“避圈法”。655172344v1v2v3v4v5v6破圈法：任选一个圈，从圈中去掉权最大的一条边。在余下的图中重复这个步骤，直到得到一不含圈的图为止。最小部分树（支撑树）最小部分树（支撑树）第19页/共49页20v3v21v42v53v6

10、41v2v3v4v5v6避圈法：开始选一条权最小的边，以后每一步中，总从未被选取的边中选一条权尽可能小，且与已选边不构成圈的边。第20页/共49页21归纳 子图矩阵表示含元素的个数点的次边特殊的图点边关系简单图多重图空 图连通图树部分树第21页/共49页空 图不含边G=(V,E) 邻接矩阵 关联矩阵 距离矩阵 边e=u,v 关联边 端点 环多重边 多于1条边简单图多重图 0 1 奇数 偶数 子图真子图部分图导出子图孤立点悬挂点奇点偶点悬挂边顶点数p边数q点边关系各种链的概念第22页/共49页23点边关系真子图部分图子图各种链的概念点）初等链（无重边、无重简单链（无重边

11、）初等回路简单回路路）链、开链、闭链（即回点边交替序列序列各种链的概念通路 树连通图 部分树有向、无向第23页/共49页24 图G中，所有顶点的次的和等于所有边数的2倍。即在任一图中，奇点的个数必为偶数。证明要点：qvdVv2)(VvVvVvvdvdvd)()()(21（V1、V2分别是图G中次为奇数和偶数的顶点集合）第24页/共49页25二、 图论在网络分析中的应用中心、重心最小费用最大流结果分析？步骤？求解原理？使用条件？理解各种算法海斯算法算法）列表法（氏标号法最短路问题最大流问题（标号法）最短树问题应用网络赋权图权有向图弧网络有关概念FordD 第25页/共49页26（3）指与边或弧有

12、关的数量指标。根据实 际背景可赋予不同含义，如距离、时间、 费用、容量等。（1）点与点之间有方向的连线。 指从 ；),(jivva jivv （5）指定了的的 。包括无向网络、 有向网络、混合网络。),(EVG （4）图 连同边上的权总体。),(EVG ),(AVD （2）由点集v和弧集A组成的图第26页/共49页27三、网络的计算机表示 大量的工程计算无法依靠手工完成 交通工程中的网络计算必须依靠计算机 网络在计算机中的表示与存储网络在计算机中的表示与存储第27页/共49页28900900多节点，多节点，30003000多条边多条边第28页/共49页29 构造V E阶矩阵 A=aij否则相联

13、时与点边 0 1ijijVeaV1V3V2V4e1e2e3e4e6e51 1 1 0 0 01 0 0 1 1 00 1 0 0 1 10 0 1 1 0 1A1、关联矩阵法第29页/共49页30V4V2V1V5V3563263540 1 1 1 01 0 1 0 11 1 0 1 11 0 1 0 10 1 1 1 0D2、邻接矩阵法 D=dij 否则有边相联与节点节点 0ji 1ijd第30页/共49页31V4V2V1V5V356326354权重矩阵有边相连无边相连jiwjiWijij, 00 3 5 6 3 0 6 25 6 0 4 36 4 0 5 2 3 5 0W第31页/共49页3

14、2V4V2V1V5V3 3、边目录法e1e6e7e4e5e2e3e1=(1,2)e2=(2,5)e3=(5,4)e4=(1,4)第32页/共49页33 4、邻接目录法（推荐） 计算机存储利用率高123456节点号 V(I)（相邻节点数） N(I,J) （相邻节点）号 1 2 2,5 2 3 1,3,4 3 2 2,6 4 3 2,5,6 5 3 1,4,6 6 3 3,4,5 第33页/共49页34最短路问题（SP）详见单独文件第34页/共49页35最大流问题最大流问题第35页/共49页36AC(40)(10)(10)(20)(30)(30)(20)(20)(20)(30)(60)(40)(1

15、0)下图为某一城市道路网络，路段均为双向，图中下图为某一城市道路网络，路段均为双向，图中数据（数据（a a ）为道路通行能力（容量）。）为道路通行能力（容量）。 求：从求：从A A、C C两点到两点到B B点的最大网络运输能力（最大流量）。点的最大网络运输能力（最大流量）。B第36页/共49页371 网络与流 网路流一般在有向图上讨论 定义网路上支路的容量为其最大通过能力，记为 cij ，支路上的实际流量记为 fij 图中规定一个发点s，一个收点t 节点没有容量限制，流在节点不会存储 容量限制条件：0 fij cij 平衡条件： tifvtsisifvffijijvBvjivAvij)(,0)

16、()()( 满足上述条件的网路流称为满足上述条件的网路流称为可行流可行流，总存在，总存在最大可行流最大可行流 当支路上当支路上 fij = cij ，称为，称为饱和弧饱和弧 最大流问题也是一个线性规划问题最大流问题也是一个线性规划问题viA(vi)B(vi)第37页/共49页382 截集与截集容量截集与截集容量定义：把网路分割为两个成分的弧的最小集合，其中一 个成分包含 s 点，另一个包含 t 点 。 一般包含 s 点的成分中的节点集合用V表示，包含 t 点的成分中的节点集合用V表示 截集容量是指截集中正向弧的容量之和( ,)iji Vj VC V Vc 福特福特-富克森定理富克森定理：网路的

17、最大流等于最小截集容量：网路的最大流等于最小截集容量st5342(4,0)(3,0)(2,0)(1,0)(1,0)(5,0)(3,0)(2,0)(5,0)第38页/共49页393 确定网路最大流的标号法确定网路最大流的标号法 从任一个初始可行流出发，如 0 流 基本算法：找一条从 s 到 t 点的增广链(augmenting path) 最大流充要条件： 当且仅当不存在增广链时，可行流为最大流。 增广链中与 s 到 t 方向一致的弧称为前向弧，反之后向弧 增广过程：前向弧增广过程：前向弧 f ij=fij +q q , , 后向弧后向弧 f ij=fij q q 增广后仍是可行流增广后仍是可行

18、流 st5432(3,0)(5,3)(1,1)(5,1)(1,1)q qs2=4q q5t=2q q45=3q q43=1q q32=1增广量 增广量 q q = min q qij= min(4,1,1,3,2)= 1st5432(3,1)(5,4)(1,0)(5,2)(1,0) 后后向向弧弧前前向向弧弧ijijijijffcq q前向弧非饱和弧；后向弧非零流弧。第39页/共49页40 最大流最小截的标号法步骤最大流最小截的标号法步骤第一步：标号过程，找一条增广链1、给源点 s 标号s+,q(s)=，表示从 s 点有无限流出潜力2、找出与已标号节点 i 相邻的所有未标号节点 j，若(1) (

19、i, j)是前向弧且饱和，则节点 j 不标号；(2) (i, j)是前向弧且未饱和，则节点 j 标号为i+,q(j)，表示从节点 i 正向流出，可增广 q(j)=minq(i), cijfij ；(3) (j, i)是后向弧，若 fji=0，则节点 j 不标号；(4) (j, i)是后向弧，若 fji0，则节点 j 标号为i,q(j)，表示从节点 j 流向 i，可增广 q(j)=minq(i), fji ；3、重复步骤 2，可能出现两种情况：(1) 节点 t 尚未标号，但无法继续标记，说明网路中已不存在增广链，当前流 v(f) 就是最大流；所有获标号的节点在 V 中，未获标号节点在 V 中，V

20、 与 V 间的弧即为最小截集；算法结束(2)节点 t 获得标号，找到一条增广链，由节点 t 标号回溯可找出该增广链；到第二步第40页/共49页41 最大流最小截的标号法步骤最大流最小截的标号法步骤第二步：增广过程1、对增广链中的前向弧，令 f=f+q(t)，q(t) 为节点 t 的标记值2、对增广链中的后向弧，令 f=fq(t)3、非增广链上的所有支路流量保持不变第三步：抹除图上所有标号，回到第一步 以上算法是按广探法描述的，但在实际图上作业时，按深探法进行更快捷 一次只找一条增广链，增广一次换一张图 最后一次用广探法，以便找出最小截集第41页/共49页42最大流最小截集的标号法举例最大流最小

21、截集的标号法举例st134256(14,14)(9,9)(15,9)(16,15)(3,1)(12,10)(6,6)(4,3)(5,5)(22,22)(13,12)(7,5)(6,3)(19,10)st134256(14,14)(9,9)(15,10)(16,15)(3,1)(12,10)(6,5)(4,4)(5,5)(22,22)(13,12)(7,5)(6,3)(19,11)(s+, )(s+,6)(2 ,6)(3+,1)(4+,1)(s+, )(s+,5)(2+,2)(5 ,2)(4+,2)第42页/共49页43最大流最小截集的标号法举例最大流最小截集的标号法举例st134256(14,14)(9,9)(15,10)(16,15)(3,1)(12,10)(6,5)(4,4)(5,5)(22,22)(13,12)(7,5)(6,3)(19,11)st134256(14,14)(9,9)(15,12)(16,15)(3,1)(12,