线型/圈型网络上单台车辆分群调度问题

本文研究线型/圈型网络上单台车辆分群调度问题。给定一个线型/圈型网络,若干客户分布其中。所有客户被划分成若干个子集,每个子集称为一个群。每个客户有一个释放时间和一个服务时间。给定一台车辆,其需要服务所有客户,且每个群内的客户连续服务。问题的要求是计算一个时间表,使得车辆能够按要求服务完所有客户并返回初始出发位置所花费的时间最少。针对该问题,就线型网络和圈型网络,分别给出一个7/4和一个13/7近似算法。     

平面图的强边染色

图$G$的强边染色是在正常边染色的基础上, 要求距离不超过$2$的任意两条边染不同的颜色, 强边染色所用颜色的最小整数称为图$G$的强边色数。本文首先给出极小反例的构型, 然后通过权转移法, 证明了$g(G)\geq5$, $\Delta(G)\geq6$且$5$-圈不相交的平面图的强边色数至多是$4\Delta(G)-1$。     

k圈图的最大Laplace分离度

设$ G $是一个$ n $阶$ k $圈图, $ k $圈图为边数等于顶点数加$ k-1 $的简单连通图。$ \mu_{1}(G) $、$ \mu_{2}(G) $分别记为图$ G $的Laplace矩阵的最大特征值和次大特征值, 图$ G $的Laplace分离度定义为$ S_{L}(G)=\mu_{1}(G)-\mu_{2}(G) $。本文研究了给定阶数的$ k $圈图的最大Laplace分离度, 并刻画了相应的极图, 其结果推广了已有当$ k=1, 2, 3 $时的结论。     

图的字典序积和自同态幺半群

Ｆ．Ｈａｒａｒｙ￣［１］和Ｇ．Ｓａｂｉｄｕｓｓｉ￣［２］考虑过图Ｘ和ｙ的字典序积Ｘ［Ｙ］的自同构群ＡｕｔＸ［Ｙ］与它们各自的自同构群的圈积ＡｕｔＸ［ＡｕｔＹ］的关系，并给出了两者相等的一种刻划．在本文，我们考虑更广意义上的问题，即Ｘ［Ｙ］的自同态幺半群ＥｎｄＸ［Ｙ］与各自的自同态幺半群的圈积ＥｎｄＸ［ＥｎｄＹ］的关系，也给出了两者相等的一种刻划，同时得到了下面结果：如果Ｘ和Ｙ都是不含Ｋ＿３导出子图的连通图，且其中之一图有奇数围长，那么ＥｎｄＸ［Ｙ］＝ＥｎｄＸ［ＥｎｄＹ］．     

若干运算图的倍乘赋权Harary指标

ALIZADEH等近期提出了一个修正的Harary指标,即顶点对的贡献被赋予其度的乘积.其指标被称为倍乘赋权Harary指标,定义为H_M（G）=Σ_u≠v（δ_G（u）δ_G（v））（d_G（u,v））,其中,δ_G（u）表示顶点u在图G中的度,d_G（u,v）表示2个顶点u和v在图G中的距离.给出了张量积G×K_r,强积GK_r,圈积G₁oG₂的倍乘赋权Harary指标值的精确计算公式,这些公式与图的其他不变量（如倍加赋权Harary指标、Harary指标、第1类和第2类Zagreb指标、第1类和第2类反Zagreb指标）有关.此外,利用所得结果计算了开栅栏与闭栅栏的倍乘赋权Harary指标.     

带弦有向圈的2级合成

考察带一条弦的有向圈的2级合成图,得到了它们强连通的充要条件,这些结果被用于判定布尔矩阵组合合成的本原性。     

基于K图的函数RM展开式在固定极性下的最小化

分析了K图的性质，发现在K图中过某格的所有聚合圈相应的各乘积项所含变量与该格对应的最小项均有相同的极性，在此基础上提出了得到基于K图函数RM展开式在固定极性下的最小化的图形方法，该方法可以从K图直接得到函数的最小化的RM展开式，从而省略了传统的把K图转变为bj图再求最小化的步骤，它具有直观、简单、易于掌握等特点。此外，文中还提出了该方法的改进算法。     

图论在离散事件动态系统中的应用

运用图论方法和极大代数方法,研究了非强连通图中的强连通分支的最大圈长平均值与该图的赋权邻接矩阵的特征值之间的关系,并进一步证明了其等价性.     

既不含4-圈又不含6-圈的平面图的非正常染色

设d₁, d₂,..., d_k是k个非负整数. 若图G=(V,E)的顶点集V能被剖分成k个子集V₁, V₂,...,V_k, 使得对任意的i=1, 2,..., k, V_i的点导出子图G[V_i] 的最大度至多为d_i, 则称图G是(d₁, d₂,...,d_k)-可染的. 本文证明既不含4-圈又不含6-圈的平面图是(3, 0, 0)-和(1, 1, 0)-可染的.     

图的Smarandachely邻点无圈边色数的一个上界

提出了图的Smarandachely邻点无圈边染色的概念,讨论了图的Smarandachely 邻点无圈边染色与邻点可区别无圈边染色之间的关系,并运用概率方法得到了图G的Smarandachely邻点无圈边色数的一个上界,其中G为无孤立边的图.