图论在网络拓扑发现算法中的应用
小 型 微 型 计 算 机 系 统 Journal of Chinese Computer Systems
2008 年 月 第 期 Vol.28 No. 2008
?
图论在网络拓扑发现算法中的应用
路连兵 1+，胡吉明 2，姜 岩 1
1，2
，2
(河海大学 计算机及信息工程学院,江苏 南京
210098)
E-mail ：famioo@https://www.wendangku.net/doc/2817334085.html,
摘
要：网络拓扑发现技术已经广泛地应用在各种项目软件中。然而，随着网络结构复杂度升级，这给拓扑发现带来了
挑战。所以我们越来越需要一种高效，准确的网络拓扑算法自动发现网络拓扑结构。目前的拓扑算法主要集中在：(1)路 由层的发现。这个层面的发现算法在技术上比较简单，只需要寻找路由与路由之间，或路由端口与子网之间的连接关系， 利用路由器的自身特性，很容易实现。(2)链路层的发现。直到目前为止，已有的厂商工具很难准确发现网络拓扑，已发 表的理论文献知识也只是理论上阐述，实际应用难度比较大。本论文，提出一种基于图论的骨架树数据存储结构算法，可 以高效推断网络的拓扑关系。 关键词：骨架树;子网;地址转发表;图论；信任节点
Topology Discovery in Networks Based on Graph Theory*
LU Lian-Bing1+, HU Ji-Ming2，Jiang Yan1,2
1,2
(School of Computer Science and Information, Hohai University, Nanjing Jiangsu 210098, China)
Abstract: Topology discovery systems are starting to be introduced in the form of easily and widely deployed software. However, Today's IP network is complex and dynamic. Keeping track of topology information efficiently is a difficult task. So, we need effective algorithms for automatically discovering physical network topology. Earlier work has typically focused on: (1) Layer-3 (network layer) topology, which can only router-to-router interconnections and router interface-to-subnet relationships. This work is relatively easy and has lots of systems can do it. (2)Layer-2(link layer), till now, no tools can discovery the network topology exactly because of bad algorithm. In this paper, Skeleton-tree based on Graph theory is proposed to infer the connections between network nodes. Key words: Skeleton-tree; subnets; Address Forwarding Table; Graph Theory；Trust Node
作者简介: 路连兵(1979－),男,江苏泗洪人,硕士。 主要研究网络自拓扑,软件项目管理,Perl 研究;胡吉明(1967－),男,硕导,副教授,主要研究 领域为计算机应用技术,网络安全,数据挖掘，Z 语言; 姜岩(1979-),男,硕士研究生,主要研究方向,网络应用,中间件
2
小 型 微 型 计 算 机 系 统
2004 年
1 网络拓扑的现状 Ethernet Local Area Networks (LANs) 是指在一区域内 将不同的网络设备通过传输光缆， 电缆连接起来， 实现网络 资源共享的网络。但是由于网络设备种类众多， 而且同类产 品产自不同厂家也会在原理上有所区别， 所以管理员要能够 高效管理维护日益膨胀、 复杂的网络已经十分困难。 本课题 ——网络拓扑发现（Topology Discovery ，简称 TD）就 是从降低网络维护人员工作的难度、 准确高效反应网络结构 的角度而研究的。TD 主要功能是尽可能真实反应不同设备 之间的物理连接关系。 有效的 TD 算法不但能够快速绘制出 网络实体互联关系， 而且能够准确的体现不可管理设备如集 线器 HUB（但目前有的 HUB 是可管理的）等。这样网络管 理员就可以直接在网络拓扑图上得到网络故障， 流量瓶颈等 重要信息，对所发生的故障一目了然。 如果网络拓扑上显示 一条链路总处于满负荷传输状态， 那么扩大该条链路的容量 对提高网络性能将有很大帮助。
地连接， 甚至于插上线缆就可以建立一个局域网。 而这种连 接的简便性使得局域网对网络管理软件都是透明的。 但这并 不意味着第二层发现功能将无所作为。 关键基础设施的厂商 们已经开发出了自有的发现协议，可将数据存储于 SNMP 企业版，例如 Cisco 公司的 CDP 协议（Cisco Discovery Protocol ） Extreme Networks 的 EDP 协 议 （ Extreme 、 Discovery Protocol ） Enterasys Networks 的 CDP 协议 、
（Cabletron Discovery Protocol）以及 Nortel Networks 的
NDP 协议（Nortel Discovery Protocol）等。这里的一个明 显问题是， 这些协议都不能工作在混合厂商设备集成的网络 环境下。2 层网络设备交换机、网桥、集线器等与终端的主 机或上层的路由设备都是直接互联， 而且设备不记录相邻的 设备信息，仅有二层交换机上维护着一张表,记录着接收的 数据包应该从哪个端口转发出去,这张表就是 AFTs。
（ii）2 层网络中设备缺乏统一的标准。2 层网络中存在亚
元设备， 所谓亚元设备是指有些设备通过 SNMP Bridge MIB 很难实现获取 AFTs 信息，甚至不支持 SNMP 服务；有些 设备比如集线器（HUB）, 不具有类似于交换机的"智能记
1.1 网络拓扑中几个难点
至于难于拓扑第二层网络这种状况，其原因是多方面 的，下面介绍在网络拓扑发现算法设计的过程中， 仅仅借助 于 2 层的网络设备的 MIB 信息所存在的困难。从国内外研 究得知，设计出好的网络拓扑算法， 主要是要解决一下几方 面的问题。
忆"能力和"学习"能力，它也不具备交换机所具有的 MAC(Media Access Control)地址表。 所以要准备发现网络中 这些设备，是网络拓扑算法设计的一大挑战。
（iii）多子网网络结构。目前的 LANs 都支持划分多子网，
在同一子网内的设备可以直接通讯， 不需要经过路由器。而 不同子网内的设备之间通讯需要经过路由器数据转发 （即使
（i）2 层网络设备的透明性。二层拓扑困难其原因是多方
面的，主要是建立这些网络十分容易。 因为交换机可以透明
1 期
图论在网络拓扑发现算法中的应用
3
物理上是连接直接连接） 同一子网内的设备构成了连接树。 。 见图 1-1 a） （ 。它表示的典型的网络结构被分成三个子网结 构:
N 1 ? { n1 , n 6 , n 7 , n8 , n13 , n14 , n15 , n 20 , n 25 } N 2 ? { n 3 , n 4 , n 5 , n 9 , n10 , n16 , n17 , n 21 , n 23 }
n21 n3 n4 s5 n5 s11 h1 s1 s6 s8 s7 n10 s2 h2 n23
N 3 ? { n 2 , n11 , n12 , n16 , n18 , n19 , n 22 , n 24 }
s9 s10 n9 n17 n16
图 1-1(c) 连接树
其中 n i 表示主机节点， s i 表示交换机节点， h i 表示集线器 等共享设备，相应的网络无向树模型见图 1-1（b） 、图 1-1 （c） 、图 1-1（d） 。
n21 n3 n4 s5 n5 n13 n11 n24
n19 s11 h1 s3 n12
n20 n1 s1 s6 n18 n2 s7 s9 s4 s8 n10 h3 n14 s13 n16 s14 n15 n22 s2 h2 n7 n6 n8 n23
n19 s11 h1 n24 n11 n12 s3 n2 s1 s6 n18 s7 s9 h3 n16 s14 n22
s2 h2 n7 n6 n8
II 网络模型 目前日益复杂的 LAN 主要由交换机（也称网桥） ，路由 图 1-1(d) 连接树
s2 s4
s10 n25 n9 n17 n16
图 1-1(a) 网络模型
n20 s11 s5 h1 n1 s1 s6 n13 s7 s9 s10 n14 h3 s13 n15
图 1-1(b) 连接树
器， 主机等组成， 由于本课题研究的 LAN 是一个连接实体， 在 2 层网络中，任意一对网络节点之间总会存在仅包含 2 层网络设备（交换机，HUB 等）的路径，且仅有一条。路 径中的交换的活动端口(也称转发端口)可以通过生成树协 议判断。 子网生成树用无向树 G (V , E ) 表示。 其中 V 是网络节点
n25
4
小
型
微
型
计 算
机
Dv
N
系
统
2008 年
集， E 是任意两网络节点的活动端口的物理连接关系。把 实际物理网络拓扑结构抽象表达成无向树 G (V , E ) ，是本 课题－网络拓扑发现的目标。 在无向树中， 交换机是无向树 内部节点，路由器和主机用无向树的叶节点表示。 2 层网 在 络拓扑中，发现路由器比较困难， 所以用一系列的主机表示 一个路由器。由于子网生成树是无向树 G ，任意两节点之 间的数据传输都遵循生成树协议， 而路径选择由交换机活动 端口上的 AFT 信息决定。换个角度描述，AFT 是端口接收 的一系列 Media Access Control (MAC)地址信息， 形成 MAC 地址表并维护它。下面为了算法的描述方便，给出 TD 算法 和描述中所用到字符的原始定义：
10.
:节点 v 的所有活动端口，即如果 F N v , k 蛊
N
，则
k ? Dv
。
11. 12.
r
:连接树 T N 的根节点。 :一系列节点 v ? N ，且在 T N 中以 v 为根节点。
Bv
下列是本课题中用到的术语定义:
1.
True 节 点 : 表 示 有 唯 一 MAC 地 址 并 且 可 以 通 过 SNMP 获得 AFT 信息的网络设备。 所有主机都是 True 节点。为了简化本研究课题，课题中的 True 节点用交 换机（Switch）代表。
1.
Ps , t
:表示在 G (V , E ) 图中任意两节点 s , t ? V 之间的路
径。
2.
False 节点: 表示与 True 节点相反的网络设备。也就 是哑元设备或无法通过 SNMP 获得 AFT 信息的设备。 本研究课题简化 False 节点,用 Hub 代表。
2. 3. 4.
Dv
:表示任意节点 v?V 的所有活动端口集合。 :表示节点 v ? V 的第 k th 个端口。
th
( v ,k )
3.
Subnet: 表示最大 IP 网络设备集合 N ì N 任意两设备 之间通信都不需要经过路由器。
Fv , k
:表示节点 v ? V 的第 k
个端口的 AFT 地址转发
4.
F
N v,k
完备性: 端口 ( v , k ) 的 AFT 信息中包含子网 N 中
表。
所有节点。 :表示节点 v ? V 的活动端口与节点 u ? V 具有连
v , v(u)
5.
v (u )
5.
Fv , k
完备性: 端口 ( v , k ) 的 AFT 信息中包含子网集 N
v
接关系且 u ? F
中所有节点。 III 拓扑算法概述 本课题中的网络自拓扑算法(TD)在实际网络中应用主要 实现： 1. 在给定的网络中，能够正确拓扑发现 True 节点活动 端口之间的物理连接关系。 2. 通过已知网络设备的有限 AFT 信息，推导网络中的 False 节点如 Hub，以及与之相邻的网络节点之间的 连接关系。 下面我们阐述网络自拓扑算法 TD 的详细设计。TD 算法 设计主要分为三步骤： 1. 2. 充分获得网络设备的 AFTs 信息。 利用一定的推导算法或称为技术，为每个子网 N 建 立数学模型：无向连接树 T N 。但是在算法设计过程 中考虑到 AFTs 信息可能不完备， 所以推导算法引入 了一种辅助结构树 Assistant Data Tree(简称 ADT),以
th
6. 7.
N :表示子网 subnet 的集合。
T N (V N ,E N )
:表示任意子网 N ì N 所确定的连接树。
N
{P } s ,t
N
:任意一对网络节点 s , t?
|N | N N
,的路径集合。所以
T
N
(V
,E ) =
N N N N V ? { Ps , t } ， , E 是 { Ps , t } 中所有网络
i
i= 1
节点与边的集合。
8.
Nv
:任意一交换机 v ? V ，如果子网 N i 包含 v ，则
n
N v ＝ ? N i 且 N v í N 。所以给定节点 v 的 AFTs 信
i= 1
息是指 v 在 N
N v,k
v
中所有可达的节点的集合。
9.
F
:
由 Fv , k 可以这样定义： F N v , k 也是节点 v 在第 k
简化算法实现过程。 3. 约定合并规则，合并所有无向树 T N 的 ADT 结构。 递归合并无向树 T N 的 ADT 结构，如果结果得到的 是一独立的辅助结构树，那么就认为这颗辅助结构 树就是网络的实际拓扑结构。这一结论在后面将给 出证明。
端口处的 AFT 信息集合(这个 AFT 信息集合忽略不属于子 网 N 中 节 点 的 信 息 ， 即 满 足 AFT 中 的 节 点 v ? N 且
N
? N v ).
1 期 A. 辅助结构树 AT 的数据结构
图论在网络拓扑发现算法中的应用
5
基于无向生成树 T N (V N , E N ) ，选定任意节点 r ? N 为根 节点， T N 则为以 r 为根节点的生成树。
子网 N
?
N 的连接树为 T N (V N , E N ) ，交换机在 T N 中可
Tv
定义 4。 B v 是 T N 任意节点 v ? V
N
N
，以 v 为根节点的子树
以分为两类节点：交叉节点和横越节点。在给出定义之前， 首先我先给出图论中度的概念：无向图 G 的顶点 v 的度是 指 G 中与 v 关联的边的数目。用 d ( v ) 表示顶点 v 的度。 ? ? 度大于等于 3 的节点称为交叉节点。 度等于 2 的节点称为横越节点。
í T
N
的所有节点, B v í N 。而 | B v | 是 B v 包含节点的数
量。 特别要声明的是 V 节点,在图 2－(1)中,
N 1 = { n1 , n 6 , n 7 , n8 , n13 , n14 , n15 , n 20 , n 25 }
V
N1
N
与 N 存在区别：在 T N 中 V
N
包含子
在图 1-1（b）中交换机 s 2 ， s 5 ， s 6 ， s 7 ， s1 1 都是横越节 点， s1 , s 9 是交叉节点。 定义 1。 T N 的辅助结构树用 H (Y , A ) 描述： H (Y , A ) 每个 顶点 y ? Y 是 T N 中节点的集合 C y ? V
N
网内所有的节点包括交换机以及根节点。而 N 则只包含叶
，弧 A 是 T N 中边的
= { s1 , s 2 , s 5 , s 6 , s 7 , s 9 , s11 , s13 , n1 , n 6 , n 7 , n8 , n13 , n14 , n15 , n 20 , n 25 }
集合。每个交叉节点和叶节点可以用单独定点 y ? Y 表示， 而横越节点段(组)（若多于一个的连续横越节点相连接，称 为横越节点段或组）可用一个或多个顶点 y ? Y 表示。 为了陈述方便， 在无向连接树 T N (V N , E N ) 中， E N 中的 元素称为边， V
N
n20 s11 s5 h1 n1 s1 s6 s2 h2 n13 s7 s9 n7 n6 n8
中的元素称为节点。而 T N 对应的辅助结
Y 构树 H (Y , A ) 中， 中的元素称为顶点，A 中的元素称为弧。
需要强调的是元素 y ? Y ，可能包含多个 T N 中的节点，理 由我们在后面章节给予阐述。无向连接树 T N (V N , E N ) 与其 对应的辅助结构树 H (Y , A ) 之间存在同构的 关 系 。 定义 2。 一般说来， 两个图 G 和 H 是同构的(记为 G @ H )， 如果存在两个一一映射
q
f
[7]
s10 n14
h3 s13 n15
： V (G ) ? V ( H ) ： E (G ) ? E ( H )
G
n25
( f ( e )) = q ( u ) q ( v )
使得 j
(e) = uv
当且仅当 j
H
，这样的映射 图 2－(1) 属性 1。
N N
对 ( u , v ) 称为 G 和 H 之间的一个同构。 所以，通过细分辅助结构树 H ，使得每个交叉节点在 H 中都用独立的顶点 y 代替， 一旦达到这种状态， 那么就可以 反向得到 H 所对应的无向树 T 。相反，通过无向树 T ，
N N
T
(V
, E ) 中任意一对节点 v , u ? V
N
N
i.
如果节点 u 是 v 的子孙节点，则
Bv ê Bu
也可以得到辅助结构树 H 。很容易发现，由无向树 T N 可以 得到唯一的骨架树 H ，反向推导则不成立。 定义 3。 如果辅助结构树 H 中任意顶点 y ? Y 映射到无向树
T
N
。 。
ii.
节点 v ? N ，或者 v 是交叉节点，则
Bv é Bu
中的节点 v 都是一一对应，即由 H (Y , A ) 到 T N 的映射，
V
N
为了下面讨论，现引入有序序列表 L 。 节点 v ? V
N
总存在唯一节点 v ?
与顶点 y ? Y 对应，那么称他们是信 ，按照 | B v | 值大小，生成序列表 L 。如果节
任节点或信任顶点。所以给定网络中,如果任意节点都是信 任节点，那么这个网络拓扑结构可以被唯一确定。
点具有相同 | B v | 值，则横越节点排列在交叉节点前面。在 图 2－(1)中, n1 是根节点,根据 | B v | 值的大小, n1 是序列 L 的 第一个元素， 所有的叶节点的 | B v | 值最小， 所以在列表 L 的
B. 辅助结构树生成 ATC 算法概述
s 最后。 1 是交叉节点， 而其他的交换机 s 2 , s 5 , s 6 , s 7 , s 9 , s11 , s13 都
是横越节点，由属性 1 可知,在序列表 L 中, s1 在其他交换机 辅助结构树生成算法是拓扑算法的核心部分，在 IV 章节 会详细的介绍。 的 前
1
面
n ,
1
,
s ,
2
所
s ,
6
以
s ,
子
7
网
9
N1
1
的
s5 ,
序
s1 ,
列
1
是
s , 1 n3 , n6 , n7 ,
L= {
s ,
s ,
s 2,
6
小
型
微
型
|
计 算
机
系
统
N
2008 年 的连接树，所以任意叶节点
， 其中 s 2 , s 6 , s 7 , s 9 具有相同的 | B v | 值, s 5 , s11 , s13 具有相同 | B v 值。
证明: 由于 T N 是集合
v? V
N
ATC 算法依据元素 e 在序列 L 中的顺序， 首先取第一个序 列元素 n1 ，作为辅助结构树的第一个节点，并可以计算出
Bn
1
且 v ? N 。由 B v 的计算表达式可得，任意子树都至
少包含一个叶节点。 属性 3： 任意节点 v 以及其任意子孙节点 u ， 存在 B v 且 | Bv
|3 | B u | ê Bu
的值。然后取出 s1 节点作为第二节点。由于 s 6 , s 7 , s 9 都
。
V
N
是横越节点而且 | B v | 值都相同所以不需要区别顺序，所以 在辅助结构树中仅用同一个顶点代表。由 B s 2 与 B s1 2 值的差 异可以判断出，在 s 2 和 s 8 之间存在一个 False 节点 Hub。同 理, s1 与 s 5 、 s11 之间也存在 Hub 节点， s 6 , s 7 , s 9 与 s1 3 之间 存在 Hub 节点，见图 2－(2) 。
属性 4 ： 任意节点 v ? N ，其子孙节点 u ?
Bv é Bu
，存在
且 Bv
|> | B u |
。
Bu
证明:由属性 2 可知 B v ê
表达式为
Bv =
。由于 v ? N ，且 B v 的计算
?
k ? Dv { v ( r )}
Fv , k
N
惹({ v }
N)
s11 s5 h1
n1 s1 s2 s6
存在 B v
可推导 B v 包含 v ，但不在 B u 中。得证。 属性 5： 任意交叉节点 v ?
é Bu V
N
， 其任意一子孙节点 u ?
V
N
，
且 Bv
|> | B u |
。
3
证明:节点 v 是交叉节点，所以度 d ( v ) 3
v? V
N
，即叶节点数
量 k 3 2 。由属性 1 可知任意子树至少包含一个节点
s7
s9
(应该是叶节点)。得证。
h2
利用以上属性可以确定节点之间的顺序。现定义 n v ：等 式2
ì | N | + 1/ 2 : 如 果 v = r; ? ? ? nv = ? | Bv | - 1 / 2 : 如 果 v N 或 是 交 叉 节 点 ; í ? ? ? | Bv | :其 它 节 点 , 如 横 越 节 点 ; ? ?
h3 s13
定义 5：节点 v 在序列 L 中是完备的是指:节点 v 出现在 图 2－(2) 从列表 L 中依据 | B v | 的值大小依次提取节点,最终可以得 到T
N1
其所在序列的所有父节点之后，出现在所有子孙节点之前。 引理 1: 任意节点 v ? N 以及交叉节点在序列 L 中顺序是 完备的。
的辅助结构树 H 。
IV 辅助结构树生成(ATC)算法 本章节详细介绍 ATC 算法。介绍之前先阐述几个理论基 本属性。然后介绍在 ATC 算法中是如何应用的。
证明:由等式 2 可知根节点 n r
= | N | + 1/ 2
,故在序列 L
中是第一个节点。假设节点 v ? N 以及交叉节点, u 是其子 节 点 ( u ? N 或 交 叉 节 点 或 横 越 节 点 ), 由 属 性 3,4 可 得
| Bv ? Bu | | |
,1 v n
> nu
= | Bv | - 1 / 2
, nu = | Bu | - 1 / 2或 nu = | Bu | , 综
上可得即 n v A. 基本属性定义
。得证。
但是引理 1 不适合交叉节点，因为横越节点不包含在 N 中。在辅助结构树中具有相同 n v 值的横越节点用一个顶点
现有节点集(一个或多个子网),且 T (V , E ) 为无向连
N N N
接树。 r ? N 为根节点。假设任意节点 v ? 于 N 都是完备的,任意节点 v ?
v(r )
V
N
V
N
的 AFT 相对
表示。为了区别横越节点顺序，应用如下引理： 引理 2： 任意两横越节点 u , v ? V
N
，根端口(root－port)是指
N
, Bu
= B v , Pu , v
为两
与根节点相连接的端口，其他端口 D v N － v ( r ) 为叶端口
节点之间的路径,假设路径 Pu , v 中存在节点 w ，则 w 也是横 越节点且 B w
= Bv
(leaf－ports)。所以 B v 表达式为：
Bv =
。
N
证明:由属性 3,4 可得， 如果节点 w 是 w ?
N
或交叉节点，
?
k ? Dv { v ( r )}
Fv , k
惹({ v }
N)
则 Bw
é Bv
。由于题设中 B w
= Bv
，所以 w 必横越节点。
集合 { B v } 有以下属性： 属性 2： T 中任意节点 v ? V
N
N
推论 1： 假定存在横越节点 v ? , Bv
蛊 V
N
, C 是所有横越节点集合且
。
1 期
N
图论在网络拓扑发现算法中的应用 ,如果任意节点 u ? C , B u = B v ,则所有 C 中节点是连
7
（ 表示，并修改 H Y, A）， 为了方便讨论，约定末梢弧已知连
C ì V
接节点记作 y 。 首先验证末梢弧 a ? Z 是否与新抽取的元素
续的。
v 相连接：
引理 1:如果存在 B a ê B v ' 关系，则与节点 v ' 相连接，否 则 v ' 不与末梢弧 a 连接。 STC 算法目标就是把连接树 T N (V N , E N ) 转化为辅助结
（ 构树 H Y, A）。 转化过程是迭代的过程， 初始化状态 H 为空，
'
B.
ATC 算法 (Algorithm)
ATC 算法在依据等式 2 计算节点 n v 值的时候，判断横
越节点准则： 如果 n y = n v ' 且是整数， 那么 v 与 y 节点都是 横越节点。如果是横越节点则添加节点 v 到集合 C y 中，在
H
6
每次迭代过程中加入 TRUE 节点 v ?
V
N
V
N
到 H 中，直到所有
'
中的 TRUE 节点都在 H 中。 STC 算法需要初始值 V
N
集合、N 集合、 根结点 r ? N 和
'
所有节点 v ?
V
N
的 AFT 信息即 F N v , k 。在 H 中每个顶点 ( C y 中包含 一个或 多个节点
中都用 y 表示。见图 3－(b)。 s 6 , s 7 都是横越节点，且
7
B s = B s = { n14 , n15 , n 25 }
， n s6 = n s7 。
y? Y
都代表集 合 C y ì V N
v ), n y 代表 T N 中节点 n v 值。如果 H 中某节点 y 包含了多
个横越节点，则节点 v ? C y 具有相同的 n v 值。 H 中弧 a 代 表 T N 中的边。在计算 H 中弧的过程中，必然会出现弧的前 端连接有节点,另一端末梢节点没有连接节点或称没有发现, 这种弧称为末梢弧(见图 3－(a)中)，末梢弧集合记作 Z 。如 果末梢弧的末梢节点被发现，则此末梢弧从集合 Z 中被删 除。每一弧 a ? A 都有相应的一个集合 B a 相对应。 B a 是指 通过弧 a 所能到达的节点集合即： 节点 v 的某个端口 k （连 接弧 a 的端口）的 AFT 值。为了详细阐述 ATC 算法，仍 以图 2－(1)为例。
n1
s1 s2
s6
s7
{n14 , n15 , n25 }
V
N
ATC 算法首先获得每个节点 v ?
和 n v 的值。然后比较节点 V
N
的根端口 v ( r ) ， B v
图 3－(b)
如果 n y > n v ' ，那么 v ' 在 H 中将用新的顶点 y ' 表示。顶点
y
'
- {r}
的 n v 值，构造序列 L 。
（ ） 然后初始化 H Y , A ，选择顶点 y 代表根节点 r ，并记
y 对应集合
N v
'
'
C
y
'
= {v }
'
， n y' = nv' ,
'
v
'
的每个叶端口
C y = {r }
， n y = | N | + 1 / 2 (依据等式 2)，并把与根节点连
k? D { v ( r) } ，都对应有末梢弧 a
'
接的 | D N r | 个末梢弧添加到 Z 集合中。图 3－(a)是 STC 算 法初始状态。
，并添加到 Z 中。如
果 B v = B v ' ，则 v ' 与 v 之间直接连接即不存在其它节点。图
n1
末梢弧
3－(c), n s6 = n s7 = 3 , n s9 = 2 .5 ,所以节点 s 9 在 H 中用新的 顶点 y 代替。由于 B s 6 = B s 7 = B s9 = { n14 , n15 , n 25 } ，故 s 9 与 s 6 或 s 7 直接连接。
{n6, n7 , n8 , n13 , n14 , n15 , n20 , n25 }
图 3－(a)
初始化后，ATC 算法反复从序列 L 中抽取第一元素，用 v
'
8
小
型
微
型
计 算
机
系
统
2008 年
n1
顶点 x 代表 Hub, x 与顶点 y （ s 9 节点）连接，与顶点 y ' （ n1 4 节点）连接。故，顶点 x 的另一个末梢弧 a 2 具有
s1 s2
B a = { n15 }
2
，见图 3－(e)。
n1
s6
s7
s1 s2
s9
s6 s7
{n25 }
{n14 , n15 }
y
图 3－(c)
假设 B a é B v ' （a 是末梢弧） ，那么节点 v ' 的上级节点是 FALSE 节点，存在两种情况需要考虑： 1. 如果 y 是 TRUE 顶点，C y 蛊 插入 FALSE 顶点 x ，且 C x
=
s9
a1 h3 x y n14
'
{n25 }
{n15 }
，则
,那么在 y 与 y ' 顶点之间 ， nx
= | Ba | - 1 / 2
图 3－(e)
2. 如果顶点 y 是 FALSE 节点（如，Hub） C y = ，
? 顶点 y 是节点 v 的父节点。此时创建新末梢弧 a 且
Ba = Ba - Bv ?
（依
据等式 2，顶点 x 是交叉顶点类型） 。由顶点 x 引伸出 的 2 个末梢弧 a1 ， a 2 。算法首先用弧 a 连接顶点 x ， 然 后 用 顶 点 x 的 其 中 一 个 末 梢 弧 a1 连 接 y ' 顶 点 即
Ba = B
1
? ，然后添加末梢弧 a 到 Z 中，末梢弧 a 连
接节点 v （即顶点 y ' ） ，删除末梢弧 a 。见图 3－(f) 。
n1
y
'
（ a1 是末梢弧线） B a 2 = B a - B y （ a 2 是顶点 ，
x
的另一个末梢弧， a 是顶点 y 的末梢弧） 。最后从集
s1 s2 h2 n7
y s 9
合 Z 中删除末梢弧 a ，添加末梢弧 a 2 。
n1
s1 s2
s6
s7
{n6 , n8 }
s6
s7
a1 h3 x y' n14
{n25 }
y
s9
a1 h3 x y n14
'
{n15 }
{n25 }
图 3－(f)
假设算法从序列 L 中抽取节点元素 n 7 。由于顶点 x 有 末梢弧 a 且 B a 种情况： 1. 在顶点 n 6 与 x 之间存在另一个 FALSE 节点 即 Hub。
= { n 6 , n8 }
图 3－(d)
在图 3－(d)中，n1 4 是新发现的节点在 H 中用 y ' 代表， y 是代表 s 9 节点。 由于 B s9 = { n1 4 , n1 5 } ，n1 4 需要与 s 9 的其中 一个末梢弧 a1 （ B a1 = { n1 4 , n1 5 } ， B a1 é B n14 ）连接。添加
，也就是说通过这末梢弧 a 可
以到达节点 n 6 。但是因为 B a 包含也节点 n 8 ，此时有两
1 期 2.
图论在网络拓扑发现算法中的应用 顶点 x （Hub）存在另一端口连接顶点 n 8 。
9
个节点 v ? N ，或交叉节点，在 H (Y , A ) 中表现都是出现在 其所有子节点之前，所有父节点之后，即顺序是固定的。从 序列 L 中选定节点元素 v ，如果父节点的 k th 末梢弧 a ? Z ，
Ba = Bv
从网络布线的实际设计思路考虑， 后者出现的几率要高。 所以 ATC 算法搜寻连接顶点 n 6 与 x ， 然后添加新的 x 末梢
? 弧 a 且 B a?
= { n8 }
，见图 3－(g)。
， 那么节点元素 v 与末梢弧 a 相连。 所以在 H (Y , A )
n1
中的位置是唯一确定的。 假如 B a 1 B v ， 那么在顶点 y 与 v ' 之 间插入 FALSE 节点 x 。利用引理 2,在 T N 中具有相同 B v 的
s1 s2 h2 n7 {n6 } {n8 }
y s 9
横越节点，在 H 中用同一顶点 y ? Y 表示。综上可知，
H (Y , A )
是一颗有效的树 e。
s6
s7
C. 降低难度系数：获取完备的 AFTs 信息。
由 B v 的定义，每个节点 v ? V
N
所包含的 AFTs 信息
a1 h3 x y' n14
就是节点 v 的所有叶端口 AFT 信息总和。所以只要这些 叶端口完备即可。判断根端口则通过端口的 AFT 是否包 含根节点。 必要条件 1:给定连接树 T N (V N , E N ) ， 且集合 N 已知，
{n25 }
{n15 }
N1
图 3－(g)
按同样的方法最终把图 2－(1)中的无向树 T 辅助数据树如图 3－(h)。 转化为对应的
r 是其根节点。每个节点 v ?
V
N
，根端口 v ( r ) 的 AFT 必
须包含根节点 r ，所有叶端口 D N v - { v ( r )} 在 N 中必须完 备的。
{n20 }
n20
n1
在下一章中介绍必要条件 1 很容易满足。
s11 s5
{n13}
D. (AFTs-Supplement) 信息
h1
s1 s2 h2 n7 {n6 } {n8 }
y s 9
{n25 }
在 IV-C 部分介绍在了 AFTs 不完整的情况下如何得 到辅助结构树。 但是我们在合并所有子网的辅助结构树 时候，需要每个节点的 AFTs 信息包含前导端口所指向 的节点信息。为了方便讨论，把这部分信息记为
AFT s - S
s6
s7
。现假设 X í V
N
是 T N 中信任节点集合。以
辅助结构树为数据基础， 根节点 r 为起点， 后序遍历方 式，采用递归方法计算得到 AFT s - S 。在计算过程中， 任意以顶点 y ? Y 为根节点的子树都对应存在信任节 点集合 X y 。 下面详细阐述 AFT s - S 程序实现过程：给定顶点
y? Y
a1 h3 x y' n14
{n15 }
以及其子节点记为
y1 , y 2 , ? , y J ? Y
，在后序遍历
（post-order tour）过程中，每个 y 的子节点 y j 都把其 信任节点集合 X y j 返回给 y ，获得所有子节点 y j 的信 任集合 { X y j } 后就可以得到顶点 y 的信任节点集合 X y
J
图 3－(h)
定理 1：给定连接树 T N (V N , E N ) ，并指定根节点 r ? N ， STC 算法相应的创建辅助结构树 H (Y , A ) ，在 T N 中每个节 点 v ? N ，或交叉节点在 H 中都可以被唯一的顶点 y 表示。
证明:序列 L 中的元素加入到辅助结构树 H (Y , A ) 过程中
都是按照在 L 中的顺序依次加入。由引理 1 可知， T N 中每
即： X y = ( ? X y j ) ? ( X ? C y ) 。顶点 v ? C y 的每个叶端
j= 1
10
小
型
微
型 计
算
机
系
统
2008 年
口都对应着一个子节点 y j ，添加 X y j 到顶点 v 对应端 口的 AFT 信息中，端口 v ( r ) 增加 X - X y 信息。
B. 复杂度。
阐 述 本算 法 的复 杂度 。 TD 算 法 主要 由 STC 算 法 和
A F T s _S
两部分组成。 先考虑时间复杂度。 STC 算法的运行 ，所以 TD 算法运行时间的复杂度是 O (| V |3 ) 。
E. 合并辅助结构树
时间复杂度是 O (| V | 2 ) ， A F T s_ S 算法的运行时间复杂度是
O (| V | )
2
TD 算法由两个主要部分组成.首先,依据 ATC 辅助结构 VII 总结 树生成算法计算每个子网 N ?
N v 的辅助结构树 H 。需要
本文详细讨论了怎样利用图论的理论知识来实现网络拓 扑结构的自动发现，介绍了拓扑发现算法中的主要两步骤， 同时对实现过程中的关键技术进行了详细分析。 但是本文在分析 FALSE 节点的时候，还没有给出很好 的算法分析， 所以下一步工作重点是重点研究 FALSE 节点， 研究出发点是 FALSE 节点与 TRUE 节点对网络数据流的影 响，找出特征，进一步分析处理，旨在提高网络拓扑算法的 准确度，降低算法的复杂度。 References:
[1] Y.Bejerano, Y.Breitbart, M.Garofalakis, and R.Rastogi, Physical Topology Discovery for Large Multi-Subnet Networks [J], July 2002, Bell Labs Tech. Memorandum. [2] B.Lowekamp, D.R.O’Hallaron, and T.R.Gross, “Topology Discovery for Large Ethernet Networks”, in Proceedings of ACM SIGCOMM,
获得子网的信息包括：子网内的所有节点列表，根节点 ri ，
V
Ni
以及子网内节点的 AFTs 信息，依据获得的有效信息每
个子网可以对应生成一个辅助结构树。 然后我们可以根据一 定的规则合并每个子网的辅助结构树。 现有两辅助结构树 H i (Yi , Ai ) ， H j (Y j , A j ) 。 N i , N j 分别 是其节点结合， X i , X j 是信任节点结合。 假设两辅助结构树 具有共同的信任节点（至少一个） ，那么这两辅助结构树可 以合并，即 n ? X i ? X j 且 | n |3 1 。合并以后 N = N i ? N j ，
X = Xi ? X
j
。再次选择一辅助结构树与之合并，递归合并
后，如果最终合并结果是一颗独立的辅助结构树 H ――即 计算所需要的该网络拓扑物理结构。
VI 算法分析
San Diego, California, Aug.2001. [3] J.Case,M.Fedor, M.Schoffstall, and J.Davin,“A Simple Network Management Protocol (SNMP)”,1990,Internet RFC-1157 (available
A. 正确性。
[4]
from https://www.wendangku.net/doc/2817334085.html,/rfc/) W.Stallings, “SNMP, SNMPv2, SNMPv3, and RMON 1 and 2”.Addison-Wesley Longman,Inc,1999,(Third Edition) [5] Y. Breitbart, M. Garofalakis, C.martin, R.Rastogi, S.Seshadri, and A.Silberschatz, “Topology proceedings Discovery of in Heterogeneous IP
现证明算法的正确性与复杂度。 本论文中 TD 算法的正确 性完全依赖于 ATC 算法的正确性。
定理 2：TD 算法为每个子网 N i ? N 可以创建一个辅助
结构树。
Networks”,
in
IEEE
INFOCOM’2000,Tel
Aviv,Israel,Mar.2000. [6] Donnet B, Raoult P, Friedman T, Crovella M. Efficient algorithms for large-scale topology discovery. In: Eager DL, Williamson CL, Borst SC, Lui JCS, eds. Proc. of the ACM SIGMETRICS 2005. New York: ACM Press, 2005. 327?338. [7] Govindan R, Tangmunarunkit H. Heuristics for Internet map discovery. In: Sidi M, Sengupta B, eds. Proc. of the IEEE INFOCOM 2000. New York: IEEE Press, 2000. 1371?1380.
证明:(由定理 1 可以得证)
下面证明合并辅助结构树算法的正确性。 假设存在两辅助 结构树
Ni H i ( Yi , Ai )
和 H j (Y j , A j ) 以 及 对 应 连 接 树 节 点 集 合
， N j 。他们信任节点集合为 X i 和 X j ，且 v ? X i ? X j ， 。 算法合并后， N = N i ? N j ，V N = V N i ? V TD 记
N
v蛊
Nj
。
经证明节点 V
的 AFTs 信息对于集合 N ? {v} 满足必要条件
1。即合并后的连接树是有效的。
图论算法及其MATLAB程序代码
图论算法及其MATLAB 程序代码 求赋权图G =(V ,E ,F )中任意两点间的最短路的Warshall-Floyd 算法： 设A =(a ij )n ×n 为赋权图G =(V ,E ,F )的矩阵,当v i v j ∈E 时a ij =F (v i v j ),否则取a ii =0,a ij =+∞(i ≠j ),d ij 表示从v i 到v j 点的距离,r ij 表示从v i 到v j 点的最短路中一个点的编号. ①赋初值.对所有i ,j ,d ij =a ij ,r ij =j .k =1.转向② ②更新d ij ,r ij .对所有i ,j ,若d ik +d k j ＜d ij ,则令d ij =d ik +d k j ,r ij =k ,转向③. ③终止判断.若d ii ＜0,则存在一条含有顶点v i 的负回路,终止;或者k =n 终止;否则令k =k +1,转向②. 最短路线可由r ij 得到. 例1求图6-4中任意两点间的最短路. 解：用Warshall-Floyd 算法,MATLAB 程序代码如下： n=8;A=[0281Inf Inf Inf Inf 206Inf 1Inf Inf Inf 8607512Inf 1Inf 70Inf Inf 9Inf Inf 15Inf 03Inf 8 Inf Inf 1Inf 3046 Inf Inf 29Inf 403 Inf Inf Inf Inf 8630];%MATLAB 中,Inf 表示∞ D=A;%赋初值 for (i=1:n)for (j=1:n)R(i,j)=j;end ;end %赋路径初值 for (k=1:n)for (i=1:n)for (j=1:n)if (D(i,k)+D(k,j) 1.1、prim算法: 无向图的生成树就是从图的边集中选择一些边，使得这些边构成一个连通无环图，也就是树。如果给每一条边加一个权，所有生成树中权和最小的生成树称为最小生成树。 【Prim算法思想】 任意时刻的中间结果都是一棵树，每次花费最小的代价，用一条边把不在树中的结点加进来。【最小生成树算法实例】 现有一张城市地图，图中的顶点为城市，无向边代表两个城市间的连通关系，边上的权代表公路造价。在分析了这张图后发现，任一对城市都是连通的。现在要求用公路把所有城市联系起来，如何设计可使得工程的总造价最少？ 【输入】第一行两个数v(v<=200),e，分别代表城市数和边数以下e行，每行为两个顶点和它们之间的边权w(w<1000)。 【输出】连通所有城市的公路最小造价。 【输入样例】 6 10 1 2 10 1 5 19 1 6 21 2 3 5 2 4 6 2 6 11 3 4 6 4 5 18 4 6 14 5 6 33 【输出样例】50 原图 最小生成树 #include d[i]=INT_MAX; } d[f]=0; s=0; for(i=1;i<=n;i++) { mi=INT_MAX; for (j=1;j<=n;j++) if ((v[j]==false) && (d[j] 一笔画问题是图论中一个著名的问题。一笔画问题起源于柯尼斯堡七桥问题。数学家欧拉在他1736年发表的论文《柯尼斯堡的七桥》中不仅解决了七桥问题，也提出了一笔画定理，顺带解决了一笔画问题[1]。一般认为，欧拉的研究是图论的开端。 与一笔画问题相对应的一个图论问题是哈密顿问题。 目录[隐藏] 1 问题的提出 2 一笔画定理 2.1 定理一 2.2 定理二 3 例子 3.1 七桥问题 3.2 一个可以一笔画的例子 4 一笔画问题与哈密顿问题 5 参见 6 参考来源 [编辑] 问题的提出 一笔画问题是柯尼斯堡问题经抽象化后的推广，是图遍历问题的一种。在柯尼斯堡问题中，如果将桥所连接的地区视为点，将每座桥视为一条边，那么问题将变成：对于一个有着四个顶点和七条边的连通图G(S,E)，能否找到一个恰好包含了所有的边，并且没有重复的路径。欧拉将这个问题推广为：对于一个给定的连通图，怎样判断是否存在着一个恰好包含了所有的边，并且没有重复的路径？这就是一笔画问题。用图论的术语来说，就是判断这个图是否是一个能够遍历完所有的边而没有重复。这样的图现称为欧拉图。这时遍历的路径称作欧拉路径（一个圈或者一条链），如果路径闭合（一个圈），则称为欧拉回路[1]。 一笔画问题的推广是多笔画问题，即对于不能一笔画的图，探讨最少能用多少笔来画成。 [编辑] 一笔画定理 对于一笔画问题，有两个判断的准则，它们都由欧拉提出并证明[1]。 [编辑] 定理一 有限图G是链或圈的充要条件是：G为连通图，且其中奇顶点的数目等于0或者2。有限连通图G是圈当且仅当它没有奇顶点[2]。 证明[2][3]： 必要性：如果一个图能一笔画成，那么对每一个顶点，要么路径中“进入”这个点的边数等于“离开”这个点的边数：这时点的度为偶数。要么两者相差一：这时这个点必然是起点或终点之一。注意到有起点就必然有终点，因此奇顶点的数目要么是0，要么是2。 充分性： 如果图中没有奇顶点，那么随便选一个点出发，连一个圈C1。如果这个圈就是原图，那么 5经典图论问题 5.1 一笔画问题 一笔画算法即是从起点a开始选择关联边（第一这条边不是往回倒，第二这条边在前面延伸路上没有出现过）向前延伸，如果到达终点b，得到a—b迹，判断路上的的边数是否为图的总边数，是就终止，否则选择迹上某个关联边没有用完的顶点v，用同样方式再搜索v—v的闭迹，添加到a—b迹上，即得到a—v---v—b迹，如果这个迹的边数还没有达到总边数，则再选择迹上某个关联边没有用完的顶点。。。。。。逐步扩展即可。 二、弗罗莱（Fleury ）算法 任取v 0∈V(G)，令P 0=v 0； 设P i =v 0e 1v 1e 2…e i v i 已经行遍，按下面方法从中选取e i+1： （a ）e i+1与v i 相关联； （b ）除非无别的边可供行遍，否则e i+1不应该为G i =G-{e 1,e 2, …, e i }中的桥（所谓桥是一条删除后使连通图不再连通的边）； （c ）当（b ）不能再进行时，算法停止。 5.2 中国邮递员问题（CPP ） 规划模型： 设ij x 为经过边j i v v 的次数，则得如下模型。 ∑∈= E v v ij ij j i x z ?min ∑ ∑ E ∈E ∈∈=j i i k v v i v v ki ij V v x x , E ∈∈≤j i ij v v N x ,1 ..t s 5.3旅行推销员问题（TSP，货郎担问题）（NPC问题） 定义：包含图G的所有定点的路（圈）称为哈密顿路（圈），含有哈密顿圈得图称为哈密顿图。 分析：从一个哈密顿圈出发， 算法一：（哈密顿圈的充要条件：一包含所有顶点的连通子图，二每个顶点度数为2） 象求最小生成树一样，从最小权边加边，顶点度数大于3以及形成小回路的边去掉。 算法二： 算法三： 图论实验三个案例 单源最短路径问题 Dijkstra 算法 Dijkstra 算法是解单源最短路径问题的一个贪心算法。其基本思想是，设置一个顶点集合S 并不断地作贪心选择来扩充这个集合。一个顶点属于集合S 当且仅当从源到该顶点的最短路径长度已知。设v 是图中的一个顶点，记()l v 为顶点 v 到源点v 1的最短距离， ,i j v v V ?∈，若 (,)i j v v E ?，记i v 到j v 的权ij w =∞。 Dijkstra 算法： ① 1{}S v =,1()0l v =；1{}v V v ??-,()l v =∞,1i =,1{}S V v =-； ② S φ=，停止，否则转③； ③ ()min{(),(,)} j l v l v d v v =， j v S ∈，v S ?∈； ④ 存在 1 i v +，使 1()min{()} i l v l v +=，v S ∈； ⑤ 1{} i S S v +=， 1{} i S S v +=-，1i i =+，转②； 实际上，Dijkstra 算法也是最优化原理的应用：如果12 1n n v v v v -是从1v 到 n v 的最短路径，则 12 1 n v v v -也必然是从1v 到 1 n v -的最优路径。 在下面的MATLAB 实现代码中，我们用到了距离矩阵，矩阵第i 行第j 行元 素表示顶点i v 到j v 的权ij w ，若i v 到j v 无边，则realmax ij w =，其中realmax 是 MATLAB 常量，表示最大的实数+308)。 function re=Dijkstra(ma) Dijkstra 算法： 用矩阵n n a ?（n 为顶点个数）存放各边权的邻接矩阵，行向量 pb 、1index 、2index 、d 分别用 来存放P 标号信息、标号顶点顺序、标号顶点索引、最短通路的值。其中分量 ? ? ?=顶点未标号当第顶点已标号 当第i i i pb 01)(； )(2i index 存放始点到第i 点最短通路中第i 顶点前一顶点的序号； )(i d 存放由始点到第i 点最短通路的值。 求第一个城市到其它城市的最短路径的Matlab 程序如下： clear; clc; M=10000; a(1,:)=[0,50,M,40,25,10]; a(2,:)=[zeros(1,2),15,20,M,25]; a(3,:)=[zeros(1,3),10,20,M]; a(4,:)=[zeros(1,4),10,25]; a(5,:)=[zeros(1,5),55]; a(6,:)=zeros(1,6); a=a+a'; pb(1:length(a))=0;pb(1)=1;index1=1;index2=ones(1,length(a)); d(1:length(a))=M;d(1)=0;temp=1; while sum(pb) 各种聚类算法的比较 聚类的目标是使同一类对象的相似度尽可能地小；不同类对象之间的相似度尽可能地大。目前聚类的方法很多，根据基本思想的不同，大致可以将聚类算法分为五大类：层次聚类算法、分割聚类算法、基于约束的聚类算法、机器学习中的聚类算法和用于高维度的聚类算法。摘自数据挖掘中的聚类分析研究综述这篇论文。 1、层次聚类算法 1.1聚合聚类 1.1.1相似度依据距离不同：Single-Link:最近距离、Complete-Link：最远距离、Average-Link：平均距离 1.1.2最具代表性算法 1）CURE算法 特点：固定数目有代表性的点共同代表类 优点：识别形状复杂，大小不一的聚类，过滤孤立点 2）ROCK算法 特点：对CURE算法的改进 优点：同上，并适用于类别属性的数据 3）CHAMELEON算法 特点：利用了动态建模技术 1.2分解聚类 1.3优缺点 优点：适用于任意形状和任意属性的数据集；灵活控制不同层次的聚类粒度，强聚类能力 缺点：大大延长了算法的执行时间，不能回溯处理 2、分割聚类算法 2.1基于密度的聚类 2.1.1特点 将密度足够大的相邻区域连接，能有效处理异常数据，主要用于对空间数据的聚类 1）DBSCAN：不断生长足够高密度的区域 2）DENCLUE：根据数据点在属性空间中的密度进行聚类，密度和网格与处理的结合 3）OPTICS、DBCLASD、CURD：均针对数据在空间中呈现的不同密度分不对DBSCAN作了改进 2.2基于网格的聚类 2.2.1特点 利用属性空间的多维网格数据结构，将空间划分为有限数目的单元以构成网格结构； 1）优点：处理时间与数据对象的数目无关，与数据的输入顺序无关，可以处理任意类型的数据 2）缺点：处理时间与每维空间所划分的单元数相关，一定程度上降低了聚类的质量和准确性 2.2.2典型算法 1）STING：基于网格多分辨率，将空间划分为方形单元，对应不同分辨率2）STING+：改进STING，用于处理动态进化的空间数据 3）ＣＬＩＱＵＥ：结合网格和密度聚类的思想，能处理大规模高维度数据4）WaveCluster：以信号处理思想为基础 2.3基于图论的聚类 2.3.1特点 转换为组合优化问题，并利用图论和相关启发式算法来解决，构造数据集的最小生成数，再逐步删除最长边 1）优点：不需要进行相似度的计算 2.3.2两个主要的应用形式 1）基于超图的划分 2）基于光谱的图划分 2.4基于平方误差的迭代重分配聚类 2.4.1思想 逐步对聚类结果进行优化、不断将目标数据集向各个聚类中心进行重新分配以获最优解 聚类分析法 先用一个例子引出聚类分析 一、聚类分析法的概念 聚类分析又叫群分析、点群分析或者簇分析，是研究多要素事物分类问题的数量，并根据研究对象特征对研究对象进行分类的多元分析技术，它将样本或变量按照亲疏的程度，把性质相近的归为一类，使得同一类中的个体都具有高度的同质性，不同类之间的个体都具有高度的异质性。 聚类分析的基本原理是根据样本自身的属性，用数学方法按照某种相似性或差异性指标，定量地确定样本之间的亲疏关系，并按这种亲疏关系程度对样本进行聚类。 描述亲属程度通常有两种方法：一种是把样本或变量看出那个p维向量，样本点看成P 维空间的一个点，定义点与点之间的距离；另一种是用样本间的相似系数来描述其亲疏程度。有了距离和相似系数就可定量地对样本进行分组，根据分类函数将差异最小的归为一组，组与组之间再按分类函数进一步归类，直到所有样本归为一类为止。 聚类分析根据分类对象的不同分为Q型和R型两类，Q--型聚类是对样本进行分类处理，R--型聚类是对变量进行分类处理。 聚类分析的基本思想是，对于位置类别的样本或变量，依据相应的定义把它们分为若干类，分类过程是一个逐步减少类别的过程，在每一个聚类层次，必须满足“类内差异小，类间差异大”原则，直至归为一类。评价聚类效果的指标一般是方差，距离小的样品所组成的类方差较小。 常见的聚类分析方法有系统聚类法、动态聚类法（逐步聚类法）、有序样本聚类法、图论聚类法和模糊聚类法等。 二、对聚类分析法的评价 聚类分析也是一种分类技术。与多元分析的其他方法相比，该方法较为粗糙，理论上还不完善，但应用方面取得了很大成功。与回归分析、判别分析一起被称为多元分析的三大方法。 聚类的目的：根据已知数据，计算各观察个体或变量之间亲疏关系的统计量（距离或相关系数）。根据某种准则（最短距离法、最长距离法、中间距离法、重心法），使同一类内的 图论〔Graph Theory〕是数学的一个分支。它以图为研究对象。图论中的图是由若干给定的点及连接两点的线所构成的图形，这种图形通常用来描述某些事物之间的某种特定关系，用点代表事物，用连接两点的线表示相应两个事物间具有这种关系。 图论与数学的关系 图论本身是应用数学的一部份，因此，历史上图论曾经被好多位数学家各自独立地建立过。关于图论的文字记载最早出现在欧拉1736年的论著中，他所考虑的原始问题有很强的实际背景。 图论的起源 图论起源于著名的柯尼斯堡七桥问题。在柯尼斯堡的普莱格尔河上有七座桥将河中的岛及岛与河岸联结起来 问题是要从这四块陆地中任何一块开始，通过每一座桥正好一次，再回到起点。然而无数次的尝试都没有成功。欧拉在1736年解决了这个问题，他用抽像分析法将这个问题化为第一个图论问题：即把每一块陆地用一个点来代替，将每一座桥用联接相应的两个点的一条线来代替，从而相当于得到一个“图”（如下图）。 欧拉证明了这个问题没有解，并且推广了这个问题，给出了对于一个给定的图可以某种方式走遍的判定法则。这就是后 来的欧拉路径和欧拉回路。这项工作使欧拉成为图论〔及拓扑学〕的创始人。 汉密尔顿的游戏与图论 1859年，英国数学家汉密尔顿发明了一种游戏：用一个规则的实心十二面体，它的20个顶点标出世界著名的20个城市，要求游戏者找一条沿着各边通过每个顶点刚好一次的闭回路，即“绕行世界”。用图论的语言来说，游戏的目的是在十二面体的图中找出一个生成圈。这个生成圈后来被称为汉密尔顿回路。这个问题后来就叫做汉密尔顿问题。由于运筹学、计算机科学和编码理论中的很多问题都可以化为汉密尔顿问题，从而引起广泛的注意和研究。 四色猜想 在图论的历史中，还有一个最著名的问题－－四色猜想。这个猜想说，在一个平面或球面上的任何地图能够只用四种颜色来着色，使得没有两个相邻的国家有相同的颜色。每个国家必须由一个单连通域构成，而两个国家相邻是指它们有一段公共的边界，而不仅仅只有一个公共点。这一问题最早于1852年由Francis Guthrie提出，最早的文字记载则现于德摩根于同一年写给哈密顿的信上。包括凯莱、肯普等在内的许多人都曾给出过错误的证明。泰特(Tait)、希伍德(Heawood)、拉姆齐和哈德维格(Hadwiger)对此问题的研究与推广引发了对嵌入具有不同亏格的曲面的图的着色问题的研究。一百多年后，四色问题仍未解决。1969年，Heinrich Heesch发表了一 图论算法m a t l a b实现求最小费用最大流算法的 MATLAB 程序代码如下： n=5;C=[0 15 16 0 0 0 0 0 13 14 0 11 0 17 0 0 0 0 0 8 0 0 0 0 0]; %弧容量 b=[0 4 1 0 0 0 0 0 6 1 0 2 0 3 0 0 0 0 0 2 0 0 0 0 0]; %弧上单位流量的费用 wf=0;wf0=Inf; %wf 表示最大流量, wf0 表示预定的流量值 for(i=1:n)for(j=1:n)f(i,j)=0;end;end %取初始可行流f 为零流 while(1) for(i=1:n)for(j=1:n)if(j~=i)a(i,j)=Inf;end;end;end%构造有向赋权图 for(i=1:n)for(j=1:n)if(C(i,j)>0&f(i,j)==0)a(i,j)=b(i,j); elseif(C(i,j)>0&f(i,j)==C(i,j))a(j,i)=-b(i,j); elseif(C(i,j)>0)a(i,j)=b(i,j);a(j,i)=-b(i,j);end;end;end for(i=2:n)p(i)=Inf;s(i)=i;end %用Ford 算法求最短路, 赋初值 for(k=1:n)pd=1; %求有向赋权图中vs 到vt 的最短路 for(i=2:n)for(j=1:n)if(p(i)>p(j)+a(j,i))p(i)=p(j)+a(j,i);s(i)=j;pd=0;end;end;e nd if(pd)break;end;end %求最短路的Ford 算法结束 if(p(n)==Inf)break;end %不存在vs 到vt 的最短路, 算法终止. 注意在求最小费用最大流时构造有 向赋权图中不会含负权回路, 所以不会出现k=n dvt=Inf;t=n; %进入调整过程, dvt 表示调整量 while(1) %计算调整量 if(a(s(t),t)>0)dvtt=C(s(t),t)-f(s(t),t); %前向弧调整量 elseif(a(s(t),t)<0)dvtt=f(t,s(t));end %后向弧调整量 《图论及其算法》 --最短路问题 学院：通信学院 姓名：周旋 学号： S110131133 指导老师：陈六新 摘要 图论是数学的一个分支，它以图为研究对象。图论中的图是由若干给定的点及连接两点的线所构成的图形，这些图形通常用来描述某些事物之间的特定关系，用点代表事物，用连接两点的线表示相应两个事物间具有的关系。通过对《图论及其应用》中最短路问题的深入学习，本文利用Dijkstra算法来解决日常生活中寻找最短路的问题。同时也是对本学期学习知识的巩固。 关键词：最短路径 Dijkstra算法迭代 Abstract Graph theory is a branch of mathematics, it studies the object of picture. Graph theory graph is given by the number of points and lines connecting the two points of the graphic form. These graphics are often used to describe a specific relationship between certain things. And with the point on behalf of things, with the line connecting the two points that have a corresponding relationship between two things. Through the "Graph Theory and Its Applications," in-depth study of the shortest path problem. In this paper, we use The Dijkstra's algorithm not only to solve everyday life to find the shortest path problem, but also for the consolidation of the semester to learn the knowledge. Keyword: shortest path Dijkstra's algorithm Iteration 聚类的目标是使同一类对象的相似度尽可能地大；不同类对象之间的相似度尽可能地小。目前聚类的方法很多，根据基本思想的不同，大致可以将聚类算法分为五大类：层次聚类算法、分割聚类算法、基于约束的聚类算法、机器学习中的聚类算法和用于高维度的聚类算法。摘自数据挖掘中的聚类分析研究综述这篇论文。 1、层次聚类算法 1.1聚合聚类 1.1.1相似度依据距离不同：Single-Link:最近距离、Complete-Link：最远距离、Average-Link：平均距离 1.1.2最具代表性算法 1）CURE算法 特点：固定数目有代表性的点共同代表类 优点：识别形状复杂，大小不一的聚类，过滤孤立点 2）ROCK算法 特点：对CURE算法的改进 优点：同上，并适用于类别属性的数据 3）CHAMELEON算法 特点：利用了动态建模技术 1.2分解聚类 1.3优缺点 优点：适用于任意形状和任意属性的数据集；灵活控制不同层次的聚类粒度，强聚类能力缺点：大大延长了算法的执行时间，不能回溯处理 2、分割聚类算法 2.1基于密度的聚类 2.1.1特点 将密度足够大的相邻区域连接，能有效处理异常数据，主要用于对空间数据的聚类 2.1.2典型算法 1）DBSCAN：不断生长足够高密度的区域 2）DENCLUE：根据数据点在属性空间中的密度进行聚类，密度和网格与处理的结合 3）OPTICS、DBCLASD、CURD：均针对数据在空间中呈现的不同密度分不对DBSCAN作了改进 2.2基于网格的聚类 2.2.1特点 利用属性空间的多维网格数据结构，将空间划分为有限数目的单元以构成网格结构； 1）优点：处理时间与数据对象的数目无关，与数据的输入顺序无关，可以处理任意类型的数据 2）缺点：处理时间与每维空间所划分的单元数相关，一定程度上降低了聚类的质量和准确性 2.2.2典型算法 1）STING：基于网格多分辨率，将空间划分为方形单元，对应不同分辨率 2）STING+：改进STING，用于处理动态进化的空间数据 3）ＣＬＩＱＵＥ：结合网格和密度聚类的思想，能处理大规模高维度数据 4）WaveCluster：以信号处理思想为基础 2.3基于图论的聚类 2.3.1特点 转换为组合优化问题，并利用图论和相关启发式算法来解决，构造数据集的最小生成数，再逐步删除最长边 1）优点：不需要进行相似度的计算 2.3.2两个主要的应用形式 1）基于超图的划分 2）基于光谱的图划分 2.4基于平方误差的迭代重分配聚类 2.4.1思想 逐步对聚类结果进行优化、不断将目标数据集向各个聚类中心进行重新分配以获最优解2.4.2具体算法 1）概率聚类算法 期望最大化、能够处理异构数据、能够处理具有复杂结构的记录、能够连续处理成批的数据、具有在线处理能力、产生的聚类结果易于解释 2）最近邻聚类算法——共享最近邻算法SNN 特点：结合基于密度方法和ROCK思想，保留K最近邻简化相似矩阵和个数 不足：时间复杂度提高到了O(N^2) 3）K-Medioids算法 特点：用类中的某个点来代表该聚类 常见问题： 1、图论的历史 图论以图为研究对象的数学分支。图论中的图指的是一些点以及连接这些点的线的总体。通常用点代表事物，用连接两点的线代表事物间的关系。图论则是研究事物对象在上述表示法中具有的特征与性质的学科。 在自然界和人类社会的实际生活中，用图形来描述和表示某些事物之间的关系既方便又直观。例如，国家用点表示，有外交关系的国家用线连接代表这两个国家的点，于是世界各国之间的外交关系就被一个图形描述出来了。另外我们常用工艺流程图来描述某项工程中各工序之间的先后关系，用网络图来描述某通讯系统中各通讯站之间信息传递关系，用开关电路图来描述IC中各元件电路导线连接关系等等。 事实上，任何一个包含了某种二元关系的系统都可以用图形来模拟。由于我们感兴趣的是两对象之间是否有某种特定关系，所以图形中两点之间连接与否最重要，而连接线的曲直长短则无关紧要。由此经数学抽象产生了图的概念。研究图的基本概念和性质、图的理论及其应用构成了图论的主要内容。 图论的产生和发展经历了二百多年的历史，大体上可分为三个阶段： 第一阶段是从1736年到19世纪中叶。当时的图论问题是盛行的迷宫问题和游戏问题。最有代表性的工作是著名数学家L.Euler于1736年解决的哥尼斯堡七桥问题(Konigsberg Seven Bridges Problem)。 东普鲁士的哥尼斯堡城(现今是俄罗斯的加里宁格勒，在波罗的海南岸）位于普雷格尔(Pregel)河的两岸，河中有一个岛，于是城市被河的分支和岛分成了四个部分，各部分通过7座桥彼此相通。如同德国其他城市的居民一样，该城的居民喜欢在星期日绕城散步。于是产生了这样一个问题：从四部分陆地任一块出发，按什么样的路线能做到每座桥经过一次且仅一次返回出发点。这就是有名的哥尼斯堡七桥问题。 哥尼斯堡七桥问题看起来不复杂，因此立刻吸引所有人的注意，但是实际上很难解决。 瑞士数学家(Leonhard Euler)在1736年发表的“哥尼斯堡七桥问题”的文章中解决了这个问题。这篇论文被公认为是图论历史上的第一篇论文，Euler也因此被誉为图论之父。 欧拉把七桥问题抽象成数学问题---一笔画问题，并给出一笔画问题的判别准则，从而判定七桥问题不存在解。Euler是这样解决这个问题的：将四块陆地表示成四个点，桥看成是对应结点之间的连线，则哥尼斯堡七桥问题就变成了：从A，B，C，D任一点出发，通过每边一次且仅一次返回原出发点的路线(回路)是否存在？Euler证明这样的回路是不存在的。 第二阶段是从19世纪中叶到1936年。图论主要研究一些游戏问题：迷宫问题、博弈问题、棋盘上马的行走线路问题。一些图论中的著名问题如四色问题(1852年)和Hamilton环游世界问题(1856年)也大量出现。同时出现了以图为工具去解决其它领域中一些问题的成果。1847年德国的克希霍夫(G.R.Kirchoff)将树 数学竞赛中的图论问题 分类号密级 U D C 编号 本科毕业论文(设计) 题目数学竞赛中的图论问题 所在院系数学与数量经济学院 专业名称数学与应用数学 年级 08级 学生姓名李曼 学号 0850410013 指导教师孙静 二 0一二年三月 学位论文原创性声明 本人郑重声明：所呈交的论文是本人在孙静老师的指导下独立进行研究所取得的研究成果. 除了文中特别加以标注引用的内容外，本论文不包含任何其他个人或集体已经发表或撰写的成果作品.本人完全意识到本声明的法律后果由本人承担. 作者： 日期：2012年3月29日 文献综述 一综述 在18世纪30年代，一个非常有趣的问题引起了欧洲数学家的浓厚兴趣，这个问题就是著名的哥尼斯堡七桥问题，即要求遍历哥尼斯堡七桥中的每一座桥恰好一次后回到出发点. 欧拉证明这是不可能完成的. 此后，欧拉发表了著名的论文《依据集合位置的阶梯方法》，这是图论领域的第一篇论文，标志着图论的诞生. 图论的真正发展始于20世纪五六十年代之间，是一门既古老又年轻的学科. 图论极有趣味性，严格来讲，它是组合数学的一个重要分支. 虽然图论只是研究点和线的学科,但是它的应用领域十分广泛，不仅局限于数学和计算机学科，还涵盖了社会学、交通管理等. 总的来说，图论这门科学具有以下特点：（1）图论蕴含了丰富的思想、漂亮的图形和巧妙的证明； （2）涉及的问题多且广泛，问题表明上简单朴素，本质上却十分深刻复杂； （3）解决问题的方法千变万化，非常灵活，常常是一种问题一种解法. 由以上三个特点可以看出，图论与其他的数学分支不同，它不像群论、拓扑等学科那样有一套完整的体系和解决问题的系统. 而且图论所研究的内容非常广泛，如图的连通性、遍历性、图的着色、图的可平面性等等. 二内容 由于图论具有蕴含了丰富的思想、漂亮的图形和巧妙的证明，涉及的问题多且广泛，问题表面上简单朴素，本质上却十分深刻复杂，解决问题的方法千变万化，非常灵活，常常是一种问题一种解法的特点. 随着数学竞赛越来越规范化，并且越来越考察考生的灵活运用知识的能力. 因此近年来，图论问题频繁的出现在数学竞赛中，如典型的一笔画问题、中国邮递员问题、旅游推销员问题、排课表问题等. 离散数学图论部分综合练习 一、单项选择题 1．设图G 的邻接矩阵为 ??? ???? ? ????? ???0101 010******* 11100100110 则G 的边数为( )． A ．6 B ．5 C ．4 D ．3 2．已知图G 的邻接矩阵为 ， 则G 有（ ）． A ．5点，8边 B ．6点，7边 C ．6点，8边 D ．5点，7边 3．设图G ＝ 图三 7．设有向图（a ）、（b ）、（c ）与（d ）如图四所示，则下列结论成立的是 ( )． 图四 A ．（a ）是强连通的 B ．（b ）是强连通的 C ．（c ）是强连通的 D ．（d ）是强连通的 应该填写：D 8．设完全图K n 有n 个结点(n ≥2)，m 条边，当（ ）时，K n 中存在欧拉回路． A ．m 为奇数 B ．n 为偶数 C ．n 为奇数 D ．m 为偶数 9．设G 是连通平面图，有v 个结点，e 条边，r 个面，则r = ( )． A ．e －v ＋2 B ．v ＋e －2 C ．e －v －2 D ．e ＋v ＋2 10．无向图G 存在欧拉通路，当且仅当( )． A ．G 中所有结点的度数全为偶数 B ．G 中至多有两个奇数度结点 C ．G 连通且所有结点的度数全为偶数 D ．G 连通且至多有两个奇数度结点 11．设G 是有n 个结点，m 条边的连通图，必须删去G 的( )条边，才能确定G 的一棵生成树． A ．1m n -+ B ．m n - C ．1m n ++ D ．1n m -+ 12．无向简单图G 是棵树，当且仅当( )． A ．G 连通且边数比结点数少1 B ．G 连通且结点数比边数少1 C ．G 的边数比结点数少1 D ．G 中没有回路． 二、填空题 1．已知图G 中有1个1度结点，2个2度结点，3个3度结点，4个4度结 点，则G 的边数是 ． 2．设给定图G (如图四所示)，则图G 的点割 ο ο ο ο c a b f 图论的发展及其在生活中的应用 数学与应用数学张佳丽 指导教师刘秀丽 摘要主要介绍了图论的起源与发展及其生活中的若干应用，如：渡河问题、旅游推销员问题、最小生成树问题、四色问题、安排问题、中国邮递员问题。同时也涉及到了几种在图论中应用比较广泛的方法，如：最邻近法、求最小生成树的方法、求最优路线的方法等。 关键词图论生活问题应用 Graph Theory Development and the Application in Life Mathematics and applied mathematics Zhang Jiali Tutor Liu Xiuli Abstract This paper mainly introduces the origin and development of graph theory and its several applications in our life, such as: crossing river problem, traveling salesman problem, minimum spanning tree problem, four color problem，arrangement problem，Chinese postman problem．It also researches several methods that are more widely applied in graph theory, for example: the method of most neighboring, the method of solving the minimum spanning tree，the method of the best route，and so on． Key words graph theory life problem application 引言 图论是一门古老的学科，是数学中有广泛应用的一个分支，与其他的数学分支，如群论、矩阵论、概率论、拓扑学、数分析等有着密切的联系．图论中以图为研究对象，图形中我们用点表示对象，两点之间的连线表示对象之间的某种特定的关系．事实上，任何一个包含了二元关系的系统都可以用图论来模拟．而且,图论能把纷杂的信息变的有序、直观、清晰．由于我们感兴趣的是两对象之间是否有某种特定关系，所以图形中两点间连接与否尤为重要，而图形的位置、大小、形状及连接线的曲直长短则无关紧要．图论在自然科学、社会科学等各个领域都有广泛的应用．随着科学的发展，以及生产管理、军事、交通运输等方面提出了大量实际的需要，图论的理论及其应用研究得到飞速发展。从20世纪50年代以后，由于计算机的迅速发展，有力地推动了图论的发展，加速了图论向各个学科的渗透，尤其是网络理论的建立，图论与线性规划、动态规划等优化理论和方法互相渗透。同时，计算机的发展使图论成为数学领域中发展最快的分支 算法图论（Graph Theoretic Algorithms） 第一部分：区间图、弦图、相似图、完美图 本书英文版共29讲，第一部分共12讲，系译者学习的同时为备以后查阅复习之便作的翻译，内容基本忠实于原著，且大部分是直译，同时加入了译者的少许想法，并补上了少部分略去的证明过程（限于译者的水平只能证明一些力所能及的证明）。 第1讲是概论导读；第2到10讲比较详细地介绍了区间图、弦图及其相关的性质、算法（包括证明）以及延伸内容，其中第7到9讲涉及相似图的一些内容，部分定理尚未证明；第11、12讲介绍完美图、相交图及其部分特例，侧重于介绍性，概念结论较多但证明较少，可以作为知识性的阅读。 《尚为解决的问题》是译者翻译学习过程中遇到的一些不懂的问题，原文中未给出详细证明，而译者目前还无法自己证明的，这些在译文中将用粗括号扩出。各路高手如有知道方法的情与译者联系，不胜感激！ 复旦附中葛潇 第一讲、概论 本讲对这门课程的主要议题进行了大致的介绍。 1．概念 这门课程涉及了一些特殊的图以及这些图上某些已经得到改进及仍未解决的问题。 为了解我们所说的内容，我们必须回顾一些特殊图中的概念、算法、复杂度分析及NP —HARD问题。在这门课中对些将不作深入，我们假设读者以对这些有所了解。 2．一些图的分类 下面我们将给出这门课程中将涉及的一些图的形式。在以后的各讲中将进行深入的分析。 z区间图（Interval graphs）：如果一个图能用一些区间的intersection graph表示，那么这个图称为区间图。更准确地说，给定一系列区间，将其中每个区间看作一个顶点，两个顶点间有边，当且仅当这两个点所代表的区间相交。一个图是区间图，当且仅当它能通过以上方法构造出来。（见图1） 图1：一些区间及它们所构成的区间图 我们同时学习各种相关的图，例如弦图和完美图。这部分的主要参考是[Gol80]。 z树（Trees）：一个图是一颗树，当且仅当它是连通的，并且没有环。我们将同样学习有关的图，例如partial k-trees. 这部分的主要参考是[Bod93]。 z平面图（Planar graphs）：一个图如果能画在二维平面上，且各边没有交点，则该图称为平面图。注意每个树都是平面图，但反之却不一定。我们将同样学习有关的图，例如outer-planar graphs 和 series-parallel graphs（混联图）。这部分的主要参考是[NC88]。 本课程中除特别说明，一般所指的图都是简单的、连通的，且至少有两个顶点（或是图有意义的最少顶点）。显然这不会影响大多数算法的适用性。 同时，一般给出的图都是无向图，虽然有时我们为了设计算法人为地加上方向。 3．一些问题 下面是我们将学习的一些问题，以及它们在一些特殊图上的复杂度。 z最大独立集（Maximum Independent Set）：这是著名的NP难题。但在区间图中，最大独立集问题能够在O（N＋M）时间内解决，同时在树上可以在线性时间内解决，但对于平面图这仍是NP难题。 z最大割(Maximum Cut)：图G＝（V，E）上的一个割将该图的顶点分成两个子集：V＝A＋B。更准确地说，给定一种顶点划分，一个割是哪些一个端点在A中，另一个在B 中的边组成的集合。最大割问题是寻找一种顶点划分方式，使得对应割集中的边数最多。 同样也有最小割问题。最小割问题用最大流的方法可以在多项式时间内解决，但最大割问题是NP难题。但在平面图上最大割问题是多项式级的；在树上，最大割问题是平凡 图论实验三个案例 单源最短路径问题 1.1 Dijkstra 算法 Dijkstra 算法是解单源最短路径问题的一个贪心算法。其基本思想是，设置一个顶点集合S 并不断地作贪心选择来扩充这个集合。一个顶点属于集合S 当且仅当从源到该顶点的最短路径长度已知。设v 是图中的一个顶点，记()l v 为顶点 v 到源点v 1的最短距离， ,i j v v V ?∈，若 (,)i j v v E ?，记i v 到j v 的权ij w =∞。 Dijkstra 算法： ① 1{}S v =,1()0l v =；1{}v V v ??-,()l v =∞,1i =,1{}S V v =-； ② S φ=，停止，否则转③； ③ ()min{(),(,)} j l v l v d v v =， j v S ∈，v S ?∈； ④ 存在 1 i v +，使 1()min{()} i l v l v +=，v S ∈； ⑤ 1{} i S S v +=U ， 1{} i S S v +=-，1i i =+，转②； 实际上，Dijkstra 算法也是最优化原理的应用：如果121n n v v v v -L 是从1v 到 n v 的最短路径，则 121 n v v v -L 也必然是从1v 到 1 n v -的最优路径。 在下面的MATLAB 实现代码中，我们用到了距离矩阵，矩阵第i 行第j 行元 素表示顶点i v 到j v 的权ij w ，若i v 到j v 无边，则realmax ij w =，其中realmax 是 MATLAB 常量，表示最大的实数(1.7977e+308)。 function re=Dijkstra(ma)图论算法详解(C++版)
一笔画问题是图论中一个著名的问题
经典图论问题
图论算法及matlab程序的三个案例
图论算法
各种聚类算法的比较
聚类分析法总结
图论问题
maab图论程序算法大全
图论及其算法
聚类比较
图论经典问题
数学竞赛中的图论问题
离散数学图论部分经典精彩试题及问题详解
图论的发展及其在现实生活中的几个应用
算法图论
(完整word版)图论算法及matlab程序的三个案例