利用对偶理论求解线性规划问题的策略探讨

利用对偶理论求解线性规划问题是教学中的重点及难点之一.本研究将从例子出发,分析互补松弛条件的使用方法,探讨求解线性规划问题的多种解题思路.

围长为g且有k个悬挂点的单圈图的谱半径和Laplacian谱半径

图的谱半径和Laplacian谱半径分别是图的邻接矩阵和Laplacian矩阵的最大特征值.本文中,我们分别刻画了围长为g且有k个悬挂点的单圈图的谱半径和Laplacian谱半径达到最大时的极图.

关于3-点临界图的一个猜想的证明

设γ(G)是图G的点控制数.如果对任意的v∈V(G),都有γ(Gv)<γ(G)成立,那么称G为γ-点临界图.本文主要给出Ananchuen和Plummer提出的一个猜想的证明,得到了如下的结果:若G是无K1,7的3-点临界图,且阶数为不小于18的偶数,则除几类特殊图外,G均有完美匹配.

图的匹配与拉普拉斯特征值

设G=(V(G),E(G))是一个图,M是E(G)的—个子集.如果M中任意两条边均无公共端点,则称M为图G的匹配.如果图G的一个匹配M中的边恰好关联G的每一个顶点,则称M为图G的完美匹配.如果图G中除了一个顶点以外,其他所有顶点都与匹配M中的边相关联,则称M为图G的几乎完美匹配.如果对任意v∈V(G), G-v均有完美匹配,则称G是因子临界的.本文中,我们给出了判定一个图有完美匹配、或者几乎完美匹配或者是因子临界的拉普拉斯谱条件.