第五章图与网络分析ppt课件.ppt

第四章第四章 图与网络分析图与网络分析图是最直观的模型图是最直观的模型图论是交通系统分析中的重要工具图论在交通系统规划、管理中作用大图论是对实际交通网络进行抽象分析的重要手段SEUSEUSEUSEU苏州市规划公交线路网经过抽象后的城市道路网络图经过抽象后的城市道路网络图SEUSEUSEUSEUSEUSEUSEUSEUSEUSEU大量的工程对象无法研究实物大量的工程对象无法研究实物 只能进行抽象只能进行抽象 道路网、公交线网等道路网、公交线网等SEUSEUBACD图论图论 Graph Theory•哥尼斯堡七桥问题哥尼斯堡七桥问题 (欧拉回路欧拉回路)/环球旅行问题环球旅行问题(哈密尔顿回哈密尔顿回路路)• /中国邮路问题中国邮路问题•欧拉欧拉Euler (1707-1783) 在在1736年发表第一篇图论方面的论文，年发表第一篇图论方面的论文，奠基了图论中的一些基本定理奠基了图论中的一些基本定理•很多问题都可以用点和线来表示，一般点表示实体，线表很多问题都可以用点和线来表示，一般点表示实体，线表示实体间的关联示实体间的关联SEUSEU一、图与网络的基本概念一、图与网络的基本概念 节点节点 (Vertex)物理实体、事物、概念物理实体、事物、概念一般用一般用 vi 表示表示边边 (Edge)节点间的连线，表示有关系节点间的连线，表示有关系一般用一般用 eij 表示表示图图 (Graph)节点和边的集合节点和边的集合一般用一般用 G(V,E) 表示表示点集点集 V={v1,v2,…, vn}边集边集E={eij }网络网络 (Network) (Network)边上具有表示连接强度的边上具有表示连接强度的权值，如权值，如 wij wij又称加权图又称加权图(Weighted (Weighted graph)graph)SEUSEU无向图与有向图无向图与有向图•边都没有方向的图称为无向图边都没有方向的图称为无向图•在无向图中在无向图中 eij=eji，或，或 (vi, vj)=(vj, vi)•当边都有方向时，称为有向图，用当边都有方向时，称为有向图，用G(V,A)表示表示•在有向图中，有向边又称为弧，用在有向图中，有向边又称为弧，用 aij表示，表示，i, j 的顺序的顺序是不能颠倒的，图中弧的方向用箭头标识是不能颠倒的，图中弧的方向用箭头标识•图中既有边又有弧，称为混合图图中既有边又有弧，称为混合图端点，关联边，相邻，次端点，关联边，相邻，次•图中可以只有点，而没有边；而有边必有点图中可以只有点，而没有边；而有边必有点•若节点若节点vi, vj 之间有一条边之间有一条边 eij，则称，则称 vi, vj 是是 eij 的端点的端点(end vertex)，而，而 eij 是节点是节点 vi, vj 的关联边的关联边(incident edge)•同一条边的两个端点称为相邻同一条边的两个端点称为相邻(adjacent)节点，具有共节点，具有共同端点的边称为相邻边同端点的边称为相邻边•一条边的两个端点相同，称为自环一条边的两个端点相同，称为自环(self-loop)；具有两；具有两个共同端点的两条边称为平行边个共同端点的两条边称为平行边(parallel edges)•既没有自环也没有多重边的图称为简单图既没有自环也没有多重边的图称为简单图(simple graph)•在无向图中，与节点相关联边的数目，称为该节点的在无向图中，与节点相关联边的数目，称为该节点的“次次”(degree)，记为，记为 d ；次数为奇数的点称为奇点；次数为奇数的点称为奇点(odd),次数为偶数的点称为偶点次数为偶数的点称为偶点(even)；图中都是偶点；图中都是偶点的图称为偶图的图称为偶图(even graph)SEUSEU 端点，关联边，相邻，次端点，关联边，相邻，次•有向图中，由节点指向外的弧的数目称为正次数，记为有向图中，由节点指向外的弧的数目称为正次数，记为 d+，指向该节点的弧的数目称为负次数，记为，指向该节点的弧的数目称为负次数，记为 d–•次数为次数为 0 的点称为孤立点的点称为孤立点(isolated vertex) ，次数为，次数为 1 的点称为悬挂点的点称为悬挂点(pendant vertex)链，圈，途径，回路链，圈，途径，回路相邻节点的序列相邻节点的序列 {v1  ,v2  ,…, vn } 构成一条链构成一条链(link)，，又称为行走又称为行走(walk)；首尾相连的链称为圈；首尾相连的链称为圈(loop)，或闭，或闭行走行走在无向图中，节点不重复出现的链称为路径在无向图中，节点不重复出现的链称为路径(path)；在有；在有向图中，节点不重复出现且链中所有弧的方向一致，则向图中，节点不重复出现且链中所有弧的方向一致，则称为有向路径称为有向路径(directed path)首尾相连的路径称为回路首尾相连的路径称为回路(circuit)；；SEUSEU 连通图，子图，成分连通图，子图，成分设有两个图设有两个图 G1(V1, E1), G2(V2, E2), 若若V2  V1, E2  E1，， 那么那么 G2 是是 G1 的子图的子图若若V2 V1，， E2   E1,称称G2为为G1的真子图的真子图若若V2=V1，， E2   E1,称称G2为为G1的部分图的部分图无向图中，若任意两点间至少存在一条路径，则称为连无向图中，若任意两点间至少存在一条路径，则称为连通图通图(connected graph)，否则为非连通图，否则为非连通图( discon-nected graph)；非连通图中的每个连通子图称为成分；非连通图中的每个连通子图称为成分 (component)链，圈，途径链，圈，途径(简称路简称路)，回路都是原图的子图，回路都是原图的子图SEUSEUV6V1V4V2V5V3V1V2V3V4V5V6V1（a）（b）V2V3V4V5（c）（d）V2V3V4V5V6b,c,d均为a的子图，b为a的部分图，c,d 为a的真子图SEUSEU子子 图图基础图基础图(母图母图)真子图真子图部分图部分图 真子真子 图图SEUSEU 树图与最小部分树树图与最小部分树•一般研究无向图一般研究无向图•树图：倒置的树，根树图：倒置的树，根(root)在上，树叶在上，树叶(leaf)在下在下•多级辐射制的电信网络、管理的指标体系、家谱、分多级辐射制的电信网络、管理的指标体系、家谱、分类学、组织结构、路网布局等都是典型的树图类学、组织结构、路网布局等都是典型的树图SEUSEU树的定义及其性质树的定义及其性质•任两点之间有且只有一条路径的图〔无圈的连通图〕称任两点之间有且只有一条路径的图〔无圈的连通图〕称为树为树(tree)，记为，记为T•树图树图G=（（V,E〕的点数记为〕的点数记为p，边数记为，边数记为q，则，则q=p-1。

