一类仙人掌图的星边染色

图G的星边染色是指G的一个正常边染色,使得G中任一长为4的路和长为4的圈均不是2-边染色的.图G的星边色数χ’_(st)(G)表示图G有星边染色的最小颜色数.仙人掌图是一个连通图使得每个块是圈或者边.利用数学归纳法得到了一类仙人掌图C_(n)·C_(m)(n≥3,m≥3)的星边色数,从而推广已知结果.

路与星图的强乘积图的容错直径

设路P_(m)与星图S_(1,n-1)的强乘积图为G=P_(m)S_(1,n-1).首先,通过归纳假设和构造内点或边不交路的方法,结合星图的中心性,给出图G的点容错直径D_(w)(G)和边容错直径D′t(G).结果表明,对图G中发生的任意点或边故障,都有D_(w)(G)≤d(G)+2,D′t(G)≤d(G)+1.其次,通过顶点数和边数构造的不等关系,给出两个极大连通图的强乘积图的点容错直径的上界,以及两个非平凡连通图的强乘积图的边容错直径的上界.

度为2的广义星图矩阵的逆特征值问题

运用两种不同的方法对度为2的广义星图矩阵(一种特殊类型的树的矩阵)的逆特征值问题进行了深入研究。首先,引入了一种标记这种树的顶点的方案,以便以多种特殊形式表示相应的矩阵。然后,针对给定的两类不同的特征数据,将此类矩阵的逆特征值问题转化为线性方程组求解问题,得到了所研究问题有唯一解的充分必要条件。最后,给出了矩阵唯一解的表达式和相应的算法。通过数值模拟实例验证了结果的准确性。

字典积图的任意可分性

给定n个顶点的图G,对于满足∑_(i=1)^(k)n_(i)=n的任意一个正整数序列(n_(1),n_(2),…,n_(k)),如果都存在顶点集V(G)的划分(V_(1),V_(2),…,V_(k)),满足Vi导出的子图G[V_(i)]是连通的,并且|V_(i)|=n_(i),其中1≤i≤k,则称图G是任意可分图(简称为AP).两个图G和H的字典积图记为G?H,其顶点集为V(G)×V(H),(g,h)(g,h)是G?H的一条边当且仅当gg∈E(G)或者g=g且hh∈E(H).讨论了可迹图和任意可分图的字典积图的任意可分性,证明了对于最大度至多为n+1的树T,如果T有一条路P满足全部度数为(T)的顶点属于顶点集V(P),则字典积图T○Pn是任意可分图;如果G是一个可迹图且H是任意可分图,则图G○H是任意可分图;如果G=S(2,a,b)是一个满足2≤a≤b的任意可分星型树,则图G○G是任意可分图;如果G是哈密顿图且H是一个图,则G○H是任意可分图.

双星图的LI矩阵的Ky Fan k-范数

树是连通的无圈图,研究树的拉普拉斯矩阵具有重要的图论和实际意义.设G是一个有n个点和m个边的图,A(G)和D(G)分别是图G的邻接矩阵和对角度矩阵,那么G的拉普拉斯矩阵定义为L(G)=D(G)-A(G).LI矩阵定义为LI(G)=L(G)-(2m/n)I_(n),其中I_(n)是单位矩阵.图的LI矩阵的Ky Fan k-范数代表了拉普拉斯特征值和拉普拉斯特征值平均值之间距离的有序和.研究了双星图的LI矩阵的Ky Fan k-范数,证明了双星图的LI矩阵的Ky Fan k-范数满足文献[6]中提出的猜想.

基于A星搜索算法的5G前传路由选取技术

在基于到光纤直驱和波分复用等技术的5G前传网络中,无论使用哪种前传承载技术方案,均涵盖不同路由站点之间传输的场景。本文基于启发式图搜索法——A星搜索算法的思路,结合基站前传的特征以及分析盲目的图搜索的劣势,提出新的估价函数思想,并且为5G前传路由的选取提供一种更为高效的算法。

基于图论节点的改进A-star栅格路径规划算法

提出了一种将图论最短问题中的路径节点及栅格地图中的栅格节点位置信息结合的路径规划算法。依据图论最短问题思想,提取室内具有特殊信息的位置节点,并判断节点间可视性,加入到先决地图信息中。在此基础上改进的A-star算法在扩展节点时,根据启发函数,只在特殊节点位置进行扩展,避免计算大量不必要栅格点的启发函数,从而提高算法效率。实验结果表明,改进后的A-star算法较之前时间缩短了79.2%,所遍历栅格节点减少了99.4%,且栅格分辨率大小不影响路径规划效率。最后总结改进方法的优缺点,期望改进算法可用于室内多目标同时导航。

繁星树线图的完美匹配数

称一棵树T为繁星,如果它可以通过在星形树的悬挂点上添加一些悬挂边得到.给定两个正整数k和l满足k+l为偶数,令T_(k,l)表示由星形树S_(1,k)添加l条悬挂边而得到的所有繁星的集合.对任意的繁星T∈_(k,l),本文首先得到了其线图完美匹配数M(L(T))的表达式,然后通过引进一些变换,确定了M(L(T)),T∈_(k,l)的最小值和最大值.

几类r-冠图的星边染色

图的星边染色是指图G的一个正常边染色使得G中没有长为4的路或圈是2-边染色的.图G的星边色数是指图G有星边染色的最小颜色数.本文中研究路、圈、扇、轮的r-冠图的星边染色问题.使用图分解法,反证法,染色构造法,组合分析法等方法和理论,得到4类r-冠图的星边色数.

