通信网理论基础：03-关于图

1、通信网理论基础Part 03: 关于图(Intro to Graph)2013年春季2 / 35关于图12从Knigsberg桥问题说起 图的问题及应用 本课程所涉及的“图”，是一个关于实体/对象/数据的组织、关联关系的数学/抽象概念。既不是“图形”，也不是“图像”。3 / 35Euler Knigsberg Knigsberg 7桥问题能否找到一条游览路线，使得游客经过所有7个桥，要求每个桥只经过1次，并且刚好回到起点。 Why is it so important? Euler在1736年的工作不只是解决了这个问题，而且其解决方法中所蕴涵的思想开创了一个新方向：只关注连接关系，而不考虑形状

2、/测量等几何性质。 因此，这不仅被看作是图论的起源，也被看作是拓扑学的第一个结果。2013年春季4 / 35基本术语 (一)如果图中任意两个顶点之间都邻接，则称该图为全连通图(full mesh)。全连通图顶点u和v之间有边相连，则称u和v邻接（adjacent）。邻接顶点 也称为节点/结点(node)。边 也称为弧(arc)，链路(link)。 边与两个顶点有关(head和tail)。自环(loop) 如果一条边的头和尾都是同一个顶点，则称为自环。度(degree) 与顶点相连的边的数目(或与之邻接的顶点数目)。 也称价(valence)。可达 两个顶点之间如果存在路径，则称这两个顶点可达(

3、reachable)。连通图如果图中任意两个顶点之间都可达，则称该图为连通(connected)。圈(cycle)如果路径的起点和终点是同一个顶点，称为圈，或回路(circuit)，环路。路径(path) 路径由首尾相连的一系列边构成。 起点和终点。图(Graph)由顶点(Vertex)集合和边(Edge)集合构成。点间关系关于路径关于顶点关于边与顶点u直接相连的边与u关联；反之，u也与这些边关联(Incident)。关联关于图点边关系2013年春季5 / 35Ideas of Euler (1736)转化为图 陆地顶点； 桥边。 问题：是否存在一个圈，它经过所有的边，但每条边只经过一次？ 称

4、为Euler圈。必要条件顶点度数必为偶数 经过一个点，就意味着“离开”某个点1次，和“进入”某个点1次。 奇数度意味着这个点进入和离开的次数不等。 如果它是圈的起点终点不可能是它。 如果它不是圈起点回不到终点了。充分条件偶度数连通图，必然存在Euler圈 从任意顶点w离开，每经过一个点，随意选择离开的边(然后删除)。直到到达某个顶点，已没有可供离去的边。这个点一定是w ！ 如果图中还有其它边没有经过，一定可以从刚才这个圈中的某个点出发，继续下去。Eulers Theorem连通图中存在Euler圈的充要条件是顶点度数全为偶数2013年春季2009年春季图算法及其在通信网络中的应用6 / 35V

5、ariationsCan you modify THE graph, making it include a Euler Cycle?How about this: there are odd number of vertices whose degree is odd?Todays Knigsberg (Kaliningrad) has only 5 bridgesEuler PathIMPOSSIBLE Theorem: 顶点度数之和必为偶数；且为边数的2倍。 Corollary: 奇数度顶点的数目必为偶数。The crux of mathematics is not its signat

6、ure strange symbols but its ability to engage the mind with problems involving the search for patterns.7 / 35关于图21从Knigsberg桥问题说起 图的问题及应用 Euler圈的判定问题是图论中比较简单的例子。那么，关于图的问题还有哪些？它们在通信网络中又有着什么样的应用呢？2013年春季8 / 35图的问题及应用4其它问题1关于路的问题2关于树的问题3关于流的问题2013年春季9 / 35基本术语(二)：有向图/Digraph有向图 Directed Edge 可用有序顶点对表示，

7、前者表示边的尾/起始，后者表示边的头/终止。 作图时，用箭头表示有向边的头/终止。有向边出度 Outdegree 以顶点v为起始的有向边数目。称为v的出度。入度 Indegree 以顶点v为终止的有向边数目。称为v的入度。01230123有向圈有向无圈图 DAG, Directed Acyclic Graph 注意不是树。2013年春季10 / 35基本术语(三)：加权图加权图 加权图中，每条边都赋予了一个或多个权重。 权重可以代表各种物理意义。 也称为网络(Network)。 Simple Path 不含圈的路径。简单路径22101678356ABCDE2210162356ABCDE路径权重

8、 加性权重：路径的权重等于路径所经过的所有边的权重之和。 也可能存在其它类型的权重，比如乘性权重，最大最小权重等。2013年春季11 / 35最短路问题(一) Single Source给定加权图G(V, E)，给定源点/起始点s和目的点/终止点d，求从s出发到d的权重最小的路径。给定加权图G(V, E)，给定源点/起始点s，求从s出发到V中其它所有顶点的权重最小的路径。 All-Pair给定加权图G(V, E)，求V中所有节点之间的最小权重路径。22101678356ABCDE应用分组网络的路由协议。2013年春季12 / 35最短路问题(二)Disjoint Path Pair给定加权图G