•树的性质：树的性质：•最少边的连通子图，树中必不存在回路最少边的连通子图，树中必不存在回路•任意两节点之间必有一条且仅有一条链任意两节点之间必有一条且仅有一条链•任何树必存在次数为任何树必存在次数为 1 的点的点•具有具有 n 个节点的树个节点的树 T 的边恰好为的边恰好为 n 1 条，反之，任何有条，反之，任何有n 个节点，个节点， n 1 条边的连通图必是一棵树条边的连通图必是一棵树SEUSEU路路(通路通路)初等路初等路初等回路初等回路链、路、树链、路、树简单链简单链初等链初等链初等圈初等圈树树SEUSEU图的部分树〔支撑树）图的部分树〔支撑树）图图T=（（V，，E‘）是图）是图G=（（V，，E〕的支撑子图，若图〕的支撑子图，若图T是一个是一个树，则称树，则称T是是G的一个支撑树的一个支撑树 ；；部分树一定是部分图，但部分图部分树一定是部分图，但部分图不一定是部分树不一定是部分树v1v2v3v5e2e3e5e1e6e7e8破圈法破圈法v1v2e1v3e2e4e4v4v4v5e6避圈法避圈法v2e2e3e5e4v4v1v3v5e1e6e7e8SEUSEU 给图给图G中的每一条边中的每一条边[vi，，vj]一个相应的数一个相应的数 ij，则称，则称G为赋权图。

