运输问题图上作业法的破圈技巧

图上作业法是借助流向图进行物流合理规划的简便线性规划方法.对于有圈交通图,“舍边破圈”是用图上作业法解决平衡运输问题的关键.将对运输问题图上作业法的破圈技巧展开探讨,梳理了几种常用的破圈技巧,并通过若干反例说明了常用的破圈技巧其效果的不确定性,最后给出了相对合理可行的破圈调整技巧.     

图的Hamilton圈变换

本文给出图在矩阵上的H圈变换,由此得到图的最优H圈的充分必要条件和近似计算方法。     

一类恰含一个3-圈的三色本原有向图指数上界

在传统(单个)非负本原矩阵的基础上,将非负本原矩阵对的研究推广到非负本原矩阵簇,是组合矩阵论中一个崭新的研究内容.事实上,非负矩阵簇可以与多色有向图建立一一对应关系,从而把矩阵的问题转化为图的问题进行研究.该文研究了一类三色本原有向图,它的未着色图中包含n个顶点,一个n-圈、一个(n-1)-圈和一个3-圈,给出本原条件和指数上界.     

四圈图的拉普拉斯谱宽度

图的拉普拉斯谱宽度定义为图的拉普拉斯矩阵的最大特征值与第二小特征值的差.本文证明了,在所有n(n12)顶点四圈图中恰有11个拉普拉斯谱宽度最大的四圈图.     

有关完全图的图的紧性

双随机矩阵有许多重要的应用,紧图族可以看作是组合矩阵论中关于双随机矩阵的著名的Birkhoff定理的拓广,具有重要的研究价值.确定一个图是否紧图是个困难的问题,目前已知的紧图族尚且不多,给出了三个结果:任意多个完全图的不交并是紧图;圈C_3与圈C_n(n3)的不交并是非紧图;当n是大于等于3的奇数时,完全图K_n与图K_(n+1)的不交并是非紧图,其中图K_(n+1)是从完全图K_(n+1)删去一因子而得到的图.     

图的k-单圈划分中的优化问题

图的划分问题曾引起图论界的广泛关注，在文献[4]中讨论了k-单圈划分，本文进一步研究基于k-单圈划分的优化问题，即在一个赋权图中求一个最小权可k-单圈划分的支撑子图，以及对一个不存在k-单圈划分支撑子图的图，如何添最少的边使得它有k-单圈划分的支撑子图。     

不同类型的“追赶”法及其稳定性判别

“追赶”法是求解差分方程两点边值问题或条形矩阵(即只有几条对角线上的元素不为零的矩阵)线代数问题的有效解法。“追赶”法的主要问题是稳定性问题。在早期的工作[1,2]中,利用主对角线占优的性质证明了“追赶”法的稳定性。后来“追赶”法利用到求解比较一般的差分方程两点边值问题,并利用差分方程中系数矩阵的特征值性质证明了稳定性。在[3]中证明了:当差分方程两点边值问题是C-良态的,则正交“追赶”法是稳定的。直接利用问题的性态证明“追赶”法的稳定性是有意义的,因为有些差分方程     

一个给定图中Hamilton圈数的计算定理

众所周知,“一个图中有多少H圈”的问题是一个未解决的很困难的问题[1](其中H圈是Hamilton圈的简称)。我们约定本文讨论的图都是有限简单图,所用图论术语和记号凡不加定义的均采自参考文献[2]。用e(G)记图G的边数。当e(G)>e特别当e(G)很大而e很小时,直接数遍图G中的H圈是十分困难的。例如一个阶为20的圈G~*,其补     

恰有两个Q-主特征值的三圈图

图G的无符号拉普拉斯矩阵定义为图G的邻接矩阵与度对角矩阵的和,其特征值称为图G的Q-特征值.图G的一个Q-特征值称为Q-主特征值,如果它有一个特征向量其分量的和不等于零.确定了所有恰有两个Q-主特征值的三圈图.     

基于仿射传播的道路网络聚类

对于道路网络聚类问题,提出了仿射传播算法。首先,将道路网络上的交叉路口和结点作为顶点,建立了无向图;然后,根据最短路径计算网络距离,进而得到图的相似度矩阵;并基于仿射传播算法对道路网络进行聚类;最后,试验结果证实了本文方法的有效性与稳定性。