无向双环网络的强彩虹连通性

设n,s_1,s_2是3个正整数,满足1≤s_1s_2n/2,gcd(n,s_1,s_2)=1.无向双环网络G(n;±s_1,±s_2)是如下定义的无向图(V(G),E(G)):其节点集V(G)={0,1,…,n-1},边集E(G)={i→i+s_l(mod n),i→i-s_l(mod n),i→i+s_2(mod n),i→i-s_2(mod n)|i=0,1,…,n-1}.本文中通过对无向双环网络任意两点之间的最短路径进行刻画,进而给出了该网络强彩虹连通的一个着色方案,最后得到了该网络强彩虹连通数的一个上界,该上界主要由G(n;±s_1,±s_2)所对应的同余方程xs_1+ys_2≡0(mod n)的最小非负解和最小交叉解的4个参数表示.     

无向双环网络G(N;±r,±s)直径的研究

将直角坐标系引入无向双环网络的研究,通过直角坐标系构造无向双环网络的最小路径图,在详细分析无向双环网络最小路径图性质的基础上,系统研究无向双环网络G(N;±r,±s)的直径、平均直径,验证直径的下界,得出平均直径的下界.最后给出直角坐标系下无向双环网络最小路径图的仿真方法及直径、平均直径的计算方法.     

一类3pn阶亚循环群的4度Cayley图

采用群与图的方法,研究一类3pn阶亚循环群的连通4度无向Cayley图.通过决定Caley图的自同构群得出此类亚循环群是弱4-CI的,并由此给出3pn亚循环群的连通4度无向Cayley图的完全分类,最后证明此类图都正规而且非弧传递.     

基于L形瓦的无向双环网络直径求解算法

针对构造无向双环网络最短路径图(MDD)常用的节点遍历方式较为复杂、割裂了有向双环网络和无向双环网络之间的内在联系的问题,将有向双环网络拓扑结构映射到平面直角坐标系,在得到的L形瓦基础上,对其上的节点坐标通过简单坐标变换,得到无向双环网络MDD上对应节点坐标,进而计算无向双环网络的直径.相对于目前构造无向双环网络MDD或其等价拓扑结构普遍采用节点遍历方式而言,该算法仅增加了几次比较,就改善并提高了无向双环网络直径的求解效率.     

基于树的无向双环网络G(N;±r,±s)寻径策略

提出了新的无向双环网络G(N;±r,±s)的直径求解方法,将其图论模型中的节点进行了重新排列,得到了一种基于树的路由模型,研究了该树型结构中与路由相关的一些性质;给出了计算无向双环嘲络G(N;±r,±s)直径d(N;±r,±s)的显式公式;证明了无向双环网络G(N;±r,±s)的直径等于树高;验证了Boe-sch和Wang等提出的无向双环网络G(N;±r,±s)直径的下界.     

无向双环网络G(N;±r,±s)直径求解方法

提出新的无向双环网络G(N;±r,±s)的直径求解法———分步法;并得到一种新的直观图———螺旋环,研究了螺旋环的性质;给出了无向双环网络的直径d(N;±r,±s)的显式公式;给出了N,s都固定的直径算法;在N固定,且2≤r相似文献   

关于有向双环网络G(N;r,s)平均直径的研究

针对有向双环网络的最小路径图,给出了一个快速计算有向双环网络平均直径的高效算法.根据该算法,只要知道有向双环网络G(N;r,s)的3个参数N,r和s,就能计算出L-型瓦的4个参数a,b,p和q,从而计算出平均直径.对直径与平均直径之间的关系进行了仿真研究,结果表明:在一个无限族中,直径与平均直径的分布呈轴对称图形;同一网络的平均直径约等于直径的一半;在任意无限族中,当直径达到下界值时,平均直径不一定达到下界值,但当平均直径达到下界值时,直径一定达到下界值.最终表明平均直径比直径能更好地衡量网络传输效率.     

任意无向加权图K点连通扩充的逐次改善算法

为了对网络的可靠性寻求较好的近似算法,研究了任意无向不加权图情况下的极小K 点连通扩充算法;在此基础上提出无向加权图G总边数和各点的连通度均保持不变时,使图G的总权值变小的一种可行边交换方法;同时得出一个可行边交换的引理,并加以证明.最终推出了任意无向加权图K点连通最小扩充的逐次改善算法,应用该算法作了大量例题,得到比较满意的效果.为解决任意无向加权图最小扩充问题给出了一种新途径.     

有向Kautz图的超级限制弧连通性

限制边连通度是比传统的边连通度更精确的网络可靠性指标.限制边连通度在有向图中有4个推广,分别对应有向图的4种限制弧连通度.有向Kautz图可以作为多处理机系统的基础拓扑,是一类重要网络.证明了有向Kautz图K(d,n)的4种限制弧连通度都为2d-2,并且确定了对应的最小限制弧割的结构特征.     