在赋权图为赋权图在赋权图G的所有支撑树中，必有某个支撑树，的所有支撑树中，必有某个支撑树，其所有边的和为最小，称为最小树求赋权图其所有边的和为最小，称为最小树求赋权图G的最小支撑的最小支撑树的方法也有两种树的方法也有两种,“破圈法〞和破圈法〞和“避圈法避圈法”655172344v1v2v3v4v5v6破圈法：破圈法：任选一个圈，从圈中去掉权任选一个圈，从圈中去掉权最大的一条边在余下的图最大的一条边在余下的图中重复这个步骤，直到得到中重复这个步骤，直到得到一不含圈的图为止一不含圈的图为止最小部分树〔支撑树）最小部分树〔支撑树）SEUSEUv3v21v42v53v64v15655172344v1v2v3v4v5v6避圈法：避圈法：开始选一条权最小的边，以后每一步中，总从开始选一条权最小的边，以后每一步中，总从未被选取的边中选一条权尽可能小，且与已选未被选取的边中选一条权尽可能小，且与已选边不构成圈的边边不构成圈的边SEUSEU归纳归纳 G=G=（（（（V V，，，，E E））））子图子图矩阵表示矩阵表示含元素的个数含元素的个数点的次点的次边边特殊的图特殊的图点边关系点边关系简简单单图图多多重重图图空空 图图连通图连通图树树部分树部分树空空 图图不含边不含边G=(V,E) 矩阵表示矩阵表示A 邻接矩邻接矩阵阵B 关联矩关联矩阵阵D 距离矩距离矩阵阵 ……边边e=[u,v] 关联边关联边 端点端点 重重重重合合合合环环自自自自回回回回路路路路多重边多重边 平行平行边边多于多于1条边条边简单图简单图不含不含不含不含多重图多重图含含含含点的次点的次点的次点的次 0 1 奇数 偶数 子图子图真真子子图图部部分分图图导导出出子子图图孤孤立立点点悬悬挂挂点点奇奇点点偶偶点点悬挂边悬挂边顶点数顶点数p边数边数q点边关系点边关系各种链的概念各种链的概念SEUSEU点边关系点边关系真真子子图图部部分分图图子子图图各种链的概念各种链的概念通路通路 树树连通图连通图 部分树部分树有有向向、、无无向向SEUSEU两个主要定理两个主要定理定理定理定理定理1 1 图图图图GG中，所有顶点的次的和等于所有中，所有顶点的次的和等于所有中，所有顶点的次的和等于所有中，所有顶点的次的和等于所有边数的边数的边数的边数的2 2倍。

即倍即定理定理定理定理2 2 在任一图中，奇点的个数必为偶数在任一图中，奇点的个数必为偶数在任一图中，奇点的个数必为偶数在任一图中，奇点的个数必为偶数证明要点：证明要点：证明要点：证明要点：（（V1、、V2分别是图分别是图G中次为奇数和偶数的顶点集中次为奇数和偶数的顶点集合）合）SEUSEU二、二、 图论在网络分析中的应用图论在网络分析中的应用SEUSEU（（3〕权〕权——指与边或弧有关的数量指标根据实指与边或弧有关的数量指标根据实 际背景可赋予不同含义，如距离、时间、际背景可赋予不同含义，如距离、时间、 费用、容量等费用、容量等1〕弧〕弧——点与点之间有方向的连线点与点之间有方向的连线 指从指从 ；；（（5〕网络〕网络——指定了起点、终点和中间点的连通指定了起点、终点和中间点的连通 的的 赋权有向图赋权有向图 包括无向网络、包括无向网络、 有向网络、混合网络有向网络、混合网络4〕赋权图〕赋权图—图图 连同边上的权总体。

