λ阶短哈密顿回路的最小权法

提出短哈密顿回路的概念，分析由延长而形成最短哈密顿回路的特点，得出求权图G(n，m)λ阶短哈密顿回路的最小权法，该最小权法不但可精确求得最短和其它阶的短哈密顿回路，而且可用于权图G(n，m)的判别，得出求λ阶短路径的最小权法。     

λ阶短哈密顿回路的匹配法

无向权图G(n,m)的任始结点哈密顿回路可分成两条匹配半路径,根据给定λ值,用最小权路径延长法,对所有相关半路径进行匹配,便可完全确定从最短到λ阶短哈密顿回路的匹配法和相应的匹配算法.λ阶短哈密顿回路的匹配法可用于判别权图G(n,m)是否为哈密顿图.     

图的路径运算矩阵与哈密顿回路等路径问题

从简单图的邻接矩阵定义了初始路径运算矩阵和一般路径运算矩阵,并定义了一般路径运算矩阵的加法和乘法运算,通过这些运算可以直接求简单图的最长路、最短路、任意两点之间的通路及具有长度约束的路径问题,还可以检测简单图哈密顿回路及计算所有哈密顿回路,结果都显示在最后的路径运算矩阵上.证明了一般路径运算矩阵的幂长公式并得到了简单图...     

引入方向因子的最小回路、最大回路搜索算法

提出了最小回路、最大回路和方向因子的概念，基于方向因子构造了最小回路、最大回路搜索算法。算法依据图论知识，建立改进后的无向图邻接矩阵，根据节点坐标确定搜索始点，将搜索边失量化，结合节点坐标求解邻接边的方向因子，按方向因子的大小可以快速确定搜索边，形成了无向图中最小回路、最大回路搜索算法。该算法每搜索一次都可以确定一条搜索边，通过生成退化图减小下一次搜索的搜索范围，提高了搜索速度，反映出较小的时间复杂度。根据该算法编制了相应的算法程序，成功解决了建筑工程量计算中的外墙壁和房间划分问题。     

k-集合上与算术函数关联矩阵的行列式

设S={x1,…,xn}是由n个不同元素组成的正整数集合,f是一个算术函数.用(f(S))=(f(xi,xj))表示一个n×n的矩阵,其(i,j)项为f在xi与xj的最大公因子(xi,xj)处的取值,用(f[S])=(f[xi,xj])表示另一个n×n的矩阵,其(i,j)项为f在xi与xj的最小公倍数[xi,xj]处的取值.若xi与xj的最大公因子(xi,xj)=k,1≤i≠j≤n,则称S是k-集合.本文主要给出了定义在k-集合上的矩阵(f(S))和(f[S])的行列式的计算公式.进而作为推论给出了det(f(S))|det(f[S])的条件.     

因子链上幂矩阵行列式的整除性

设S＝{x1,……,xn}是由n个不同正整数组成的集合,ε∈Z ,如果n阶矩阵的第i行j列元素是S中元xi,xj的最大公因数(xi,xj)的ε次幂(xi,xj)ε,就称这个矩阵是定义在S上的最大公因数的ε次幂矩阵,简记为(S)εn;如果n阶矩阵的第i行j列元素是S中元xi,xj的最小公因倍数[xi,xj]的ε次幂[xi,xj]ε,就称这个矩阵是定义在S上的最小公倍数的ε次幂矩阵,简记[S]εn为.如果S中元素满足1≤i≤j≤n有xi|xj,就称S是一个因子链.研究了对ε∈Z ,定义在任意因子链S上的幂矩阵(S)εn和[S]εn的行列式det(S)εn与det[S]εn间的整除性.     

关于本原奇异数的注记

设S={x1,x2,…,xn}是由n个不同正整数的集合.以S中的任意两个元xi,xj,i=1,2,…,n,j=1,2,…,n的最小公倍数为i行j列元素的矩阵称为S上的最小公倍数矩阵(LCM矩阵),记为[S].S称为最大公因子封闭集(GCD closed),如果对于S中任意两个元xi,xj,它们的最大公因子(xi,xj)∈S.1992年,Bourque和Ligh猜想(以下简称BL猜想)GCD封闭集S上的LCM矩阵是非奇异的.1999年,Hong证明了该猜想对n≤7成立,但n≥8时不真,即对任意n≥8,存在G     

关于同构图在完全图中置入性的注记(英文)

一个具有m条边的n阶(n,m)图记为G(n,m),本文给了某些G(n,m)在K_n中是i一置入的必要条件,设△(G(n,m))表示G(n,m)中的最大点度.我们证明了下述命题“设G(n,n-l)不含长度为3或4的圈和孤立点,并且不连通.如果△(G(n,n- 1))≤ n-i,此处n>2i,那么 G(n,n-1)在K_n中是i-置入的.”是正确的当且仅当i=l,2,和3.     

关于最大公因子封闭集上的幂LCM矩阵的注记

