一类3度正则有向图网络模型.pdf

总 卷 第 期 数 学 研 究 ! ! 8’,9! :’9! 年 月 #$$! % ’()*+,’-.+/012+/34+,5/(67 519#$$! ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; 一类 度正则有向图网络模型 ! 孙 力 漳州师院计算机系 福建 漳州 ? !!$$$@ 摘 要 讨论了一种 度正则网络 这类网络具有较小的网络直径 本文给出了网络直径 网络 ! ? ? A 支撑树和欧拉环游的数目的公式9 关键词 网络 直径 支撑树 欧拉环游 B B B 中图分类号 C 文献标识码 D 近年来 在局域网 广域网和各种分布式计算机系统的迅速发展的推动下 互联网络的基 ? A ? 础理论也取得了巨大发展EF?#?!G 这些网络模型常常用有向图和无向图来构造 有向迭线图在 ? 9 计算机网络模型的研究中得到了广泛的应用E?HG 在最近的文献 中讨论了含有自环的圈的 ? EIG 伴随有向图的迭线图所构成 度正则网络的性能 本文将给出另一类新的 具有更短直径的 ! 9 A ! 度正则网络 其直径大约是 中提出的网络的一半 本文首先确定了这类网络的直径 进而 ? EIG 9 ? 得到这类网络支持树和欧拉环游的数目9 基本概念J 有向图定义为由结点和弧构成的二元组 是有限结点集 是连 KL@?ML@@?KL@ ?ML@ 接有序结点对的弧 定义为由 个结点 构成的无向图 其边集为 9N F?O@ #O PQR F?#?S ?O@ ? #O Q U 如图 所示 定义为 P?P @AP?P @QR F?#?S #O.’6#O@9N F?!@ F 9N F?O@ N F? Q QT F Q QTO #O #O U