连同边上的权总体2〕有向图〕有向图——由点集由点集v和弧集和弧集A组成的图组成的图SEUSEU三、网络的计算机表示三、网络的计算机表示¡大量的工程计算无法依靠手工完成大量的工程计算无法依靠手工完成¡交通工程中的网络计算必须依靠计算机交通工程中的网络计算必须依靠计算机¡ ¡ 网络在计算机中的表示与存储网络在计算机中的表示与存储SEUSEU900900多节点，多节点，30003000多条边多条边SEUSEU¡构造构造VE阶矩阵阶矩阵 A={aij}V1V3V2V4e1e2e3e4e6e51、关联矩阵法、关联矩阵法SEUSEUV4V2V1V5V356326354¡2、邻接矩阵法、邻接矩阵法¡ D={dij} SEUSEUV4V2V1V5V356326354权重矩阵SEUSEUV4V2V1V5V3•3、边目录法、边目录法e1e6e7e4e5e2e3e1=(1,2)e2=(2,5)e3=(5,4)e4=(1,4)…SEUSEU¡4、邻接目录法〔引荐）¡计算机存储利用率高123456SEUSEU最短路问题〔最短路问题〔SP））详见单独文件详见单独文件SEUSEU最大流问题最大流问题SEUSEUAC(40)(10)(10)(20)(30)(30)(20)(20)(20)(30)(60)(40)(10)下图为某一城市道路网络，路段均为双向，图中下图为某一城市道路网络，路段均为双向，图中数据〔数据〔a a ）为道路通行能力〔容量）。

为道路通行能力〔容量） 求：从求：从A A、、C C两点到两点到B B点的最大网络运输能力〔最大流量）点的最大网络运输能力〔最大流量）BSEUSEU1 网络与流网络与流•网路流一般在有向图上讨论网路流一般在有向图上讨论•定义网路上支路的容量为其最大通过能力，记为定义网路上支路的容量为其最大通过能力，记为 cij ，，支路上的实际流量记为支路上的实际流量记为 fij •图中规定一个发点图中规定一个发点s，一个收点，一个收点t•节点没有容量限制，流在节点不会存储节点没有容量限制，流在节点不会存储•容量限制条件：容量限制条件：0  fij   cij •平衡条件：平衡条件：• 满足上述条件的网路流称为可行流，总存在最大可行流满足上述条件的网路流称为可行流，总存在最大可行流• 当支路上当支路上 fij = cij ，称为饱和弧，称为饱和弧• 最大流问题也是一个线性规划问题最大流问题也是一个线性规划问题viA(vi)B(vi)SEUSEU2 截集与截集容量截集与截集容量定义：把网路分割为两个成分的弧的最小集合，其中一定义：把网路分割为两个成分的弧的最小集合，其中一 个成分包含个成分包含 s 点，另一个包含点，另一个包含 t 点点 。