9、，以及源点s和目的点d，求从s到d的两条分离路径，要求两条路径权重之和是所有分离路径对中最小的。 k-shortest path给定加权图G，以及源点s和目的点d，求从s到d的前k条最短路。22/8010/7016/802/6035/906/100ABCDE Constrained Shortest Path给定加权图G，以及源点s和目的点d，求从s到d的所有满足约束的路径中，权重最小的路径。可能的约束： 路径长度； 跳数； 带宽； 必经点/禁止点； 应用电信网中的路径保护技术应用求解约束路由应用QoS路由2013年春季13 / 35图的问题及应用4其它问题1关于路的问题2关于树的问题3关于流

10、的问题2013年春季14 / 35基本术语(四)：树子图(subgraph)树(Tree)不包含任何圈的连通图判决条件1) 边的数目为顶点数目减1，且不含圈。2) 边的数目为顶点数目减1，且连通。3) 任意两顶点间存在唯一路径。4) 删除任意一条边，图就不连通了。生成树如果图G的一个子图包含了G的全部顶点，且为树，则称之为G的生成树(Spanning Tree)2013年春季15 / 35关于树的问题最小生成树问题给定加权图G，求最小权重生成树。应用交换机的拓扑设计施泰纳(Steiner)树问题给定加权图G，以及一个V的子集X，求一棵包含了X中所有顶点的，最小权重的树。ABCDEFG11111

11、111111应用多播路由协议110ABCDEFG1111101101011102013年春季2009年春季图算法及其在通信网络中的应用16 / 35图的问题及应用4其它问题1关于路的问题2关于树的问题3关于流的问题17 / 35基本术语(五)：流2/ 2 /5OSQRPT3/ 3 /22/ 2 /52/ 3 /23/ 3 /43/ 3 /30/ 2 /11/ 4 /2关于流(Flow)的描述性定义 一般，flow定义在流网络(flow network)上的一对顶点(s, t)之间，称为(s, t)流。其中s为流的起始点，t为流的终止点。 流网络的每条边上都有容量(Capacity)；有的流问题

12、中还要定义单位单价(Cost)。 在每条边上，流都必须满足容量约束。 在流经过的每个节点(除了s和t)上，流都需要满足守恒原则。s只有流出的流，t只有流入的流。 s流出的总和(或t流入的总和)定义为流的大小。 每条边上流量与代价相乘，然后对所有边求和，就得到流的代价。S为源，T为目的。边上的x/y/z，x代表流量值，y代表容量，z代表代价。满足容量约束么？满足流量守恒么？流的大小？流的代价？5532013年春季18 / 35最大流问题Maximum Flow Problem给定流网络G，给定节点对(s, t)，求从s到t 的一个流，使得流量值最大(或者只要求得到最大流量值)。?/ 2OSQRP

13、T?/ 3?/ 2?/ 3?/ 3?/ 3?/ 2?/ 4?/ 1OSQRPT?/ 1?/ 1?/ 1?/ 1?/ 1? /1?/ 1典型应用通信网络可靠性设计(S, T)之间的最大流？将每条边上的容量都设置为1，求(S, T)之间的最大流(要求必须是整数)？2013年春季19 / 35最小费用流问题Minimum Cost Flow Problem给定流网络G，给定节点对(s, t)，以及s到t 的流量需求x，求一个流量安排方案(即一个流)，该流的大小为x，且是所有大小为x的流中，代价最小的。典型应用业务量工程(S, T)之间的流量需求为3。求最小费用流。每条边上的容量都设置为1，(S, T

14、)之间需求也为1，求出的最小费用流是什么？?/ 2 /5OSQRPT?/ 3 /2?/ 2 /5?/ 3 /2?/ 3 /4?/ 3 /3?/ 2 /1?/ 4 /2?/ 1 /5OSQRPT?/ 1 /2?/ 1 /5?/ 1 /2?/ 1 /4?/ 1 /3?/ 1 /1?/ 1 /22013年春季20 / 35图的问题及应用4其它问题1关于路的问题2关于树的问题3关于流的问题2013年春季21 / 35其它问题关于图的问题还有很多，这里仅遴选几个在通信网络中有一定应用的，作一简单介绍。匹配(Matching)图的生成Hamilton圈与旅行商问题(TSP)着色(Coloring)控制集(

15、Dominating Set)其它问题2013年春季22 / 35基本术语(六)：偶图与匹配偶图如果图的顶点可以划分为两个集合，使得任一集合内部的任意两个顶点都不邻接，则称该图为偶图(Bipartite)给定图G(V, E)，匹配是E的一个子集M，其中任意两条边之间都没有共同的顶点与之关联。匹配2013年春季23 / 35匹配问题(Matching) 极大匹配(Maximal Matching)给定图G(V, E)，求匹配M，使得再向M中添加任何边都导致M不再是匹配了。完美匹配(Perfect Matching)给定图G(V, E)，求匹配M，使得V中所有顶点都至少与M中的一条边关联。也称为完

