山东轻工业学院学报（自然科学版）
山東輕工業學院學報（自然科學版）
산동경공업학원학보（자연과학판）
JOURNAL OF SHANDONG INSTITUTE OF LIGHT INDUSTRY(NATURAL SCIENCE EDITION)
2007年
1期
32-35,39
,共5页
匡桂娟%丁杰东%于仁师%曹洪波
劻桂娟%丁傑東%于仁師%曹洪波
광계연%정걸동%우인사%조홍파
并行系统%互连网络%广度优先搜索算法(BFS)%故障直径
併行繫統%互連網絡%廣度優先搜索算法(BFS)%故障直徑
병행계통%호련망락%엄도우선수색산법(BFS)%고장직경
考虑了至多可以删除多少个顶点才能保证互连网络的连通,给出了网络的容错能力.根据Menger定理可以得到BC互连网络之间至少存在n条内部节点互不相交的路径.利用广度优先搜索的思想,给出了求任意两个节点之间的n条内部节点互不相交,且在两点间所有路径中是最短的n条路径的算法.该算法为网络故障直径的研究提供了依据.而且,在故障存在但是网络连通的情况下,可以求得网络中任意两节点间的n条最并行路径,提高了网络的容错能力.本文对提出的方法及算法的正确性进行了证明,为研究互连网络的性质提供了新的研究方法.
攷慮瞭至多可以刪除多少箇頂點纔能保證互連網絡的連通,給齣瞭網絡的容錯能力.根據Menger定理可以得到BC互連網絡之間至少存在n條內部節點互不相交的路徑.利用廣度優先搜索的思想,給齣瞭求任意兩箇節點之間的n條內部節點互不相交,且在兩點間所有路徑中是最短的n條路徑的算法.該算法為網絡故障直徑的研究提供瞭依據.而且,在故障存在但是網絡連通的情況下,可以求得網絡中任意兩節點間的n條最併行路徑,提高瞭網絡的容錯能力.本文對提齣的方法及算法的正確性進行瞭證明,為研究互連網絡的性質提供瞭新的研究方法.
고필료지다가이산제다소개정점재능보증호련망락적련통,급출료망락적용착능력.근거Menger정리가이득도BC호련망락지간지소존재n조내부절점호불상교적로경.이용엄도우선수색적사상,급출료구임의량개절점지간적n조내부절점호불상교,차재량점간소유로경중시최단적n조로경적산법.해산법위망락고장직경적연구제공료의거.이차,재고장존재단시망락련통적정황하,가이구득망락중임의량절점간적n조최병행로경,제고료망락적용착능력.본문대제출적방법급산법적정학성진행료증명,위연구호련망락적성질제공료신적연구방법.