完全二部图的路和星分解

主要研究完全二部图的{路,星}-分解.设p,q为非负整数,得到了完全二部图K_(2k,n)可以分解为p条路P_(k+2)(P_(k+3))和q个星S_(k+1)的充要条件,以及完全二部图K_(k,n)可以分解为p条路P_(k-1)和q个星S_(k+1)的充要条件.

K_(1,7)与P_(6)的强积图的任意可分性

设G=(V,E)是n个顶点的简单图。序列λ=(λ_(1),λ_(2),·,λ_(p))满足λ_(1)+λ_(2)+·+λ_(p)=n,则序列λ被称为是可允许的序列。如果图G的顶点集V的一个划分(V_(1),V_(2),·,V_(p))满足|V_(i)|=λ_(i),i=1,2,·,p,且G[V_(i)]是连通的,则这个可允许的序列λ被称为是可表示的,并且称图G是λ-可分的。记K1,t是最大度为t的星,K1,t■Pn为星与路的强积图,图K1,7■P6是(1,λ_(2),·,λ_(p))-可分的。

两类非连通图(P_2∨■)(0,0,r_1,0,…,0,r_n)∪St(m)及(P_2∨■)(r_1+a,r_2,0,…,0)∪G_r的优美性

对自然数n,m,i∈N,设Ki表示i个顶点的完全图,■表示Kn的补图,St(m)表示m+1个顶点的星形树,Gr为有r条边的优美图,Pn为n个节点的路,P2∨■是P2与Kn联图。给出了非连通图(P2∨■)(r1,r2,0,…,0)∪St(m)及(P2∨■)(r1+a,r2,0,…,0)∪Gr的定义,并论证了当n≥2时,这两类图都是优美图。

星图和扇图的广义Mycielski图的星全染色

图G的一个正常全染色被称作G的星全染色,如果G中任意路长为2的点和边着色均不相同,则称它为图G的星K-全着色.图的全部星K-全着色中最小的数K称为它的星全色数.讨论了星图和扇图的广义Mycielski图的星全染色问题,得到了不同情况下它们的星全色数,其中每个点的色集合包含该点及其关联边的颜色.

多角度可交互的多维数据可视化方法

提出一种多维数据的可视化方法"旋转坐标系折线法",通过将Fisheye与星型法相结合,增强可交互性。针对不同可视化技术的特点,提出多角度交互连线法(MCA),将多种可视化方案相结合,从不同角度可视化多维数据。实验证明,该可视化方法可以分析数据进行聚类,评价聚类的准确性与可靠性,也能与用户灵活交互,可更清晰地将可视化效果呈现给用户。该方法已应用于EFCS_Grid网格系统中,达到了预期目标。

轮和路的广义Mycielski图的星全染色

图G的一个正常全染色被称作G的星全染色,如果G中任意路长为2的点和边着色均不相同.图的全部星k-全着色中最小的数k称为它的星全色数.讨论轮和路的广义Mycielski图的星全染色问题,得到不同情况下它们的星全色数,其中每个点的色集合包含该点及其关联边的颜色.

星形图上无死锁的路径算法

星形图具有许多良好的拓扑性质，是一种有可能替代传统的超立方体的并行计算互联网络的模型．在本文中，作者针对在星形图这样一种高度规则的网络中，可能产生死锁的问题，对星形图上无死锁的路径算法进行了研究．首先利用星形图中匹配基的性质，给出了从Sn（B）到Sk的正规映射的定义，然后提出了星形图上的两个无死锁受限条件，最后证明了一个满足无死锁受限条件的路径算法．作者还提出了星形图上路径算法的最小无死锁受限条件等，有待于进一步研究．

图C_7(r_1,r_2,r_3,r_4,r_5,0,0)∪St(m)的优美性

圈C7的(r1,r2,r3,r4,r5,0,0)-冠简记为C7(r1,r2,r3,r4,r5,0,0),St(m)表示有m+1个顶点或有m条边的星型树.讨论了C7(r1,r2,r3,r4,r5,0,0)与St(m)的非连通并集C7(r1,r2,r3,r4,r5,0,0)∪St(m)优美性,用构造性的方法给出了一些特殊的C7(r1,r2,r3,r4,r5,0,0)∪St(m)的优美标号.

组合星图的最优生成树

文章解决了组合星图生成树的构造问题。首先给出了组合星图的定义及其重要的拓扑性质,然后采用构造方法获得了组合星图的一棵高度为D(Sn,k)的生成树,并给出了相应的算法,其中D(Sn,k)为组合星图的直径。该生成树具有最优的高度,且是一棵贪婪树。

拟双星图的N-G型的代数连通度的界

文章利用图G的代数连通度与其线图的邻接谱半径之间的关系,给出:任n阶拟双星图G ,s0-1<a(G) +a(Gc) ,其中:s0= n0 k+s≥n-n0+1k+s-2k+s<n-n0+1 ,n0= N-2n=2N-1N-1n=2N 。

星型网络的3-限制边连通性

星型互连网络是并行与分布式处理领域中最流行的互连网络之一,它以n维星图作为拓扑结构。k-限制边连通度是衡量网络的可靠性的参数之一。一般来说,一个网络的k-限制边连通度越大,其连通性就越好。研究了星型互连网络的k限制边连通度;证明了当n≥3时,n维星型互连网络的3-限制连通度为3n-7。