无向双环网络G(N;±1,±s)紧优分布特性

研究了无向双环网络G(N;±1,±s)的紧优分布特性,提出了一种快速仿真算法,计算出了4≤N≤1 000中任意节点数N存在的紧优个数n,仿真出了4≤N≤1 000的n-N紧优分布率和n/(N-3)-N紧优分布率,给出了其中无紧优无向双环网络的N值.仿真结果表明,n-N分布呈现平稳的波动特性,n不随着N递增,而n/(N-3)-N随着N的增加呈波动性下降的趋势,且与N的奇偶性无关.     

qp~2阶连通4度半传递图

称图X是半传递图,如果X的自同构群Aut(X)作用在其顶点集和边集上都传递,但作用在其弧集上非传递。本文证明了qp2(其中q相似文献   

最优双环网络的构造算法

在刘焕平等人工作的基础上,给出一个k(k≥0)紧优双环网络的构造算法及其若干具体应用.给出N最小的5紧优双环网络G(417 289;47 721),其直径为1 122;N最小的6紧优双环网络G(7 243 747;65 576),其直径为4 666.     

带循环时间窗口的独立路径配送问题

通过优化物流的配送运输网络,可以有效降低配送成本.带循环时间窗口的独立路径配送问题实际是车辆路径优化问题,属于NP-hard问题类.定义了循环时间窗口,并设计了图形预处理算法,通过建立有向赋权网络上带循环时间窗口的物流配送问题的数学模型,构造有向网络赋权辅助图,在辅助图上采用最大流的Ford-Fulkerson算法来解决弧独立路径问题,判断问题是否有解,之后用最小费用流的最小费用路算法来求权值和最小的R条弧独立路径,得到该问题的一个最优算法,为物流配送环节提供新思路.     

图是λ4-最优及超级-λ3的最小度条件

为精确估计网络的可靠度,我们需要最优化其图模型的限制边连通度,证明一个n≥11阶最小度δ(G)≥[n/2]-3的λ4-连通图G,在一定的条件下是λ4-最优的.进而,若n≥12,则G是超级-λ3图.并举例说明了最小度的下界是最好可能的.     

一些具有较多边数图的临界群

图的临界群是图生成树数目的一个加细,图的临界群的阶数恰为该图的生成树的数目.确定了一些具有较多边数图如Kn-K1,m,Kn-Km,Kn-mK2,Kn,n-nK2的临界群的结构,证明了这些图的临界群不是一个循环群,而是多个循环群的直和.     

上可嵌入图与次上可嵌入图的线性荫度

通过度再分配的方法研究上可嵌入图与次上可嵌入图的线性荫度,证明了最大度△不小于(4-3ε)~(1/3)且欧拉示性数ε≤0的上可嵌入图其线性荫度为「△/2」.对于次上可嵌入图,如果最大度△≥(4-3ε)~(1/3)且ε≤0,则其线性荫度为「△/2」.改进了文献[1]中最大度的的界.作为应用证明了双环面上的三角剖分图的线性荫度.     

最小度生成树的最大度算法

最小度生成树问题是一个NP难问题.给出了求最小度生成树的一个直观近似算法:找到图G的最大度,从其所在的基本圈上删掉1条与其关联的边,如此循环,直到图G的最大度不在任何基本圈上,如还有其它基本圈,删掉圈上的1条边,得到1棵生成树.这种算法得到的生成树的最大度数比最优解的度数至多大1.     

3r阶循环群的最小图

设α(n)是自同构群与n阶循环群C(n)同构的图的最小顶点数,该文构造出群为C(3r)的具有α(3r)个顶点的边数最少的图,并证明了这样的图是唯一的.     

一种新的紧优双环网络无限族构造方法

提出一种新的紧优双环网络无限族的构造方法.该方法从一个具体的不含k(0≤k≤m)紧优双环网络的N0出发,通过求一个同余方程方程组的所有解,构造不含k(0≤k≤m)紧优双环网络的无限族.从一个具体的可实现L形瓦出发,利用其h和y互素条件,构造可实现L形瓦的无限族.作为应用,给出若干7紧优和8紧优双环网络无限族;解决了几个关于紧优双环网络无限族的公开问题.     

4连通图中生成树上的可去边

图的可收缩边与可去边是研究连通图的构造和使用归纳法证明连通图的一些性质的有力工具.利用边点割端片的性质给出某些4连通图中在特定子图上可去边的分布情况,得到了最小度至少为5或围长至少为4的4连通图中在其生成树上存在至少两条可去边;同时也得到了最小度至少为5的4连通图中在其生成树外存在至少两条可去边.