通信网络理论基础 03-关于图-2007-BIG.pptxVIP

通信网络理论基础 王晟 博士 教授 博导 Part 03: 关于图(Intro to Graph) 2014年春季 通信网络理论基础 2 / 40 关于图 1 2 从Königsberg桥问题说起 图的问题及应用 本课程所涉及的“图”，是一个关于实体/对象/数据的组织、关联关系的数学/抽象概念。既不是“图形”，也不是“图像”。 3 / 40 Euler @ Königsberg 2014年春季 通信网络理论基础 4 / 40 基本术语 (一) 2014年春季 通信网络理论基础 5 / 40 Ideas of Euler (1736) 经过一条边，就意味着“离开”某个点1次，且“进入”某个点1次。 奇数度意味着这个点进入和离开的次数不等。 如果它是圈的起点终点不可能是它。 如果它不是圈起点回不到终点了。 2014年春季 通信网络理论基础 Euler’s Theorem 6 / 40 这个点一定是w ！ 如果图中还有其它边没有经过，一定可以从刚才这个圈中的某个点出发，继续下去。 2014年春季 通信网络理论基础 Variations(1/3) 7 / 40 2014年春季 通信网络理论基础 Variations(2/3) 8 / 40 2014年春季 通信网络理论基础 Variations(3/3) 9 / 40 2014年春季 通信网络理论基础 The Power of Math 10 / 40 2014年春季 通信网络理论基础 11 / 40 关于图 2 图的问题及应用 Euler圈的判定问题是图论中比较简单的例子。那么，关于图的问题还有哪些？它们在通信网络中又有着什么样的应用呢？ 2014年春季 通信网络理论基础 12 / 40 图的问题及应用 2014年春季 通信网络理论基础 13 / 40 基本术语(二)：有向图/Digraph 2014年春季 通信网络理论基础 14 / 40 基本术语(三)：加权图 2014年春季 通信网络理论基础 15 / 40 最短路问题(1/3) 2014年春季 通信网络理论基础 16 / 40 最短路问题(2/3) 可能的约束： 路径长度； 跳数； 带宽； 必经点/禁止点； … 2014年春季 通信网络理论基础 最短路问题(3/3) 17 / 40 2014年春季 通信网络理论基础 18 / 40 图的问题及应用 2014年春季 通信网络理论基础 19 / 40 基本术语(四)：树 2014年春季 通信网络理论基础 20 / 40 关于树的问题 2014年春季 通信网络理论基础 21 / 40 图的问题及应用 2014年春季 通信网络理论基础 22 / 40 基本术语(五)：流 满足容量约束么？ 满足流量守恒么？ 流的大小？ 流的代价？ 5 53 源=S; 目的=T; x/y/z=流量/容量/代价 2014年春季 通信网络理论基础 23 / 40 最大流问题 (S, T)之间的最大流？ 将每条边上的容量都设置为1，求(S, T)之间的最大流(要求必须是整数)？ 2014年春季 通信网络理论基础 24 / 40 最小费用流问题 (S, T)之间的流量需求为3。求最小费用流。 每条边上的容量都设置为1，(S, T)之间需求也为1，求出的最小费用流是什么？ 2014年春季 通信网络理论基础 25 / 40 图的问题及应用 2014年春季 通信网络理论基础 26 / 40 其它问题 关于图的问题还有很多，这里仅遴选几个在通信网络中有一定应用的，作一简单介绍。 匹配(Matching) 图的生成 Hamilton圈与旅行商问题(TSP) 着色(Coloring) 控制集(Dominating Set) 其它问题 2014年春季 通信网络理论基础 27 / 40 基本术语(六)：偶图与匹配 2014年春季 通信网络理论基础 28 / 40 匹配问题(Matching) 2014年春季 通信网络理论基础 29 / 40 其它问题 关于图的问题还有很多，这里仅遴选几个在通信网络中有一定应用的，作一简单介绍。 匹配(Matching) 图的生成 Hamilton圈与旅行商问题(TSP) 着色(Coloring) 控制集(Dominating Set) 其它问题 2014年春季 通信网络理论基础 30 / 35 四色猜想/定理 Four-Color Conjecture /Theorem 1890~1976年间，许多人尝试了各种方法来证明这个猜想都没有成功。但是其间出现的思想和方法极大地丰富、发展、促进了图论的相关研究。直到… 2014年春季 通信网络理论基础 31 / 40 顶点着色问题 2014年春季 通信网络理论基础 32 / 40 其它问题 关