当前位置：文档之家 › 关于3连通图的容错直径和宽直径的一个新结果

关于3连通图的容错直径和宽直径的一个新结果

  • 格式：pdf
  • 大小：121.49 KB
  • 文档页数：3

在 并行 计算 系 统 的 网络 中 ， 信息 是通 过若 干 条 内点 不交 的路径 并 行 地 进 行传 输 ， 于是 仅 孤立
地 考虑 连通 度和直 径 是 不 够 的 ， 因为 网络 虽 然 有
大 的连 通度 和小直 径 ， 通 过 该 网络 中若 干条 内 但 点不 交 的路并行 传 输 信 息 时 ， 中某些 路 径 可 能 其 很 长因 而传输延 迟大 ， 信息 达 到的 时间 间隔大 ， 从 而影 响 了整个系 统 的有 效 性 ， 因此在 并 行 系 统 中 只用 连通 度和直 径或 容错 直径作 为 网络可 靠性 和 有效性 的度量是 不恰 当 的 ， 以很 自然 地 产 生 了 所
在容错 网络 中 ， 点和 （ ）连线 的失灵 会导 结 或
个新 的参 数 —— 宽 直 径 ． 直 径 的 概 念 是 由 宽
Ｈ ｕ Ｌｕ 和 Ｆａｄｉ， 独 立 提 出来 的 ． ｓ ，ｙｕ ｌｎ ｒ ｌ ｎ ｉ 而 Ｈ ｕ在 参考文 献 ［ ］中证 明 了确定 给定 图 的宽 直 ｓ ６
ｄ ３≤ ２ Ｄ （ ２—１ ［ Ｄ２—１ （ ）（ ） Ｄ３—１ ）一Ｄ ］＋１ ２
证 明 ： 据宽 直径 的定 义 ， 根 可知 只 需证 明对 Ｇ
集 Ｆｃ （ ） 如果 Ｉ ］那 么 Ｇ —Ｆ是 连通 Ｇ ， ｉ＜｜ Ｆ ｝ ，
的 ， Ｇ—Ｆ的直径 是 确定 的 ， 即 Ｇ的 （ 一１ 容 错 直 ｜ ） ］ ｝ 径 Ｄ （ ）定义 为 ： （ ） ＝ｍａ ｛ （ Ｇ Ｇ ｘ ｄ Ｇ—Ｆ） ：
关键 词 ： 连通 度 ； 直径 ； 容错 直径 ； 宽直径 ； 网络
容错直 径 问题 是 否为一 个 Ｎ Ｃ问题 ． Ｐ
０ 引 言
在分 析 网络 拓 扑结 构 时 ， 常把 网络 中组 件 通 抽 象成一个点 ， 通信 信 道抽 象 成 两点 之 间 的连 把
线， 于是该 网络的拓 扑 结构 就被 抽 象成 一 个 图． Ｇ 的直径为 ｄ Ｇ （ ）是 Ｇ中任 何两顶点 之 间最短路 的
中任 意两 顶 点 ｕ和 存在 ３条 内部 点不 交且 长 度 都不 超过 ２ Ｄ （ 一１ ［ Ｄ ） （ 一１ （ ３—１ ）Ｄ ）一Ｄ ］＋
１的 ｕ 即可． 路 当Ｄ ≥ Ｄ ２≥ ３时 （ 一１ （ ３—１ Ｄ ）Ｄ ）一（ ，＋１ ＝ Ｄ ） Ｄ３ Ｄ （ ２—２ ）一Ｄ ２≥ Ｄ２ Ｄ （ ２—２ ）一Ｄ２＝ Ｄ２ Ｄ （ ２—３ ）≥ ０ （） １ Ｄ （ ３—２ ２Ｄ ）＋２一（ ２—１ （ ３—１ Ｄ ）Ｄ ）＝Ｄ Ｄ ２３
对 于任 意 ｋ 连通 图 ， 的容错 直径 不超过 宽 直径 ｄ ， 它 讨论 ｄ 和 之 间的进一 步 关
系是很有 意义 的． 本文证 明 了 当Ｄ ≥ ３时 ，，≤２ Ｄ 一１ ［ Ｄ 一１ （ ，一１ ２ ｄ （ ： ） （ ： ）Ｄ ）一Ｄ ］ ：
＋１ 改进 了 已有的 结果． ，
Ｋ ｉ ｎｍｏｒ ｙ和 Ｋ ｉ ｎ ｍ ｒ ｙ 提 出来 的 ， ｒ ｈ ａ ｏｔ ｓ ｈ ｒｈ ａ ｕｔ ¨ ｓ ｈ 直
容错 直 径 可 以度 量 容 错 网 络 中数 据 传 输 延
迟， 宽直径能度量网络的容错度和传输效率 ， 因此
容错 直径 和宽直 径是 设计 和评 估 网络性 能 的重要 参数 ， 了解 它们 之 间 的关 系 对 设 计 和评 估 网络 的 性 能 有着很 重要 的 意义 ， 文 研究 了 ３连 通 图 的 本 容错直 径 和宽直 径 之 间 的关 系 ， 改进 了这 方 面 已
径 问题是 一个 Ｎ Ｃ问题． Ｐ
致 数据传输延 迟的 增加 ， 因此 采 用 拓扑 结 构 的直
径来度量传输延迟是不准确的， 而在容错网络中， 哪些 结点和 （ ）连线 失灵是 随机 的 ， 了准确 地 或 为 度量容错 网络中的数据传输 ， 引进了一个新 的度 量参 数 —— 容 错 直 径． 容 错 直 径 概 念 是 由
关 于 ３连 通 图 的 容 错 直 径 和 宽 直 径 的 一 个 新 结 果 冰
周 树 娜 刘焕 平
（ 哈尔 滨 师 范 大 学 ）
【 摘要】 容错直径 可以度量容错网络 中数据传输延迟， 宽直径 ｄ 能度量网 络 的容错度 和传输 效率 ， 因此容错 直径和 宽直 径是设 计和评 估 网络性 能 的重要参 数．
维普资讯
第 ２ 卷 ４
第 ２期
哈尔滨师范大学 自然科学学报
Ｎ ＵＲ Ｃ ＥＮ Ｓ Ｊ ＵＲＮＡቤተ መጻሕፍቲ ባይዱ ＯＦ ＨＡ Ｉ ＡＴ ＡＬ Ｓ Ｉ ＣＥ Ｏ ＲＢ Ｎ ＮＯＲＭＡＬ ＵＮＩ ＶＥＲＳ Ｔ ＩＹ
Ｖ １ ４ Ｎ ． ０ ８ ｏ． ， ｏ２２ ０ ２
维普资讯
第 ２期
关 于 ３连 通 图 的 容 错 直 径 和宽 直 径 的一 个 新 结 果
５ ９
下 面介 绍 一下本 文用 到 的基 本 概念 ：
容错 直径 ： Ｇ是 一个 ｜ 通 图 ， 设 ］ ｝ 连 则对 任 何子
若Ｄ ２≥ ３ 则 ，
有 的结 果．
径和容错直 径是 两个 独立 的概念 ， 于 给定 的图 ， 对
有许 多有效算 法可 以求 出其 直径 ， 容 错 直 径 问 但 题要 比直径 问题 困难 得 多 ， 目前 为止 还 不 能证 明
收稿 日期 ：０７—０ ２０ ９—１ ２ －黑龙 江省教育厅科学研究基金项 目（ １１ １２ １５ ｌ１ ）
一
最大 长度 ， 明一个 数 据从 它 的 源 到过 目的地 通 表 过 中间处理器存储 转 发 所需 的最 小次 数 ， 而连 通
度表表示 的是 网络 能容忍 同时失灵 处理 器 的最 大
数 目． 因此 直径 和连 通 度分 别是 度 量互 连 网络传 输 延迟 和可靠性 的两 个重要 参数．

