3正则平面图的哈密顿圈

将一个图表示在一个平面上使各边除顶点外没有公共点时,称为平面图.如果平面图G含有通过所有顶点的圈(哈密顿圈),则称G为平面哈密顿图.研究化学结构的图形,尤其是3-正则平面图,确定它是否哈密顿图是个令人感兴趣的问题.Tait曾猜想每个3-正则3-连通的平面图都是哈密顿图.Tutte首先构成3-正则3-连通的反例,以后又有些人作出其他反倒,其中仿Tutte图构成的Lederberg图,具有38个顶点.     

平面图的圈基内插性质

图Ｇ的一个圈基的长度是该自基中所有圈的长度之和．设Ｃ－、Ｃ－分别是Ｇ的最小、最大圈基长度．如果对任一自然数Ｃ，Ｃ－＜Ｃ＜Ｃ－，都存在Ｇ的一个长为Ｃ的圈基，则称Ｇ有圈基内插性质．本文证明了无三角形的外平面图没有圈基内插性质，并说明存在围长任意大且有圈基内插性质的平面图．     

一类(0,1)矩阵变换图的Hamilton性

设G(R,S)表示m×n阶(0,1)矩阵类(R,S)的变换图.Brualdi提出问题:“G(R,S)有Hamilton圈吗?”当min{m,n}=2时,文献[3]中证明了此变换图是Hamilton连通的,并且是泛圈的(除K_1,K_2外),从而给该问题一个肯定的答案,当min{m,n}=3时,本文进一步地证明了此变换图是边Hamilton的(除K_1,K_2外),从而也给出该问题一个肯定的答案。     

混沌模拟退火最短路由算法的事后处理技术

基于混沌模拟退火神经网络的最短路径路由算法，虽然能有效地克服Hopfield神经网络易陷入局部最小值的缺点，但对节点数较多的网络，仍有缺陷。引进了一种事后修正机制，即在结果修正时，结合具体问题，充分考虑解的合法性，根据神经网络的输出矩阵，依次找到该行的最大值，确定与该节点相连的下一个最短路径节点。仿真结果显示既使网络节点数较多，这一算法仍运行良好且能以较大的概率找到全局最优解。     

有向圈的矩阵算法及有关性质

用矩阵方法讨论了有向图的连通性，阐述了计算有向圈的矩阵方法及有向图为Hamilton图的充要条件，最后给出了计算实例。     

关于3-可选平面图的一点注记

