网络拓扑分析.ppt

通信网基础 第五章 网络拓扑结构分析 为什么学习网络拓扑分析？ 通信网中的很多问题都与拓扑结构密切相关 通信网规划和设计 通信网的流量分配 通信网的站址规划 网络中的路由规划 路由算法设计 路由生存性研究 网络 无线传感器网络的覆盖 网络中的组播树 本章学习目的 掌握网络拓扑分析的理论基础：图论 利用图论解决通信网中的实际问题 大纲 5.1 图论基础 5.1.1 图的定义和基本概念 5.1.2 树 5.1.3 割集 5.1.4 图的矩阵表示 5.2 最短路径问题 5.2.1 最小支撑树 5.2.2 端间最短距离和路由 5.3 网络流量问题 5.3.1 基本概念 5.3.2 最大流问题 5.3.3 最小费用流问题 大纲 5.1 图论基础 5.1.1 图的定义和基本概念 5.1.2 树 5.1.3 割集 5.1.4 图的矩阵表示 5.2 最短路径问题 5.2.1 最小支撑树 5.2.2 端间最短距离和路由 5.3 网络流量问题 5.3.1 基本概念 5.3.2 最大流问题 5.3.3 最小费用流问题 哥尼斯堡Konigsberg 七桥问题 图论的起源：哥尼斯堡七桥问题 国际互联网 (K. C. Claffy) 电信网络 (Stephen G. Eick) 美国航空网 世界性的新闻组网络 (Naveen Jamal) 人际关系网络 无尺度网络 20世纪20年代，由Karinthy提出。 1950年， Pool 和 Kochen提出这样一个问题： 两个毫无关系的人，要让他们互相认识，至少要 经过多少人？ 美国哈佛大学社会心理学家S. Milgram在1967年做过一项有趣的实验，据说他从内布拉斯加州的奥马哈随机选了300人，然后请他们每个人尝试寄一封信到波士顿的一位证券业务员。寄信的规则很简单，就是任何收信者只能把信寄给自己熟识的人。 重要结论 “6度分离” —对每个人来说，平均大约只需要通过６个人就能将信寄到目的地。 研究无尺度网络，对于防备黑客攻击、防治流行病、和开发新药等，都具有重要的意义。 在1999年，Barab′asi et al.发现在因特网上，任意两个网页间的链接最多为19次。(Nature 401, 1999) 小世界实验 大纲 5.1 图论基础 5.1.1 图的定义和基本概念 5.1.2 树 5.1.3 割集 5.1.4 图的矩阵表示 5.2 最短路径问题 5.2.1 最小支撑树 5.2.2 端间最短距离和路由 5.3 网络流量问题 5.3.1 基本概念 5.3.2 最大流问题 5.3.3 最小费用流问题 图的基本定义和概念(1) 图的定义 例 G = (V, E) V = { v1, v2, v3, v4 } E = { e1, e2, e3, e4 } 或E = { (v1, v2), (v1, v3), (v2, v3), (v3, v4) } 或E = { e12, e13, e23, e34 } 图的基本定义和概念(2) 无向图与有向图 一个图如果有边(vi, vj)就一定有边(vj, vi)，称其为无向图，否则称其为有向图。 例 图的基本定义和概念(3) 空图：V = Φ时 孤立点图：E = Φ时 自环：边(vi,vi)被称为自环。 重边：如果两条边有相同的两个邻端，这两条边就被称为重边 简单图与伪图： 一个不含自环和重边的图称为简单图 一个不是简单图的图称为伪图 图的基本定义和概念(4) 端的度数 无向图中 与端Vi关联边的数目称为该端的度数，记为：d(vi) 有向图中 离开端vi的边数称为该端的出度，记为：d+(vi) 进入端vi的边数称为该端的入度，记为：d-(vi) 性质5.1 图的基本定义和概念(5) 图的基本定义和概念(6) 子图相关概念 给定图G=(V, E)，若 ， , 称图G1=(V1, E1)是G中由V1生成的子图，记为：G[V1] 若 ，称G2=(V1, E2)为G的子图 若子图的端点集合为V，这个图被称为图G的支撑子图 若 ， ，则称图G1=(V1, E1)是G中由E1生成的子图，记为：G[E1] 图的基本定义和概念(6) 子图相关概念 给定图G=(V, E)，若 ，