关于双极模糊图圈连通指数的注记

图的拓扑指数计算是化学图论的重要研究内容之一.近年来,模糊图框架下的拓扑指数逐渐被定义和研究,但缺乏对双极模糊图框架下拓扑指数的扩展.因此,通过对负极隶属度函数和圈连通性的定义,将文献[1]中提出的模糊图圈连通指数概念扩展到双极模糊图的框架.同时认为,一些在原来模糊图上得到的关于圈连通指数的性质,可以推广到双极模糊图框架中.

全图的圈连通度(英文)

对于一个图G,它的一个圈边割是一个边集,将该边集去掉之后能够分离出两个圈.如果G有一个圈边割则称G是圈可分离图.设G是一个圈可分离图,其圈边连通度cλ(G)是G的最小圈边割的基数.圈点割和圈点连通度cκ(G)可以类似定义.本文给出了全图T(G)的圈边连通度和圈点连通度的上界和下界.

k正则点传递二部图的超圈边连通性

如果删除一个图G的边集E后,至少有两个连通分支有圈,则称E为图G的圈边割,把有圈边割的图称为圈可分的.对于一个圈可分图G来说,最小圈边割的基数称为圈边连通度λc(G).如果去除任何一个最小圈边割,总存在一连通分支为最小圈,则图G为超圈边连通的.利用反证法,得到一个(k≥4)正则围长g(G)≥6的点传递二部图是超圈边连通的.

2r-正则图连通圈网络的Hamilton分解

互连网络是超级计算机的重要组成部分。互连网络通常模型化为一个图,图的顶点代表处理机,图的边代表通信链路。2010年师海忠提出互连网络的正则图连通圈网络模型,设计出了多种互连网络,也提出了一系列猜想。文中证明了2r-正则图连通圈网络可分解为边不交的一个Hamilton圈和一个完美对集的并,从而证明了当原图为2r-正则连通图时,这一系列猜想成立。

交叉立方体连通圈网络的Hamilton分解

交叉立方体连通圈网络CQCC(n)(n≥3)是一类典型的互连网络,它是3正则的.在2010年,师海忠提出如下猜想:CQCC(n)(n≥3)是Hamilton可分解的.也就是说,交叉立方体连通圈网络CQCC(n)(n≥3)可分解为边不交的一个Hamilton圈和一个完美对集的并.在这篇文章中,证明了当n=3;4;5;6时猜想成立,即交叉立方体连通圈网络CQCC(n)(n=3;4;5;6)可分解为边不交的一个Hamilton圈和一个完美对集的并。

Cayley图连通圈的一个代数性质研究

探讨Cayley图连通圈成为Cayley图的一个充分条件.利用代数学中关于群扩展理论的基本知识证明了如果Carley图连通圈中的Cayley图是具有完全旋转的Cayley图时,则相应的Cayley图连通圈可表示为一个半直积群对应的Cayley图,并通过几个实例进行说明验证.

平面图圈边连通度的有效算法

圈边连通度cλ（G）是指图G中所有圈边割中的最小势，即最少割掉多少条边使得图G的两个连通分支中都各有至少一个圈。求一般图的圈边连通度至今仍未找到有效算法。本文提出了一个多项式时间的算法求解平面图的圈边连通度。该算法的时间复杂度是O（｜V｜^2）。

具有两个同阶轨道的双轨道图的圈边连通度(英文)

一个边割被称为圈边割,如果该边割能分离图的两个不同圈.如果一个图有圈边割,称该图为圈边可分离的.一个圈边可分离图G的最小圈边割的阶数被称为圈边连通度,记作cλ(G).定义:ζ(G)=min{w(X)|X导出G的最短圈},其中w(X)为端点分别在X和V(G)-X中的边的数目.如果一个圈边可分离图G使得cλ(G)=ζ(G)成立,称该图是圈边最优的.Tian和Meng在文章[11]以及Yang et al在文章[15]中研究了两种不同的双轨道图的圈边最优性.本文我们将研究具有两个同阶轨道的双轨道图的圈边连通度.

关于冒泡排序连通圈网络猜想的一个注记

冒泡排序连通圈网络BSCC(n)是一类重要的互连网络,它是3正则的.2010年师海忠提出了如下猜想:冒泡排序连通圈BSCC(n)(n≥4)可分解为边不交的一个Hamilton圈和一个完美对集的并.在本文中证明了当nn==5,4时猜想成立,另外,给出了BSCC(6)的一个圈分解.

图的圈边连通度和圈弧连通度

令G是一个简单图.G的圈边连通度cλ(G)定义为E(G)的一个子集F的最小基数,其中G−F不连通且至少有两个分支包含圈.令D是一个有向图.D的圈弧连通度λ_(c)(D)定义为A(D)的一个子集S的最小基数,其中D−S不强连通且至少有两个强连通分支包含有向圈.在文章中,我们研究了无向二元Kautz图、无向de Bruijn图和无向二元广义de Bruijn图的圈边连通度.而且,我们获得了Kautz有向图、de Bruijn有向图和广义de Bruijn图的圈弧连通度.

同阶双轨道连通图的超圈边连通性

对于图G,如果G-F是不连通的且至少有两个分支含有圈,则称F为图G的圈边割.如果图G有圈边割,则称其为圈可分的.最小圈边割的基数叫作圈边连通度.如果去除任何一个最小圈边割,总存在一分支为最小圈,则图G为超圈边连通的.设G=(G_1,G_2,(V_1,V_2))为双轨道图,最小度δ(G)≥4,围长g(G)≥6且|V_1|=|V_2|.假设G_i是k_i-正则的,k_1≤k_2且G_1包含一个长度为g的圈,则G是超圈边连通的.