图G=（V,E）称为L-可染的,如果对给定的列表L={L（v）：v∈V（G））,存在图G的一个正常染色c,满足c（v）∈L（v）．如果对任何｜L（v）｜≥南的列表,图G都是L-可染的,则称图G为k-可选的．本文我们证明了平面图不含4圈,5圈,7圈和三角形距离小于2是3-可选的．     

由de Bruijn—Good图的1—因子构成的超立方体图

二元η级 de Bruijn-Good 图 G_n 在非线性移位寄存器的设计方面有着广泛的应用.它的每一个1-因子就是一个 n 级非奇异侈位寄存器.因而,研究由 G_n 的1-因子形成的图 M(G_n)具有实际的应用背景。本文给出了由 G_n 的1-因子形成的图 M(G_n)的构造,得到 M(G_n)同构于2~(n-5)-维的起立方体图,并由此给出一种方法去求得一切非奇异的移位寄存器,而且将它们排列在 M(G_n)的一个 Hamilton圈上.     

神经网络在逻辑阵布图中的应用

首先我们定义准连接向量,然后将一维逻辑阵布图问题归结为非正交准连接向量数目最小的优化问题,利用改进的Hopfield神经网络模型求解.最后给出嵌入线网的算法.     

路图P3(G)的色数

设G是一个图,G的路图P3(G)的顶点集是G中所有三个顶点的路P3, 当G中的两个P3路形成P4路或C3圈时,在P3(G)中它们所代表的两个顶点相邻. 在这篇文章中,我们得到对于一个无三角形的图G, χ(P3(G))≤β(G),其中β(G)表G的点覆盖数. 对于顶点数至少为3的连通图G,χ(P3(G))≤2当且仅当G是二部图, 并且χ(P3(G))=1当且仅当 G是星图. 对于K4的剖分图G,2≤χ(P3(G))≤3. 对于系列平行图和外可平面图G,χ(P3(G))≤3.     

面向表型精确鉴定的豆株快速三维重建

利用计算机视觉与图像技术对植物进行数字化重建是植物表型组学的重要手段。以国内常见的粮食作物豆类植株为研究对象，利用RGB-D深度相机采集的深度图像对豆株进行快速三维数字化重建，首先，基于点云分层聚类提取点云骨架点；然后，根据各骨架点到根节点的最短距离连接第一阶段的主干骨架点，并根据形态特征筛选子图和主干图的连接点、选择子图生长路径；最后，由连接骨架进行植物数字化建模。实验表明，基于真实大豆植株点云的单帧和配准数据，本文方法能对不同形态特征的大豆植株进行快速三维重建，并能对分辨率不高、噪音干扰较大、配准误差较大等情形做处理。     

二部图G的F－Hamilton问题

设Ｆ是二部图Ｇ的１－因子，如果Ｇ中有含Ｆ的Ｈａｍｉｌｔｏｎ图，则称Ｇ是Ｆ－Ｈａｍｉｌｔｏｎ的．本文给出了二部图Ｇ是Ｆ－Ｈａｍｉｌｔｏｎ的一个充要条件．     

哈林图的偶匹配可扩性

称图 G 的匹配 M 是偶匹配,如果 M 中的边关联的点集在 G 中的导出子图是偶图,即 G[V(M)] 是偶图. 称图 G 是偶匹配可扩的,如果 G 的每一个偶匹配 M 都包含在 G 的一个完美匹配中. 本文的主要结果是:哈林图 H=(T∪C)是偶匹配可扩的当且仅当它的特征树 T 同构于 K1,3、K1,5 或者 K1,7.     

一类Hamilton图的度序列

<正> 关于制断一个图是否是Hamilton的,到目前为止,还没有一个充要条件,这也是图论中尚未解决的一大难题。在无向图中,保证Hamilton图的存在性的充分条件较多,但概括起来,可以分为两大类:一类充分条件是Bondy和Chvatyl的闭包理论,一类是Chvatal的度序列条件。朱永津和刘振宏同     

一类Hamilton图的条件

本文给出一类Hamilton图的条件。它既不满足Bondy的闭包条件,也不满足Chvatal的度序列条件,而且不满足Bondy提出的Meta一猜想。文中所用的符号和术语主要采用〔1〕和〔2〕中的习惯用法。     

用Hopfield神经网络解哈密顿回路问题

设PN是一个圆的内接正N边形,圆的直径为1.将一个N个顶点的简单图G的每条边赋权,权重为PN的边长;对于图G中不邻接的各对顶点,先求出这对顶点最短路的长度,再赋予PN中同样长度的路的两端点的距离.如此,将图G的哈密顿回路问题转变成旅行商问题:周游回路最优解的长度是否等于正N边形的周长.为了用Hopfield神经网络方法得到正确的判定,简化了初始状态,引用了动态消元算法.     

关于四边形连通无爪图的注

文献【1】中,证明了没有1度点的每个四边形连通无爪图G如不包含同构于G1或G2（见图1）的导出子图日使得H中每个4度点x的N1（X,G）是不连通的,那么它是哈密尔顿的．然而,在文献【2】中,命题2．5和定理2．6的叙述和证明中存在一些问题．在本文中,给出了它们的正确表述以及改进了的证明．     

循环图的预解Estrada指标

Circulant graphs are an important class of network topology. Let G be a simple graph with n vertices, let A be the adjacency matrix of G, and λ₁,λ₂,…,λ_n be the eigenvalues of graph G. As a kind of centrality of complex networks, the resolvent Estrada index of G is defined as EE_r(G)=((1-λ_i)/(n-1))^-1. By Ramanujan's sum, using the Euler function and Mobius function, we characterize the lower bound of resolvent Estrada index of circulant graph, and obtain some computational formulas of integral circulant graphs.     

几类整循环图的秩的界

循环图是并行计算和分布式计算中一类重要的互联网络拓扑图,整循环图在支持完美状态传递的量子自旋网络模型中具有重要作用。图的秩定义为图的邻接矩阵的秩。利用Ramanujan和,借助Euler函数和Mobius函数,研究了几类整循环图的秩,得到了这些整循环图的秩的较为精确的界。