合集下载

研究背景

研究背景

1.1 研究背景1736年，欧拉采用图的方式解决了哥尼斯堡七桥问题，成为图论〔及拓扑学〕的创始人。

此后的一个世纪内图论处于萌芽阶段。

1859年，英国数学家哈密顿发明了一种游戏：用一个规则的实心十二面体，它的20个顶点标出世界著名的20个城市，要求游戏者找一条沿着各边通过每个顶点刚好一次的闭回路，即“绕行世界”。

用图论的语言来说，游戏的目的是在十二面体的图中找出一个生成圈。

这个问题后来就叫做哈密顿问题。

1852年，毕业于伦敦大学的弗南西斯.格思里来到一家科研单位搞地图着色工作时，发现了一种有趣的现象：“看来，每幅地图都可以用四种颜色着色，使得有共同边界的国家都被着上不同的颜色”。

1872年，英国当时最著名的数学家凯利正式向伦敦数学学会提出了这个问题，于是四色猜想成了世界数学界关注的问题。

此后的一个世纪内图论问题大量出现。

二十世纪中叶以后（侯新民, 2002）1，由于军事、生产管理、交通运输、计算机网络等方面提出的实际问题的需要，特别是许多离散性问题的出现，以及由于有了大型电子计算机，从而使大规模问题的求解成为可能，图论及其应用的研究得到了飞速的发展。