完全二叉树到星连通圈网络的嵌入

依据对二叉树嵌入的研究,主要讨论了完全二叉树到星连通圈网络的嵌入,得出该嵌入的膨胀数为1,并且给出了完全二叉树嵌入星连通圈网络的构造算法.

k次十二面体–师连通圈网络

互连网络是超级计算机的重要组成部分,片上互连网络是当前研究的热点课题之一。k次十二面体–师连通圈网络是一类重要的互连网络,是在2010年师海忠提出互联网络的正则图连通圈网络模型的基础上设计的新网络模型。它是将十二面体连通圈网络的每个顶点用三角形代替k次得到的,记为DSCC(k),它是3正则3连通的平面图,且有许多好的性质。文中提出了关于该网络的一系列猜想,如猜想1:k次十二面体–师连通圈网络是Hamilton图,对猜想1、2、3作了严格的证明。作者还利用图的笛卡尔乘积方法构建了新的笛卡尔乘积互连网络DSCC(k)xK2和DSCC(k)xCm,并对其性质进行了研究。

推广立方连通圈网络的Hamilton分解的算法

立方连通圈网络是超立方体的有界度变形,它具有超立方体几乎所有的优良性质,而且克服了超立方体顶点度随网络规模增大而增大的缺点,是代替超立方体的一个具有强大竞争力的网络结构。但立方连通圈网络的结构是简单还是复杂呢?这是一个悬而未决的问题。带弦环网络是一类经典的互连网络,该网络具有结构简单等优点。在这篇文章中利用师海忠提出的正则图连通圈网络模型设计出了包含立方连通圈网络的一类网络——推广立方连通圈网络GCCC(n) (n >2),证明了GCCC(n) (n >2)可分解为边不交的一个Hamilton圈和一个完美对集的并,即GCCC(n) (n >2)是带弦环网络。并给出推广立方连通圈网络分解为边不交的一个Hamilton圈和一个完美对集的并的算法。

基圈数为5的2-连通平图的构造

所有的 2 -连通平图可通过收缩 2度点变换成无 2度点的、基圈数不变的 2 -连通平图 .本文给出了基圈数为 5的、无 2度点的所有 2

BSCC(4,k)的Hamilton圈分解

冒泡排序连通圈网络BSCC(n)是一类重要的互连网络。2010年师海忠提出了如下猜想:冒泡排序连通圈网络BSCC(n)(n≥4)可分解为边不交的Hamilton圈和完美对集的并。记BSCC(n)为BSCC(n,0),对BSCC(n,0)的每个顶点用一个三角形代替,得到新网络BSCC(n,1),对BSCC(n,1)的每个顶点用三角形代替得到BSCC(n,2),类似迭代k次得新网络BSCC(n,k)。师海忠进一步提出猜想2:BSCC(n,k)可分解为边不交的一个Hamilton圈和一个完美对集的并。证明了BSCC(4,k)可分解成边不交的一个Hamilton圈和一个完美对集的并。

基于超立方体和圈的细胞分裂生长网络及其性质

立方连通圈是超立方体的有界变型,在这篇文章中作者以立方连通圈网络CCC(n)(n>2)为基础设计了一种新网络--CCC(n,k)(n>2且k是非负数),它是3正则3连通的,且有许多好的性质。作者证明了CCC(3,0)是哈密尔顿连通图,且CCC(n,k)(n>2且k是非负数)是哈密尔顿图,但当k>2和n>2或者k=1和2<n<8时,CCC(n,k)不是点可迁的。作者还研究了CCC(n,k)(n>2且k是非负数)和C_m的笛卡尔积的一些性质。

基于FQn和圈的细胞分裂生长网络FQCC(n,k)及其性质

折叠立方体连通圈网络FQCC(n) (n >1)是一类典型的互连网络,它是3正则的。师海忠根据折叠立方体连通圈网络i>FQCC(n) (n >1)和细胞分裂生长图模型设计出了一种新的互连网络——FQCC(n,k) (n >1,k是非负整数):用三长的圈代替FQCC(n)的每个顶点且圈中每个顶点恰位于折叠立方体连通圈网络FQCC(n) (n >1)中与该顶点关联的一条边上,得到新的网络FQCC(n,1);再类似的用三长的圈代替FQCC(n,1)的每个顶点得FQCC(n,2),循环执行上述方法k次得到的新网络称为FQCC(n,k) (n >1,k是非负整数)。该网络FQCC(n,k)在保持了FQCC(n)的小的固定的度(为3)的特性外,还有比FQCC(n)更好的扩展性。进而提出了猜想:FQCC(n,k)是Hamilton图。赵媛证明了FQCC(2,k)是平面图和Hamilton图,还证明了FQCC(n,k) (k >1)不是点可迁的。

两类网络图的平衡划分问题

图的顶点平衡划分问题是图论研究的重要内容,广泛应用于计算机网络、图像处理和并行计算等领域,可以提高网络安全性和计算速度。设 (V1,V2) 是图 G 顶点的一个二部划分,若 -1 ≤ |V1|-|V2| ≤ 1,则称它是平衡划分。e(V1,V2) 中的边数称为该平衡划分大小。本文主要研究立方连通圈网图和 Pl Pk 图的平衡划分问题,得到这两类网络图平衡划分大小的下界分别为 和 ,并证明了下界最优性。

2—可扩平面图

证明了所有具有偶顶点数的5—连通平面图是2-可扩的,并给出了非2-可扩的4-连通平面图。