16、全匹配。最大匹配(Maximum Matching)给定图G(V, E)，求匹配M，使得M中包含的边的数目最大。最大权重匹配(Maximum Weighted Matching)给定加权图G(V, E)，求匹配M，使得M中边的权重之和最大。典型应用交换调度完美匹配最大匹配极大匹配2013年春季24 / 35其它问题关于图的问题还有很多，这里仅遴选几个在通信网络中有一定应用的，作一简单介绍。匹配(Matching)图的生成Hamilton圈与旅行商问题(TSP)着色(Coloring)控制集(Dominating Set)其它问题2013年春季25 / 35四色猜想/定理Four-Color C

17、onjecture /Theorem1890Percy Heawood指出Kempe的证明是错误的。并用类似思想证明了5色定理。1976Kenneth Appel和Wolfgang Haken用计算机辅助方法证明了这个定理。这是该方法最早的成功案例。有人认为该 定理得证标志着图论的诞生。1852Francis Guthrie在给英国地图着色时提出四色猜想Fredrick GuthrieDe MorganHamilton1879Arthur Cayley在伦敦数学学会上提出了这个猜想并归之于De Morgan。Alfred Kempe公布了他的证明。他本人因此被选为皇家学会会员，后又成为伦敦数学

18、学会主席。18901976年间，许多人尝试了各种方法来证明这个猜想都没有成功。但是其间出现的思想和方法极大地丰富、发展、促进了图论的相关研究。直到2013年春季26 / 35顶点着色问题顶点着色优化问题(Optimization)给定图G，问最少需要多少色彩来着色。判定问题(Decision)给定图G，给定整数k，问G能否用少于k种色彩来着色。1) 判定问题的难度为NP-C，优化问题的难度为NP-H。2) 即使是4度平面图的判定问题也是NP-C的。3) 特例1：偶图。4) 特例2：全连通图。典型应用1) 无线网络中的频谱分配2) 光网络中的波长分配3) IP网络中的分组调度4) 操作系统中的寄

19、存器分配既然很难，应用中怎么计算？贪婪/顺序着色：按一定原则对顶点排序，逐一着色。Welsh-Powell算法：按度数排序。性能取决于排序策略：可能最佳，也可能极差。2013年春季27 / 35其它问题关于图的问题还有很多，这里仅遴选几个在通信网络中有一定应用的，作一简单介绍。匹配(Matching)图的生成Hamilton圈与旅行商问题(TSP)着色(Coloring)控制集(Dominating Set)其它问题2013年春季28 / 35控制集给定图G(V, E)，控制集是V的一个子集D，V D 中的每个顶点都与D中至少一个顶点邻接。控制集1, 2, 3, 4, 5, 6 ?2, 3,

20、4, 5 ?2, 3, 4 ?2, 3 ?4, 5 ?判定问题(Decision)给定图G，给定整数k，问能否找到规模小于等于k的控制集。优化问题(Optimization)给定图G，求规模最小的控制集。典型应用Ad Hoc/Wireless sensor网络中的中继节点的选择控制集问题是NP-C的。应用中可用近似方法求解。2013年春季29 / 35其它问题关于图的问题还有很多，这里仅遴选几个在通信网络中有一定应用的，作一简单介绍。匹配(Matching)图的生成Hamilton圈与旅行商问题(TSP)着色(Coloring)控制集(Dominating Set)其它问题2013年春季30

21、/ 35Hamilton圈和TSP问题Hamilton圈经过了图中所有顶点且每个顶点只经过一次的圈，称为Hamilton圈。Hamilton路径旅行商问题(Traveling Salesman Problem)给定加权图G(V, E)，求权重最小的Hamilton路径/圈。典型应用通信网络中的可靠性设计：p-cycleTSP不仅要判定，还要求最优的Hamilton路径，因此是NP-H问题。实际中仍然只能用近似解法。Hamilton路径/圈的判定问题是NP-C问题。2013年春季31 / 35其它问题关于图的问题还有很多，这里仅遴选几个在通信网络中有一定应用的，作一简单介绍。匹配(Matchin

22、g)图的生成Hamilton圈与旅行商问题(TSP)着色(Coloring)控制集(Dominating Set)其它问题2013年春季32 / 35图的自动生成随机模型 Erds and Rnyi (1960) 均匀随机选择一对节点并连线。经典的随机图产生模型。 Waxman (1988) 用于Internet拓扑。节点间连线的概率与欧氏距离成反比。应该真实世界图模型，为什么要自动产生？1. 难以测量2. 测试用例随机模型层次模型复杂网络模型层次模型用于描述Internet的层次结构 Doar (1996) Tier Zegura (1997) Transit-Stub1995年开始的Internet拓扑测量工作逐步展开，新的结果表明，Internet中表现出许多复杂的特性2013年春