图论成为近年来离散数学和组合数学领域较为活跃的分支之一（侯新民, 2002）1。

图的某些参数如连通度和直径，因为其在图论和组合中固有的重要性及其与通信网络的容错性和传输延迟的关系而得到广泛研究。

超大规模集成电路技术和光纤材料科学的发展使我们有能力设计大型并行处理计算机系统和快速、复杂的通信网络。

这些系统不仅要求我们研究网络的连通度和直径，而且要研究连接两个节点或两个点集间的内部点不交的多条路径。

双环网络是具有N个节点和出度为2的对称循环图，是计算机互连网络或通讯系统的一类重要拓扑结构,广泛应用于计算机局域网和各种并行处理结构。

这里所讨论的互连网络和通讯系统具有广泛的含义（陈宝兴, 2004）1，泛指组件(计算机子网络，计算机，计算机内部的处理器，存储器，通信设备，其它元件或设备)集合与通信信道(有线或无线的)集合按一定的点对点方式相互连接所形成的系统。

广义Petersen图的直径

广义Petersen图的直径


其一条最短路, 其路长等于|p1|.
情形三：i≡2(mod 3) ，分两种子情形来讨论 1.1 m≡0或1(mod 3)，此时u0ui最短路的长度为(i+
10)/3, 同时可找到两个内圈点w0，wi及其一条最短路，
其路长也等于(i+ 10)/3. 1.2 m≡2(mod 3)
为(m-i)/3+2，同时可找到两个内圈点w0，wi-1及其一条
最短路, 其路长与之相等.否则， u0ui最短路的长度为 (i+ 10)/3, 同时可找到两个内圈点w0，wi+2及其一条最 短路，其路长也等于(i+ 10)/3.
m i 若m为偶数，且恰有 2
，此时u0ui最短路的长度
定理4
当m>7时, p(m,3)的直径可表示成下面的形式：
定理1
在p(m,3)中, 对任意一个外圈点ui(3≤i≤m-3), 一定
存在一条经过内圈点wi的最短的u0ui路, 并且wi ui是这条路上
的最后一条边.
m 证明：只考察 3 i 的情形，其它情形类似。 2
情形一：i≡0(mod 3)，此时可找到一条最短的u0ui路
* p1 : u0 w0 w3 wiui
的直径.
定义 广义Petersen图记为p(m,a), 其中a<m/2, m和a均
为正整数. 它的顶点集定义为U∪W, 其中U={u0 , …,um1
},W={w0 , …,wm-1}.将U中的元素称为外圈点, W中的元
素称为内圈点; 边集为E={ui wi , ui ui+1, wiwi+a :0≤i≤m-1}, 称ui wi为对应边,称wiwi+a为内圈边, 称ui ui+1为外圈边, 下 标为模m的运算.
有向双环网络的宽直径公式

有向双环网络的宽直径公式

