ECQ网络中嵌入哈密顿圈的高效算法研究

网络的哈密顿性质在信息通信领域中具有重要的应用。具有哈密顿性质的网络能够高效率地进行线性或循环通信。交换交叉立方体(ECQ)网络是一种性能优良的互连网络。它既有较小的网络直径,又具有较低的构造成本。如果在ECQ网络的多播路由算法中使用哈密顿性质,则能够有效地减少ECQ网络通信中的死锁和拥塞。对ECQ网络中嵌入哈密顿圈的构造算法进行了研究。首先,给出了当s≥3和t≥3时,ECQ网络上从任意节点出发构造哈密顿圈的算法。然后,给出了当1≤s≤2时,ECQ网络上哈密顿圈的构造算法。最后,通过仿真试验验证了算法的正确性、有效性和高效性。本研究结果可为ECQ网络哈密顿性质的应用提供重要的理论依据。

邻集交与Hamilton性质

设G是一个n阶简单连通图,具有独立数α,本文证明了如下两个定理: 定理1如果对于G中任何两个距离为2的点u,v,都有|N(u)∩N(v)≥α,则除一些特殊图外,对于G中任一对点x,y,都存在一条Hamiltonian x-y路。定理2如果对于G中任何两个距离为2的点u,v,都有|N(u)∩N(v)≥α1,则除一些特殊图外,G是Hamiltonian。

树图的 Hamilton 性质

设Ｔ（Ｇ）为连通图Ｇ的树图，若Ｇ至少有三个支撑树，且ＧＳＦ１，则Ｔ（Ｇ）是Ｅ２－Ｈａｍｉｌｔｏｎ的．

图的关联图及关联图的边着色

对图G(V,E),假设G的关联图I(G)为:V(I(G))={(ve)|v∈v(G)and e∈E(G),v与e相关联};E(I(G))={(ue,ve)|u=v and e≠f,or e=f and u≠v,or uv=e,or uv=f。本文综述图的关联图的性质及关联图的边着色。

具有给定指数的本原有向图的Hamilton性质 (英文)

本文解决了１９８２年Ｊ．Ａ．Ｒｏｓｓ提出的两个问题，并得到如下结果：（１）设Ｄ是具有围长ｓ＞１和指数γ（Ｄ）＝ｎ＋ｓ（ｎ－２）的ｎ阶本原有向图，则Ｄ是Ｈａｍｉｌｔｏｎ的；（２）设Ｄ是含有环的ｎ阶本原有向图且γ（Ｄ）＝２ｎ－２，则Ｄ是Ｈａｍｉｌｔｏｎ的当且仅当ｍａｘ｛ｄ（ｕ,ｖ）|γ（ｕ，ｖ）＝２ｎ－２｝＝ｎ－２．