一般包含一般包含 s 点的成分中的节点集合用点的成分中的节点集合用V表示，包含表示，包含 t 点的点的成分中的节点集合用成分中的节点集合用V表示表示截集容量是指截集中正向弧的容量之和截集容量是指截集中正向弧的容量之和• 福特福特-富克森定理：网路的最大流等于最小截集容量富克森定理：网路的最大流等于最小截集容量SEUSEU3 确定网路最大流的标号法确定网路最大流的标号法•从任一个初始可行流出发，如从任一个初始可行流出发，如 0 流流•基本算法：找一条从基本算法：找一条从 s 到到 t 点的增广链点的增广链(augmenting path)•最大流充要条件：最大流充要条件： 当且仅当不存在增广链时，可行流为当且仅当不存在增广链时，可行流为最大流 •增广链中与增广链中与 s 到到 t 方向一致的弧称为前向弧，反之后向弧方向一致的弧称为前向弧，反之后向弧 • 增广过程：前向弧增广过程：前向弧 f ij=fij +q , 后向弧后向弧 f ij=fij  q • 增广后仍是可行流增广后仍是可行流 前向弧非饱和弧；前向弧非饱和弧；后向弧非零流弧后向弧非零流弧SEUSEU 最大流最小截的标号法步骤最大流最小截的标号法步骤第一步：标号过程，找一条增广链第一步：标号过程，找一条增广链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), cij fij] ；；(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 标号回溯可标号回溯可找出该增广链；到第二步找出该增广链；到第二步SEUSEU 最大流最小截的标号法步骤最大流最小截的标号法步骤第二步：增广过程第二步：增广过程1、对增广链中的前向弧，令、对增广链中的前向弧，令 f =f+q(t)，，q(t) 为节点为节点 t 的标记的标记值值2、对增广链中的后向弧，令、对增广链中的后向弧，令 f =f q(t)3、非增广链上的所有支路流量保持不变、非增广链上的所有支路流量保持不变第三步：抹除图上所有标号，回到第一步第三步：抹除图上所有标号，回到第一步以上算法是按广探法描述的，但在实际图上作业时，按深探以上算法是按广探法描述的，但在实际图上作业时，按深探法进行更快捷法进行更快捷一次只找一条增广链，增广一次换一张图一次只找一条增广链，增广一次换一张图最后一次用广探法，以便找出最小截集最后一次用广探法，以便找出最小截集SEUSEU最大流最小截集的标号法举例最大流最小截集的标号法举例(s+,)(s+,6)(2,6)(3+,1)(4+,1)(s+,)(s+,5)(2+,2)(5,2)(4+,2)SEUSEU最大流最小截集的标号法举例最大流最小截集的标号法举例(s+,)(s+,3)(2,3)最小截集最小截集SEUSEU多收发点的网络最大流•网络中存在多个发点和收点时：虚拟发点和收点，网络中存在多个发点和收点时：虚拟发点和收点，虚拟发点和收点到各发点的弧的容量、各收点的虚拟发点和收点到各发点的弧的容量、各收点的弧的容量为无穷大〔不破坏发点、收点产生、吸弧的容量为无穷大〔不破坏发点、收点产生、吸引流量能力无限的条件）引流量能力无限的条件）Vs3Vt3V2V3V4V6V513945655545104Vs1Vs2Vt2Vt1Vs3Vt3V2V3V4V6V5Vs1Vs2Vt2Vt1VsVt∞∞∞∞∞∞多收发点的最大流问题转化为单收发点的最大流问题多收发点的最大流问题转化为单收发点的最大流问题最大流问题作业最大流问题作业VsV2V3V6V5(3,2)(5,1)(1,1)(4,2)(2,2)(1,1)(5,2)(2,1)Vt(3,0)弧旁注释〔弧旁注释〔a,ba,b〕对应〔弧容量，弧流量）〕对应〔弧容量，弧流量）SEUSEU 6.4.5 最小费用最大流最小费用最大流•双权网路：每条弧不但有容量，还有单位流量的通过费用双权网路：每条弧不但有容量，还有单位流量的通过费用•两种解法：一种基于最小费用路径算法；一种基于可行弧集两种解法：一种基于最小费用路径算法；一种基于可行弧集的最大流算法的最大流算法•基于最小费用路径算法：总是在当前找到的最小费用的路径基于最小费用路径算法：总是在当前找到的最小费用的路径上增广流；缺点是每次增广后要改变弧的费用，且出现负权上增广流；缺点是每次增广后要改变弧的费用，且出现负权值费用的弧值费用的弧•基于可行弧集的最大流算法：从基于可行弧集的最大流算法：从 0 费用弧集开始应用最大流费用弧集开始应用最大流算法，然后根据计算信息提高费用的限界算法，然后根据计算信息提高费用的限界P，使可行弧集增，使可行弧集增大，再应用最大流算法，直至所有弧都进入可行弧集。

这种大，再应用最大流算法，直至所有弧都进入可行弧集这种算法是一种主算法是一种主-对偶规划的解法使用这种方法的还有运输对偶规划的解法使用这种方法的还有运输问题、匹配问题问题、匹配问题。