设S={x1,…,xn}是由n个不同正整数组成的集合,e是一个实数. 如果对所有的1≤i,j≤n,有(xi,xj)∈S,则称S是最大公因子封闭的（GCD-closed）.第i行j列元素由xi和xj的最小公倍数的e次幂［xi,xj］e 构成的n×n 阶矩阵(［xi,xj］e）称为定义在S上的e次幂LCM矩阵. 作者证明了如果e≥1并且n≤7, 那么定义在最大公因子封闭集S上的幂LCM矩阵(［xi,xj］e)是非奇异的,从而证明了洪绍方教授2004年提出的一个猜想当n≤7,e≥1时是正确的.     

用分层关联方法求简单图中所有Hamilton回路的算法

研究简单图中所有的Ham ilton回路,不但可以判断简单图是否Ham ilton图,并且还可以得到简单图的所有的Ham ilton回路。首先在简单图中建立了初级通路的关联关系,并对初级通路的关联关系进行了分层,在此基础上,设计了求简单图中所有Ham ilton回路的算法。该算法利用简单图中长度为x的初级通路及长度为x的初级通路的分层关联关系逐步求长度为x 1的初级通路及长度为x 1的初级通路的分层关联关系的方法,求得简单图的所有Ham ilton回路。通过理论证明,该算法与已有的求简单图的所有Ham ilton回路的算法相比,原有的求简单图的所有Ham ilton回路算法中大量的重复计算被避免,从而提高了算法的效率。     

关于随机相交图中Hamilton圈的门限函数的注记

随机相交图G（n，m，p）的定义如下：记V为-n,顶点集．M-m个元素的集合．对每个顶点v∈V，赋予一随机子集Fv包含M，其中从M中独立以概率p选取每个元素构成Fv，顶点u和v之间有边相连当且仅当Eu∩Fv≠Ф．当m=n^a，a≠1时．C．Efthymiou和P．G．Spirakis得到了G（n，m，p）中Hamilton圈的门限函数．对于a=1情形，本文利用二阶矩方法（Chebyshev不等式）得到了类似结果．     

一类特殊的m限制边连通图

设G是一个连通图,F是G的一个边割,若G-F的每个连通分支至少有m个顶点,则称F是G的一个m限制边割.若图G存在m限制边割,则称图G是m限制边连通图.文章刻画了只含一个圈且长度为5的m限制边连通图.     

Geodetic图的几个定理

若图G中任一对不同顶点都有唯一的一条最短路,则称图G是geodetic图,在此条件下构造了几类geodetic图和讨论了具有Hamilton圈的geodetic图。     

舵轮图都是强协调图

一个有e条边的简单图G称为是强协调的,若有V(G)到{0,1,…,e-1}的单射h,使导出映射h~*:h~*(uv)=h(u)+h(v)是由E(G)到{1,2,…,e}的一个双射。舵轮图H_n是由含n个顶点的圈C_n内添加一个与C_n的每个顶点都相邻的顶点,且再在C_n的每个顶点上都添上一条悬挂边而得到的图。本文中证明了,所有舵轮图都是强协调图,因而回答了[2]中一个open问题。     

关于图的符号圈(点)控制

引入了图的符号圈(点)控制概念,给出了所有n阶极大平面图G(n≥3)的符号圈(点)控制数γsc(G)的一个下界,即γsc(G)≥(8n - 16 - n△)/△,并且此下界是最好可能的,获得了满足γsc(G)=∣V( G)∣ -2的所有连通图的一个特点.此外,还确定了几类特珠图的符号圈(点)控制数.     

两类图的边色数

设G是连通循环图.本文讨论两个与循环图有关的图类的边着色问题,得到了下列结论:①如G是奇素数幂阶循环图,则对G的任意点v,G-v是第一类的;②如G是奇数阶循环图,则G的线图L(G)是1-可因子化的,当且仅当G的边数为偶数。     

具有最小匹配能量的广义仙人掌图

为了研究具有最小匹配能量的广义仙人掌图的结构,利用一些图形变换对图的匹配能量产生影响的相关方法,得到了具有最小匹配能量的广义仙人掌图的结构:在所有顶点数、边数、块为圈的数目和块为双圈图的数目都固定的广义仙人掌图中,G﹡(n,m,r,s)是匹配能量最小的图;在所有顶点数和边数都固定的广义仙人掌图中,G﹡(n,m,1,(m-n)/2)或G﹡(n,m,0,(m-n+1)/2)是匹配能量最小的图。     

关于二分图的F-Hamilton性

设G是一个简单图,任意e∈E（G）,定义e=uv在G中的度d（e）=d（u）＋d（v）,其中d（u）和d（v）分别为顶点u和v在G中的度数。设F是二分图G的一个1-因子,如果G中有包含F的Hamilton圈,则称G是F-Hamilton的;给出了二分图是凡Hamilton的一个新的充分条件。     

6-连通图最长圈上的可收缩边

 图的可收缩边与可去边是研究连通图的构造和使用归纳法证明连通图一些性质的有力工具。设G是一个6-连通图,e∈E（G）,若收缩e后得到的图仍是6-连通的,则称e是G的可收缩边。采用树型结构理论进行分类讨论,得到如下结论：① 如果P:x=x1x2…xn=y是6-连通图G的一条最长（x,y）－路,xi xi+1是一条不可收缩边,且S={xi,xi+1,u1,u2,u3,u4}是其对应的6-点割,则G-S的每一个断片至少包含P上的一个点;② 设P:x=x1x2…xn=y是6-连通图G的一条最长（x,y）－路,且G的任意断片的阶都大于2。如果P上任意顶点xi都满足条件d（xi）≥7或者若d（xi）=6则[V（P）]中无3-圈包含它,那么P上至少包含一条可收缩边。在上述结论的基础上,进一步研究了任意断片阶都大于2的6-连通图中最长圈上的可收缩边的分布情况,得到如下新结果：任意断片阶都大于2的6-连通图最长圈上至少有两条可收缩边。     

具有第四小Hosoya指标的单圈图

用Z（G）表示图G的Hosoya指标,定义为图G的边的匹配数的总和,设“。表示”个顶点的单圈图集．一个充分悬挂的单圈图具有这样的性质：在它唯一圈上的任意一点的度不小于3．用un^1表示充分悬挂的单圈图集．在这篇文章中,确定了在un^1中有第四小Hosoya指标的图．