双环 网络 因其对 称性 ， 于扩 展 且 具有 一 定 的容 易 错能 力． 与环状 网络 比较 ， 直 径 较小 ． 其 双环 网络在 计 算机 局域 网 ， 城域 网及并 行 计算 机 系统 的设 计 与 实现
络 Ｇ（ ；１ｓ） ｎ ｓ，２ 是强 连通 的 当且 仅 当 ｇ ｄ ｎ ｓ， ＝ １ ｃ （ ，ｌ ） ． 因为 我们所讨 论 的是 强 连 通 的有 向双环 网络 ， 以下 所
有 向 双 环 网 络 的 宽 直 径 公 式
陈 宝兴 杜 妮 ， 书 明。 ， 周
（ ． 州 师 范学 院 计 算 机科 学 系 ， 建 漳 州 ３ ３ ０ ； １漳 福 ６ ０ ０ ２ 厦 门大 学 数 学科 学 学 院 ， 建 厦 门 ３ １０ ； ． 福 ６ ０ ５ ３福 建 师 范大 学 数 学 与 计算 机 科 学 学 院 ， 建 福 州 ３０ ０ ） ． 福 ５ ０ ７
列 ：Ｏ Ｏ ， １ Ｏ ， Ｏ １ ， ２ Ｏ ， １ １ ， Ｏ ２ ， ，． （ ，） （ ， ） （ ，） （ ，） （ ，） （ ， ） … （ ， 『 Ｏ ，＿一 １ １ ， 一 ２ ２ ， ，． ｉ ） … ， １． １ ， ）（ 『 ，） （ ，） … （ 一 ， ， （ ， 一 ） 『 『
（） １ 当 一 １ 口： １时 ， ２ Ｇ ， Ｄ （ ）一 ｎ １ 一 ． （ ）当 “＞ １ 口＞ １时 ， ２ Ｇ）＝ Ｄ（ ＋ １＝ ｍａ ｛ ＋ ｂ Ｐ一 １ ａ ｂ ｑ １ ． ２ ． Ｄ （ Ｇ） ｘａ — ，＋ — 一 ）
（） “ １口 １ Ｄ （ ） 『 １ ＋口 ． ３ 当 一 ， ＞ 时， ｚＧ 一 生 ＋口 ～２ （） “ １口 １ Ｄ （ ） 『 ＋ｂ ～２ ４ 当 ＞ ， 一 时， Ｇ 一 二 １ ＋“ ．
图论及其应用

图论及其应用

图和子图 图和简单图图 G = (V, E)， 其中 V = {νv v v ,......,,21} V ---顶点集， ν---顶点数E = {e e e 12,,......,ε}E ---边集， ε---边数例。

左图中， V={a, b,......,f}, E={p,q, ae, af,......,ce, cf} 注意， 左图仅仅是图G 的几何实现（代表）， 它们有无穷多个。

真正的 图G 是上面所给出式子，它与顶点的位置、边的形状等无关。

不过今后对两者将经常不加以区别。

称 边 ad 与顶点 a (及d) 相关联。

也称 顶点 b(及 f) 与边 bf 相关联。

称顶点a 与e 相邻。

称有公共端点的一些边彼此相邻，例如p 与af 。

环（loop ，selfloop ）：如边 l 。

棱（link ）：如边ae 。

重边：如边p 及边q 。

简单图：（simple graph ）无环，无重边 平凡图：仅有一个顶点的图（可有多条环）。

一条边的端点：它的两个顶点。

记号：νε()(),()().G V G G E G ==。

习题1.1.1 若G 为简单图，则εν≤⎛⎝ ⎫⎭⎪2 。

1.1.2 n ( ≥ 4 )个人中，若每4人中一定有一人认识其他3人，则一定有一 人认识其他n-1人。

同构在下图中， 图G 恒等于图H , 记为 G = H ⇔ V （G)=V(H), E(G)=E(H)。

图G 同构于图F ⇔ V(G)与V(F), E(G)与E(F)之间各存在一一对应关系，且这二对应关系保持关联关系。

记为 G ≅F 。

注 往往将同构慨念引伸到非标号图中，以表达两个图在结构上是否相同。

de f G = (V, E)y z w cG =(V , E )w cyz H =(V ’, E ’)’a ’c ’y ’e ’z ’F =(V ’’, E ’’)注 判定两个图是否同构是NP-hard 问题。

完全图(complete graph) Kn空图（empty g.） ⇔ E = ∅ 。