（应用数学专业论文）增广立方体的强rabion数.pdf

ab s t r a c t t h e d i 姗 e t e r andc o n n e c t i v itv o f graph s are not o n l yt h e i 价 p o r t ant p aram e t e r s t o m e asu r e t h e c apabi l i tyo f n e two r k s ， b u t al s o t h e fu n d a m e n t al s o f t o p o l o gi c als t r u c t u r e a n da n a 1 y s i s o f i nter c o n - n e c t i o nn e t w o r ks. ma ny o t h e rc o n c e p t si ngrapht h e o ry are e i t h e r b 瞅 d o n t h e m， o r r e l ate dt o t h e m b u t s o m e t i me s ， 1 七 i s n o t eno u g h t o d e s c r i b e t h e c 即a b i l i t y o f n e t w 0 r k s byo n ly u s i n g t h e m s o m a n y m o r e c o m p l e x c o n c e p t s are advan c e d t o d e t e r m i n i n g t h e c a p a b i l i tyo f n e t wor k s m o r e ex朗t l 多t h e fa u l t 一 t o l e r a ntd i ame t er， w i d e- d i a m e t e r ， r abi n n u n 1 b erand s t ron g r abi n nui n b e r o f n e t w o r k s are al s o adv a 11 c ed fo r i t ， t h e yar e ver y u s e fu l t o m e 韶u r e and ana l y z e t h e p e r fo r m a n c e o f r e l i a b i l i t ya n dfa l l t t o l e r a n c e o f n e t w o r k s d e e p i 醉 b u t i t i s gen - e r a l l ys o d i ffic u l t t od e t e r m i n e t h e s e p ar a m e t e r s e x act l 叭e venfo r a c e r t ainn e t w r k t h e hyp e r c u b e i s o n e o f t h e m o s t p o p u 1 a r ， ver s at i l e a n d e ffi c i e nt t o p o l o g i c als t r u c t u r e s o f i n t e r c o n n e c t i o nn e t w 0 r k s . ma n yo t h e r n e t - w o r k s ， s u ch asfo l d e dh y p e r c u b e s ， c r o s s e dc u b e s ， twi s t e dc u b e s a n d m6 b i u s c u b e s ， ar e b ase d o n i t o n l y by add i n g o r c h ang i n g s o m e e d g e s . t h e a u g m e n t e d c u b e i s a l s o o n e o f t h e s e n e t wor k s . l t i s s u g g e s t e d bys ac h o u d u ma n d y . s u n i t h a! 1 1 . i t s d i ame t e r i s al m o s t o n l y h al f asl arg e ast h e d i a m e t e r o f t h e hyp e r c u b e i n t h e s a m e d e gre e ， and i t s c onn e c t i v i tyi s a l m o s t twi ce韶l ar geash y p e r c ube ，5 ， t h e aug m e n t e d c u b eh as t h es a m efi n e s y m m e t r ya n dr e c u r s i o np r o p e r t i e s as t h e 师p e r c u b e . s o we c a nd e t e r m i n e i t s r abi n n u i n b e r ands t r o n g r a b i n n u m b e r b yu s i n gt h e s e i nt h i s p ape r ， m y n u m b e r o f a u g m e n t e d m ai n l yb ase do n et h e 1 2 r e s u l t i s t os h ow t h att h e s t r o n gr abi n lsl 1 l l al n c u b e s r e s ul t s i si t sd i a m 眺 e radd i n go n e ， w h i c h o fs ， ac h o u d u m a n dvs u n i t h a l v 中国科学技术大学学位论文相关声明 本人声明所呈交的学位论文， 是本人在导师指导下进行研究 工作所取得的成果。 除己特别加以标注和致谢的地方外， 论文中 不包含任何他人 已经发表或撰写过的研究成果。 与我一同工作的 同志对本研究所做的贡献均已在论文中作了明确的说明。 本人授权中国科学技术大学拥有学位论文的部分使用权， 即: 学校有权按有关规定向国家有关部门或机构送交论文的复印 件和电子版， 允许论文被查阅和借阅， 可以将学位论文编入有关 数据库进行检索，可以采用影印、缩印或扫描等复制手段保存、 汇编学位论文。 保密的学位论文在解密后也遵守此规定。 作者签名: 年月日 第一章引言 现今高性能计算技术在国内 外受到高 度的重视， 它在科学 研究， 工程技术以 及 军事等方面的 应用， 己 取得了巨 大的成就， 国际 上科学家普遍认为， 没有万亿次以 上的高性能 计算. 21 世纪 人类 所面临的 基因 工 程， 全球气候准 确预 报， 海洋环流 循 环 等“ 巨 大挑战” 问 题 g r a n d ch成 喻ge ) 是 无法 解决的 现代高 性能 计算厂 月 尸 c)是 指能在互连网络上进行并行数据处理和数值模拟的大规模运算. 这里所说的互连 网 络介 耐 e 二。 n ec tio。 配 细 。 叫并 不 是 通 常 意 义 下的i nt er ne t ， 而 是 泛 指 一 些 运 算 节 点 通过通讯 信道( 包 括有 线的 和无线的 ) 按照 一定的 方式 相互 连接而构成的 系 统 这 些运算节点可以 是 计算 机子网 络， 计 算机， 计 算机内 部的 处 理器， 存储器， 通 信 设 备， 其他元件或设 备 等 这 种互连网 络与 传统的 大型计算 机相比 具有更高的 性 能价格比， 在近年来已 经引 起了 很大的研究关注 很多这方面的系统己经被实现 随 着技术的不断 提高， 可以 制造 更高 运算峰值的 超级计算 机， 但是现有的 超级 计算机的实际使用效率并不令人满意， 这个问 题要靠优化高性能 计算机的系统结 构， 软件和大规模并行算法和它们之间的密切匹配来解决. 互连网络节点之间具有较多的消息传递， 它们之间的连接方式是决定网络性 能和价格比的一个主 要因素， 因 此研究网 络组件之间的连接方式显得尤为重要. 网 络中 节点之间的 连接 方式 称为该网 络的 拓扑结构(t 叩 01 09 乞 ca l 就 。 d 二 ， 5) ， 网 络的 拓扑结构是设计计算机互 连网 络的 第一步， 也是实现各种协议的基 础， 它对网 络的 性能， 系统可靠性和费 用都 有重大影响. 在分析网 络拓扑结 构时， 人们通常 把网 络中 运算节点 抽象成一 个点， 把通信 信道抽象成两点 之间 的 连线， 那么该网 络的拓扑结构 就被抽象成一 个图. 研究网 络的拓扑结构问 题就归 结为 研究图的结构问 题. 换句话说 ， 图是网 络结构的数学模 型， 图 论就成为设计和分析互连网络的重要工具. 互连网络的可靠性是评 估网络性能的重要概念， 高可靠性的互连网络一直是 网 络设计者追求的 重要目 标之 一 然而， 可靠性是一 个非 常抽象的 概念， 我们只 从 网 络的 拓扑结构上考虑硬 件故障 对网络可靠性的影响， 即 在网 络结点 和( 或) 连线 中国科学技术大学硕士学位论文 可能发 生故障的 情况下的 数据传输可 靠性， 在这种意义下， 对于一个给定的互 连网 络， 最多 能 容忍多 少 个结 点 和( 或) 连线同 时 发生 故障， 而 剩 余的 子网 络中 每个结点 之间 还 仍 能 继 续保持 通信. 为区 别其 他 含义可 靠 性， 文 献上习 惯 称这 种可 靠性为 容 错性(fa毗tole rance) . 网 络容错性的实 质是当 故 障发生时 ， 剩余网 络的 重组能 力 网 络容 错性有多个方面的 含义， 不同 的 含义有 不同的 度量. 从网 络拓扑结 构的 观 点 这 些 度 量 可 分为 随 机 性 度量净 二 吞 ab 该 肠 讹。 ea s . 理 夕 和 确 定 性 度 童似 酥 e 、tic 。 ea 。 叼两种 可靠 性的 概率性度量是最符 合客 观实际的， 然而己 经 证明 ， 各 种具 有实际意义的概率性度量在其计算复杂性上都是n p 一 h ar d 的， 因而各种各样的多 项式近似算法是重要的. 我们所研究的确定性度量是指网络中至少需要多少数目 的结点 和( 或) 边同时 发生故障 刁导致网 络瘫 痪; 这 个数目 越大， 网络的容错性 越 大， 度量网络可靠性的参数有很多， 连通度与 直径是其中最重要的两个， 一个好的 网 络要求连通度尽可能的大， 这才能使容许的出 错点 集尽可能多; 而同时 又要求直 径尽可能的短， 这样数据传输的才会快. 但随着计算机技术的发展， 网 络结构越来 越复杂， 要求越来越多， 是在许多时候， 仅 仅单以 连通度与直径来考查网 络的性能 是不足够的， 为此人们提出了许多更复杂的 概念去更精确地度量网络的性能. 容错 直径， 宽直径， rab in 数， 强rahi n 数等都是为了 这种原因而被提出的. 它们都是针 对网络性能分析某一方面的要求而提出的， 对近一步分析度量网络的容错性及可 靠性有很大帮助. 迄今为 止， 国 际 上已 经提出了 许多种互 连网 络， 其中 超立方 体网 络的 总体 性 质 是 较 好的 ， 如 它 具 有 对 数 级 的 直 径 和 最高 连 通 度( 从 而 也 具 有 最高 容 错 度 ) 以 及正 则 性 等 等， 特 别 是liv讯 罗 t on和s to u t1 司证明 了 每 个图 都 可以 嵌 入 超立 方 体网 络. 因而也研制出了 多种超 立方体型并行机， 如 c o slnicc u be， i nt elip s c， a m t e k ，5 s y s t e m / 1 4 ， n c u b e / 1 0 ， c al t e c h / j p l m ar k l l l 和c o n n e c t i onm a c ll i ne. 而 这些 并行机的研制和使用又引 起了 人们对超立方体网 络深入研究的 兴趣. 但是， 超立方 体网 络并非各方面性质都是最好的， 于是超立 方体网络的 变形: 折叠立方体网 络， 交叉立方体网 络等被提出 来研究， 它们的直径都大约是超立方体网 络的 一半增广 立方体( a u 脚e n t e d c u b e 。 ) 也是其中 之一， 它是由5 大，c h o u d u m和v 名 u n i t h a 在2 0 0 0 3 年提出的. 增广立方体不仅保留了立方体网络的递归结构好的特点而且直径只是 相同 规模的立方体网 络的 大约一半且连通 度接近其两 倍， 所以 有很好的 应用前景 本文共分四章， 第一章是引言， 第二章是预 备知识包括基本图论术语和连通 度， 容 错直径， 宽 直径， r a b i n 数等概念的 介绍， 以 及网 络设计的 基本原 则的说 明 . 第三章是超立方体网络与增广立方体网络的概念与已知结果， 主要包括超立方体 网 络与增广立方体网 络的 概念与基 本性质的 介绍 ， 与前人已 经取得的一 些有 用的 已 知结果. 第四章是增广立方体网络的 强r a b in数研究， 也是本文的主要部分， 主 要是在s a . c h o u dum和v s u ni th a 研究结果的基础上， 进一步确定增广立方体网 络的r a b i n 数与强r 远 b i n 数为其直径加一 第二章预备知识 卯. 1 图论术语的介绍 本节简单介绍图的基本概念和在以后的讨论中要用到的记号. 所谓图 匆 哪习 是 指 有 序 三 元组( 认e ， 哟， 其中v 非 空 称为 顶点集扣 e rt ex-se 认 e称为边集r 司 夕 e 一 se t) ， 而劝 是e 到v中 元素 有序对或无 序对簇v、 v的函 数， 称 为 关 联函 数斤 二 : d o t 加 二 tio司 . v 中 元 素 称 为 顶 点和 e 材 。 x) ， e中 元素 称 为 边介 d 夕 e)， 劝 刻划了 边与顶点之间 的 关联关系. 若vxv中 元素全是有序对， 则( 矶e ， 哟称 为 有向图 阿 乞 ， ct “9 哪习 若v、 v 中 元 素 全 是 无 序 对 ， 则( 认 e ， 哟称 为 无向 图 和 n d 乞 。 c t o d 夕 呷h) 我 们 把e中 的 元素。 直 接 表 示 成v x v中 的 元 素( 二 ， 刃 ， 记。 =(x ， 功= 却. 此 时 ， 边 与 顶 点 之间 的 关 联 关 系己 明 确 ， 则 可 简 记( v，e ， 哟二( 认e ) . 两 顶 点x 与岁 称 为 边x 夕 的 两 个端点(e 耐一 ve 币ce 习 ，边与 它的 两端点 称为 关 联的介 nc : d 即 t) ， 与同 一 条边关联的两 端点或者与同一 个顶点关联的两条边称为 相部的(a 心 ac 即 妙 . 两 端点 相同的 边称为环(loor).具有 相同 的 两 个端点的 两条 边称为 平 行边净 a 二 lle l e 匆 es) 或重边伽。 lti 一 edges).无环并且无平行边的图 称为简 单图脚呷leg ” 切 尽 设( 认e ) 是图 ， v中 元素的 个 数v 和e 中 元素的 个数: ， 即。 =!vl和: 二ie ， 分别 称 为 该图 的 顶 点 数或阶(o 记 e 刁 和 边 数(si z e) . 。 和: 都 是 有限 的 图 称为 有限图 伽 te 9 仰h) . 如不 加特殊说 明 ， 本文以 下 所涉及的图 均为 有限 简单无向图 . 顶点xv ( c ) 的 邻点 集记 为凡( 幻 顶点二 的 顶点 度和 。 代 二d 匆 化 e) 定 义 为g 中 与x 关 联的 边的 数目 ， 记 为心( 司 对 简 单图 有心( x)=!凡( x) l . 图g 最 小的 顶点 度， 记为截 c ) ， 最 大的 顶点 度 ， 记为 ( g).如 果 对g 的 每 个顶点x 均 有心( x)=k ， 我 们 称g 是 k 正 则的降 一 卿侧 州 任何不同 两顶点之间 都有边相连的 简单无向图 称为完 全图(co呷l et 。 夕 ，树 声h)， n 阶完 全图记为凡 若无环图的顶点集可以 划分为两个非空子集x和y ， 使得x中 任 何两顶点之间无边相连并且y中 任何两顶点之间也 无边相连， 则称该图为螂 分 虽 2 . 1图 论术 语的 介绍 图 必 zpa成 teg m p 习 ， x ， 玛称 为 螂划 分净 ， a 爪 tio司 . 二 部 划 分 为 x ， y 的 2 部 分图 可 记 为( xuy， e ) . 任两点 若同 属 于x 或y 则 称为同色 点 ， 否 则 称为 异色 点 若x中 每个顶点 和y中 每个顶点之间 均有边相连， 则称该2 部分图为完全脚分 图 (co仰let 。 吞 勿 a 成teg 卿h) ， 记 为呱产 ， 其中!x l = 二和 州= n. 设x 和夕 是图g 中 两 顶点， 连接x 和夕 长 度为k 的 路净 a tn)， 记为卸路， 是 指 顶 点二 和 边ej 交 错出 现的 序 列尸 = 瓶( = x) 价 ， 从 两: 气众 。 ( 二 约 . 其 中 与 边ei，相 邻 的 两 顶 点 及 ， 一 ， 和气恰 好 是气的 两 个 端 点 ， 且 除 点 x 和y 外 ， 其 余 的 顶 点 互 不 相 同 . 有 时 我 们 简记踢 =x 众 : 一xt 卜 ， 夕 . x 和， 称为尸 的 端 点(e 。 d 一 ve 瓜ce s) ， 其 余 的 顶点 称为内 部点介 。 te 二al。 瓜ce s) . 尸中 边的 数目无 称为尸 的 长度. 两个端点 相 同的 路 称为圈(c 那 le) 包含图中 所有 顶点的路 称为hao ilt o ， 璐协 a m lto瓜 an那th) . 包含图 中 所有顶点 的圈 称为ham “ t on圈 协 a 。 艺 lt on乞 叭印 cl e) . 图g中最短圈的 长 度称为c的围 长向 i r t h 夕 ， 记为9 ( g ) . 图g中 两项 点x 和岁 之间的 最短路的 长 度称 为两点间的 距离 (dist 叨c e) ， 记为壳(x ， 功 ， 当 图g明 确时， 简记为d( x ， 功 . 图g中 任意 两 顶点x 和夕 之间的 距离的 最大 值， 称为图g 的 直径(dia 仇 et e 刁 ， 记为武 g ) . 设c=( v ( g ) ， e ( g ) ， 功 。 ) 和h=( v ( h ) ， e ( h ) ， 沪 ， ) 是两个图 .若v ( h ) 二 v(g)， 侧h ) 9侧g)， 并且沪 二 是价 。 在e ( h ) 上的 限 制， 则 称h是g 的子图 介 。 匆 呷习 ， 记为h二g . 称g是h的 母图介 即e 印 哪习 . 若hgc 并且v ( h ) 二v ( g)， 则 称h是 g的 支 撑子图(sran瓜 仰翎 如 仰h) 图 中 的 路 和圈 是该图 的 子图， 而h amil to n 路和h amilt oll 圈 是图 的 支撑子图 . 若h互g 并且v ( h ) 尹v(g)， 则称h是g 的 真 子 图 净 卿 夕 已 : 韶 匆 哪习 ， 记 为hc 已 设vi是v ( c ) 的 非空真子集， 以v为顶点 集， 并以g中 两端点均在vi中的 边为边 集， 所得到的子图 称为g的由vi导出 的 子图 ， 简称导出 子图介 ， 血喇 ， 幼 - 9 哪叼 ， 记 为c 【切 ， 导 出 子图c v vl 记 为c 一 vl . 若v= 对， 则 简 记c 一 好 为口一工 设ei是e ( c ) 的非 空 子集， 以刀为 边集， 并以c中由e，中 的 边的 端点 为 顶点 集 ， 所 得 到 的 子图 称 为g 的 由ei导出 的 子图 ， 记 为侧 e， 由e 刀导出 的 子 图 记 为g一 ei. 若e= e ， 则简 记c一 e为c一 。 中国科学技术大学硕士学位论文 设g l g g ， c : gg ， 若v ( c l ) n v ( c z ) 二必 ， 则 称c ; 和g : 是 点 不 交 的向 e 代 。 成 习 口 讯 t);若e ( g ， ) n e ( g 习二 必 ， 则 称口 1 和g : 是 边 不 交 的了 已 d 夕 e 一 d 勿 口 讯 t) c ; 和g : 的 并扭 瓜 0 川 ( 记 为c i u 2 ) 是 指图h ， 其中v ( h ) =v ( g l ) u v ( g : ) ， e ( h ) =e ( g ; ) ue ( g z ) .设e 中 各边端点 集为v ( ei) 并且有v ( e ， ) gv ( g l ) ， 则g ; +e是子图h ， 其中v ( h ) =v ( g i ) 且e ( h ) =e ( c ， ) ue . 若e = e ， 则简记c : +e为c l +已 对于两个图g和h如果存在一个双射 夕 : v ( g ) *v ( h ) ， 使 得( x 山 ) 任 e ( g ) ( 口 ( x ) ， 夕 ( ， ) ) e ( h ) 那么 称图g 和h是同 构的(i 50 。 口 ， 从 c) ， 记为c令h ， 并 称夕 为图c 和h的一 个 同 构 映 射介 50 二 口 印 从 c o app二 刃 .如果g=h ， 则 称。 为 图g 的 一 个自 同 构 映 封(a 耐 口 。 0 ， h 留 二二 卿i na)，图g 的 所 有自 同 构 构 成的 群 ， 称为 图g 的自 同 构 群(a 砚 口 。 。 印 从 5 二9 。 呵， 记 为a 叫g ) . 图g 称 为 点 可迁 的扣 e 代 ex-恤二 衬 二 e) ， 如 果 对 于 任 意的 两 点x ， ， c v ( g ) ， 存 在 图c 的自 同 构0 ， 使0 ( x)=夕 . 图g称为边 可迁的厂 政 才 夕 e 一 枷二 乞 枷习 ， 如果 对于任意 的 两 条 边e ; 二 tlv， e z = xy e ( g)， 有c 的 一 个自 同 构。 ， 使 得夕 ( 。 ， v ) =x ， 好 即将边e : 映到边勺. 设mce ( g ) ， 如果m中 任意两 边在图g中 是不相 邻的 ， 则m称为图g的 一 个匹 配 伽at ch no). 如 果图 g 的 匹 配m的 端 点 集 等 于v ( g)， 则m称为 图c 的 完 备匹 配伽 e 价c t 一 7n a thtno). 可 迁图 是一类重要的图， 它具有高度的 对称性， 是比 较理想的高 性能 超大规模 计 算 机系统互连网 络的 拓扑 结 构 这里我们介绍 构造 一类重要可迁图 一c ay l ey图 的 方法. 因为 构造涉及到群论的 概念， 因而被称为代数方法. 设r 是一非平凡有限 群， 5 是r 的不包含单位元e 的非空子集 定义一个有向 图g如下: v ( c ) =r ; ( x ， 夕 ) 任 e ( g ) 骨x 一 ， 夕 5 ， 对于任意二 ， ， 任 r 妙2 网 络设 计的 基本原则 如 上 定 义的 有向 图 ， 是由 英 国 数 学 家 c aylcy! 15 首 先 提出 ， 所以 一 般 教 科 书 和 文 献 都 称它为 群r 关于 子 集5 的 c ay l叮图， 记为cr( 5)或c 叼( r ， 5). 当5 一 ， =5 时 ， 群r 关于 子 集5 的 c ay l ey图cr( 匀是 对称有向 图 ， 它 可以 看成 是无向图. c ayley 图 有许多 好的 性质， 一个最明 显的 性质就是c 即 1 吧 y 图 是点 可 迁的 . 互 2 . 2 网络设计的基本原则 互连网络拓扑的 选择不 但要 考虑系统的 性能， 更要考虑系统的 制造 成本r 高 性能 低成本始终是网 络设计者所追求的日 标. 下面我们列出 衡量计算机互连网络 系统的高性能低成本的一些参数和设计这些网络时所遵循的原则 这些原则往往 是互相冲突的. 所以设计者需要在性能和造价之间找到一个满意的解. 因为网络 拓扑结构可以用图来建模， 下面我们用一些图论的术语来描述这些基本的设计原 则0. 1 、 小的或者固定的度 即对应的图的顶点的最大度受到某个常数的限制. 顶点的度对应于单元的可 供使用的输入输出端口 的数目 . 每个单元的物理连接应受限于该单元的端口 数目 . 小 顶点 度意味着少的 物理连接， 可以 降 低网络的 构建成本. 2 、 小的通信传输延迟 网 络中 任何一 个点的 信息 传递到另 外一个点 所费 的时间要尽可能的 少 ， 即 对 应的图应该具有较小的直径或者平均距离. 小的传输延迟不仅能降低网络的建造 和维护费 用， 而且能 确保网络的有效性 3 、 简单的路由算法 路由选择是互连网络的最主要的功能之一 路由选择的优劣深刻影响着网 络 的 性能 和效率. 因而 互 连网 络有好的 ， 简单的， 有效的 路由 算法 对于网 络的 选择 是 很重要的事情， 中国科学技术大学硕士学位论文 4 、 高对称性 人们希望网络中的各单元都以相同的方式启动和连接， 使得各个节点的容量 和连线的负载保持均衡 这就要求对应的图应具有某些对应性， 看是否是点对称 的， 边对称的. 最好能是c ayl ey图， 5 、 较高的容错性 网 络应有一定的 容错性， 即 容许网 络中 有若干数目 的点或者边发生故障. 我 们要求， 当 故障节点或者连线的总数不超过某一固定的 值时， 剩余的网 络的 性能 没 有大的退化. 6 、 可扩展性 设计出的网络要容易扩展. 使得网络可以由 较小的规模改造成较大规模的网 络， 而仍然保持网络的拓扑结构. 7 、 可嵌入性 通常 人们 对已 经 存在的一些简单网 络比 较熟悉 ， 并且己 经掌 握了 在这些网 络 上设计的一些算法. 所以当设计一个新的网络拓扑结构时， 要求能够将一些简单 的网络嵌入到所设计的网络中. 8 、 有效的布图算法 布图设计涉及到图的 可平面性问 题. 如果这个图是 平面图， 布图 设计实际 上是 找出 该平面图的实 现方 法. 如果该图 不是 平面图 ， 则要么 把该图 分解成若干 各子 平面图并找出 该图的厚度; 要么求出 该图的交叉数. 布图问 题是一个n p 一 h ar d 问 题， 但对于具体的 互连网 络来说， 布图问 题的 有效算法是可能 存在的. 愁 2 .3 m e n g e r 定理与 直径概念的推广 9 2 3 . i me n g e r 定理与 连 通度 m en ge r 定 理 ( 见v ) 是图 的 连 通 度 理 论中 的 重 要结 论 ， 它的内 容 如下 . 卯.3 m侣 n g e r 定理与直 径 概念的 推广 设二 与夕 是图g 中 两 个不同 的 点 ， g 中 内 点 不 交的(x ， y ) 路的 最大 条 数 ， 称为 图 g 的m e o 9 ，数 记 为 劝 (x ， 功 . g 中 边 不 交 的(x ， y ) 路 的 最 大 条 数 ， 称 为 图 g 边 形 式的me 叼e : 数 ， 记为初(x ， 功 . 若 存 在 一 个非空 子 集5二v ( g ) 、 x ， 好 使 得g 一 5 中 不 存 在(x ， y ) 路， 则 称5 为g 中(x ， y ) 分离 集( s ep ar at i ngs et ) ， 具 有 最小 点 数的(x ， y ) 分离 集 称为 最小(x ， y ) 分 离 集 . 其顶 点 数记 为 以 x ， 功 . 若 存 在 一 个 非 空 子 集b二e ( c)使 得g一 b 中 不 存 在(x ， y ) 路 ， 则 称b 为g 中(x ， y ) 截 集(c ut se t) ， 具 有 最小 边 数的(x ， y ) 截 集 称 为 最 小(x ， y ) 截 集. 其 边 数 记为人 试 二 ， 功 叙 述上述四 个参 数之间 关系的 是著 名的m en g er定理， 它 是互连网 络拓扑 结 构 设计和可靠性， 容错性分析的基础， 定理 2. 3 1了 五 了 七 n ge r 定理 堆 x 与夕 是图c 中 两 个不同 的 点， 则: 夕 ) 肥( x ， 夕 ) =人 。 ( x ， 夕 ) 厂 阳 夕 记 ( 二 ， 约=甸( 二 ， 功 ， 如果(x ， 功不 属于e ( g ) ， m e nger定理是图 论中 运用的 最多的基本结果 它深刻揭示了图的结构 特征， 是图 论中 关于连通度理 论的 核心， 因 而也 是 互连网 络拓扑结构分析的 基础， 特别 是 在并行互连网络的设计， 研究和分析中的作用越来越大. 图g 称为连通的 ， 指对图g 任意中 两 个不同 的 点x 与叭图g中 都存在连 接x 与y 的 路 图的连通 性是图 论中的一 个重要 概念， 也是衡量一 个网 络畅通与 否的 一 个 基 本 要求. 设 图g 为 连 通的 ， 若 存 在非 空 集5 v ( g ) 使 得c一 5 不 连 通 ， 则 称5 为g的分离集. 具有最小点数的分离集称为最小分离集， 记为、 分离集 最小 分 离 集中 的 顶点 数 记 为以 c ) ， 它定 义 为图g 的 连 通 度. 若 存 在非 空 集bce ( 切使 得g一b 不连通， 则 称b 为g 的截集.具有最小点数的截集称为最小 截集， 记 为入 截 集 . 最小截 集中 的 边数 记 为从 句， 它 定 义 为图g 的 边连 通 度. 如果减g ) 2。 ， 则 称图g为、 连通的 ， 如果( 仍 全。 ， 则 称图g 为。 边连 通 的 所有的非平凡连通图都是1 连通且1 边连通的， 而。 阶完全图的连通度为。 一1 . 关于图 的连通 度与 边连通 度， 有以 下两 个著 名的 定理( 见日 ) . 定 理 2 . 3 .zf 琳耐 ne 夕 不 等 式 少 对 任 何 连 通图民有 : 1 三以 c)三从 必三 叔 g) 中国科学技术大学硕士学位论文 定理2. 3. 3 ， ( ” 几 刀 t 、州别准则 夕 设。 全1 ， 并 设0 是以 2 。 +1)阶图 ， 则 : (1 ) 、 ( c ) 2。阅片 今亿( x ， 夕 ) 全 、 ， vx， 夕 任 v ( g ) ， (e)久 ( g ) 2。幸月 ， 肋( x ， ， ) 2。 ， 比， ， 任 v ( g ) ， 图的连通度的网络应用是很明显的. 若图的连通度为。 ， 则表明其对应的网 络可以 容纳最多。一1 个点同时发生故障而不会使剩余子网络中各结点之间通信 中断， 这对边连通度也一 样 因此， 连通度常被视为互连网 络可靠性与容错性的一 个重要度量 由 wint n e y 不等式可知， 图的 最大连通度与 边连通度可能是图的 最小 度占 ， 因此寻找能使其相等的条件是一 个十分重要的问 题， 目 前这种条件也已 经找 到了许多. 连通度不单是度量网 络性能的重要参数之一， 更是互连网 络拓扑结构分析的 基 础， 许多 更 精确度量网 络 性能的 概 念都是建立 在 连通 度的 基 础上， 或与 连通 度 有 密切关系. 互 2. 3 .2 容错直径 我们知道， 互连网络的 数据传输延迟可以 用其对应的拓扑结构图的直径衡量. 直 径大的网 络有很大的 传输延迟， 因 而 传输效率 差. 而 在容错网 络中 ， 结点的 失 灵 会导致数据传输延迟的 增加， 因此仅采用直径来度量数据传输延迟是不准确的， 而 且结点的失灵是随机的， 事先并不知道， 为了 准确度量容错网 络的 数据传输延迟， 需要另一个概念， 容错直径. 设g 是 连 通图 ， f 是v(g ) 的 子 集， 称 为g 的 点 故 障 集. x 与y 是 g 一 尸 的 两 个 不同 顶点， 则从x 到y 的( 。 一1)点 容错距离( ve rt exfa 几 i l t- to lerant d 运 t ance ) ， 简 称 容 错 距离 ， 记为几( g;x ， 功 ， 定 义为: 几( ex ， 约= m ax 心一 尸 (x ， 刃: fcv(c)， 尸 讨. 由 容 错 距 离的 定义 知 ， 使 得几( 民x ， 的= co的 点 故 障 集f 中 的 元 素 个 数fi最 小 值为 g ( x ， 夕 ) ， 由 m e n g e r 定 理知， 图 g 的( 。 一 1 ) 容错直 径( vert e x 几(c; x ， 刃是 有限的当 且仅当。三、 试 二 ， 好 免 u lt t o ler an t d ia m e t e r ) ， 记 为几( ) ， 定 义 为 : 互 2 3m e nger 定理与 直径概念的 推 广 几( g ) 二m ax d( g一尸 ) : fcv ( g ) ， f 。 . 由m e n g er定 理 与wint n ey判 别 准则可 知， 几( c ) 是 有限 的当 且 仅当g是。 连 通的 而当 故 障 集f=必 时 ， 有d i ( c ) =d( g ) . 因 此 容 错 直 径的 概 念 是 经典 直 径 与 连 通度 概念的 结 合与 推广. 易知， 如几( g ) 是 有限 值， 则: 几( g ) 二 m ax d ( g一 f ) : fcv ( g 川f = 。 一1 ， 且: 几( g ) 2几一 1 ( g ) 全， 二全d z ( g ) 全d ; ( g ) =d ( g ) . 容 错 直 径的 术 语 由k r 运 hnamo ort冲与k rish nam u r t 勿( 1 9 8 7 ) 首 先 提出 ， 无 疑 用它来度量容错网 络的 数据传输延迟是恰当的. 容错直径与直径的差距可能很大， 也可能 相等. 理想的 清况是其差尽可能小， 尤其对实时网 络而言更是如此. 但从广 义上 做到这一点是十分困 难的， 不过对一些具体网络的 容错直径己 有了 准确的结 果. 9 2. 3. 3 宽直径 在并行计算系统的网络中， 信息是通过若干条内点不交的路径平行的进行传 播. 于是， 对于这样的网 络， 仅仅孤立地考虑连通度与直径是不够的 这是因为网 络即使有大的连通度与小的 直径， 但通过网 络中 若干条内 点不交的 路并行传输信 息时， 其中 某些路可能很长， 因而传输延迟大， 从而影响 整个系统的 有效性. 因 此 在并行计算系统的网 络中， 只用连通度与直径甚至是容错直径作为网络可靠性与 有效 性的 度量显然是不合适的 ， 而必须将连通度与直径结合起来考虑， 由 此就有了 宽直径的概念. 设g 是。 连通图 ， x 与y 是g中 两个不同的 顶点.由m e nger定理知， g中 存 在。 条内 点不 交 的(x ， 约路. g 中。 条内 点 不 交的 (x ， 功 路 集尸二 pi， 几， 二 ， 几 称 为g 中 一 个宽 度 为 。 的 (x ， 功路 系 ， 简 称。 一 ( x ， 功路 系 ， 亦 称。 一 c ， t 面 。 ， . l( 尸 ) = pi卜 几卜 . ， 十 凡 称为p 的 路长 和， 而p 中 的 最大路长记为d( 尸 ) ， 即: 己 ( 尸 ) = m 。 pl， 1几 ， .， 凡 g中 所 有的。 一 ( x ， 功路 系的 集 记 为儿( g;二 ， 功 . 具有 最 小 路 长 和的。 一 (x ， 约路 系 称为 最 小、一(x ， 功路系. 中国科学技术大学硕士学位论文 设0 是。 连通图 ， x 与y 是g 中 两个不同的 顶点， g中 从x 到y 宽 度为。 的 距 离， 记为内( 倪x ， 功， 定义为: 心( g ; x ， v ) =m i n d ( p ) : p任儿( c ; x ， 刀 ) 即心( g ; x ， 功是 最小的正 整数d 使 得g中 存 在。 条内 点 不交 且 长度不 超过d 的 ( : ， 刃 路. 进一步说 ， g中 宽 度为。 的 直 径， 简 称。 宽 直 径( 。 一 di alnet er) ， 记为心( c ) ， 定 义为: 心( g ) =m ax 心( g ; x ， ， ) : vx， ， v ( c ) . 即心( g ) 是最小的正 整数d 使得 对g中 任何两顶点x 与叭g中 都存 在。 条内 点 不 交且长 度不 超过d 的( 二 ， 的 路. 由 定 义可 知， d ， ( g)=d g ) ， 而且: 心( g ) 全 心一 : ( g ) 全全 dz( g ) 全d l ( g ) =d ( g ) . 宽 直 径心( g ) 是将连 通度与直径结 合起来考 虑的结果， 对一个好的 并行计算 系统的网 络， 显然是要求连通度尽可能大而宽直径尽可能小， 因此， 宽直径能度 量网络的 容错 度与传输 效 率. 所以 当、 固 定时 ， 确定心( c ) 的 值非常重要. 但是对 广义来说， 这是一个n p c 问题， 不过对一些具体网络已 有了 准确的结果. 宽直径 一词是由h su和ly u u 1 6 1 在路系的概念上提出 来的 ， 而 。一成 。et 。则最早见 于fl andr in 和h l l 7 的 一 篇 报 告中 . 互 2 . 3 4 b a b i n 数与强r abi n 数 设g 是。 连通图 ， x 是g中 任意一 个顶点， y= ， 1 ， 脚 ， ， 如 是g一 二 中 任 意k 个 不同 的 顶点 组 成的 集 . 由m e nger 定 理 知， g 中 存 在。 条内 点 不 交的(x ， 从 ) 路 只 ， f =1 ， 2 . ， 。 . 我 们 称 路 集凡(x ， 均= pi， 几 ， 二， 凡 为g 中 的 一 个 (x ， 均扇. (x ， y ) 扇是图 论中 的 一 个重 要 概念 ， 它 对 分 析图 的 连通 性 或网 络的 可 靠 性 与 有效性有重要作用. 如在并行系统的网络中， 数据沿着给定的路由 选择将数据包 从 源点x 送到目 的点叭很 有可能会造成 超载或拥塞. 为了 减少这种情况的 发生， v 日 j i ant ! 18 曾 提出 过一 个 快 速传送方 法: 首 先 将 数据包分 成。 块， ( 如 果 该网 络 是。 连 通的 ) 然 后 ， 随 机的 选 取。 个中 间 结 点 集y二 夕 1 ， 功 ， 二 ， 如 ， 构 造(x ， y ) 扇 凡(x ， 均= pi， 几， ， 几 与( y，约扇凡( 丫功= q l ， q z ， . 二 ， q 。 最后， 将。 个 互 2 3 menger 定理与 直径概 念的 推 广 数 据块分别 沿路 径只传送给结点从 ， 再 沿 路径q ; 传给犷为了 使结点 x 的 数据在 指 定 的 时 间 内 传 到 结 点 y，(x ， y ) 扇 与( 丫 功扇 中 的 路 长 必 须 有 个 限 制 r abin 【 1 例 在 考 虑 随 机 路由 选 择 算 法时 ， 首 先 提出 考 虑( 二 ， y ) 扇的 路 长， 并 给 出了 一 个度量路由 选择算法 优劣的 参数， 这就是 后 来被h su!2 0 称为的r a b i n 数. 设g 是。 连通图 ， g 的r 几 b i n 数， 记 为几( g ) ， 是 一个最小的 正 整数k ， 使得 对g中 任意一个顶点x 和g一x 中 任意。 个不同 的 顶点组成的 集y ， g 中 存在一 个(x ， y ) 扇凡(x ， y ) 使得其中 所有路的 长三无 由 定 义 ， 显 然 有r 、 ( g ) =己 ( ) ， 而 且当 。三 ( ) ， 由材 e 。 夕 e r 定 理 知几 ( g ) 有 一个确定值. 而且有: 几( c ) 全几 一 ; ( c ) 全二全几 ( c ) 全r l ( c ) =或 c ) . 我们想要知道的 是， 对于一个任给的图g ， 与正 整数k 与。 ， 如何确定几( g ) 三无 但h su与ly u u20 己 证明， 这 是一 个n p c 问 题， 不过对一些具体网 络也己 有了 准 确的结果. 另一个我们所要关心的是上述三个参数之间的大小关系， 对此有不少结果， 最 重要的 是下面两 个( 见e ) . 定理2. 3. 4 . 设c 是。 连 通图 ， 则 有: 几( c)三 几( c)， 定理2 . 3 . 5 . 设 是。 连 通图 ， 则 有: 几( g ) 三心( c ) 兰与( g ) +1 . 出 于 技 术上 的 需 要 ， li aw和c h a n g l 将r ab in数 的 概 念 作了 推 广 ， 设g 是。 连 通图 ， g 的 强r ab in 数 ， 记为吃 ( g ) ， 是 一 个 最小的 正 整数k ， 使得对g中 任意 一 个 顶 点x 和c一 x 中 任 意。 个 顶点 ( 可以 有 相同 的 ) 组 成的 复 合 集y ， g 中 存 在一 个(x ， y)扇凡(x ， 均使得其中 所有路的 长三丸 由 定 义， 显 然 有 ( c ) =d ( c ) ， 而 且 当。兰、 ( ) ， 由材e o g e r 定 理 知几 ( c ) 有 一个确定值， 而且有: 定 理2. 3. 6自 夕 几( g ) 全吃 _ 1 ( g ) 全，