基于局部相对形状上下文与Q-谱的点模式匹配算法

本文提出了一种基于局部相对形状上下文与Q-谱的点模式匹配算法,对每个点构造相应的线图,并对线图的无符号Laplacian矩阵进行谱分解;利用谱分解所获得的特征值(Q-谱)作为点的特征,进而计算点的初始匹配概率;通过定义局部相对形状上下文计算点的相似性距离;将Q-谱方法与局部相对形状上下文结合进行概率松弛迭代获得匹配结果.实验结果表明了本文算法的可行性与有效性.

图的Laplacian谱半径界的可达性

设G为n阶连通的简单图 ,ρ(G)为图G的邻接谱半径 ,μ(G)表示G的Laplacian谱半径。(d1,d2 ,… ,dn) (其中d1≥d2 ≥…≥dn)为G的顶点度序列 ,令r=max{d(u) +d(v) ｜ (u ,v) ∈E(G) } =d(x) +d(y) ,s=max{d(u) +d(v)｜ (u ,v) ∈E(G) - (x ,y) }。该文证明了μ(G)上下界的可达性 :μ(G) =μ≤ 2 + ρ(LG) ,等式成立当且仅当G是偶图。μ(G)≤ 2 + (r- 2 ) (s- 2 ) ,成立等式当且仅当G为半正则偶图或P4 。μ(G)≥d1+ 1,成立等式当且仅当d1=n- 1。

完全等部二分图k_(n,n)的迭线图L^m(k_(n,n))的谱特征

研究了完全等部二分图kn ,n 的迭线图Lm(kn ,n)的谱特征 ,证明了当n≥ 7时 ,Lm(kn ,n)

二部半正则图的谱

本文给出二部半正则图的补图、全图、剖分图等的特征多项式公式 。

几类整谱图

研究二部半正则图的补图、二部补图的特征多项式公式 ,给出几个特殊图类的谱 ,得到几类整谱图的充要条件及一些新的整谱图类 .

用超广义线图构造整谱图

线图在图的谱理论研究中起着重要的作用.在本文中,通过研究超广义线图成为整谱图的充分条件,获得了一种全新的构造新的整谱图的方法,运用这种方法,可以构造出无穷多个新的整谱图.

完全二部图K_(a,b)的迭线图L^m(K_(a,b))的谱特征

本文证明了当 (a,b) { (1,8) ,(2 ,4 ) ,(3,6 ) ,(4 ,4 ) ,(2 s2 - s,2 s2 +s) }时 ,Lm (Ka,b)以谱为特征 ,其中 a b,s 2 .

关于图C_r［S_n］的线图L（C_r［S_n］）的谱特征

研究图Ｃｒ［Ｓｎ］的线图Ｌ（Ｃｒ［Ｓｎ］的谱特征，并证明当ｎ≥５时，Ｌ（Ｃｒ［Ｓｎ］）以谱为特征，这里ｒ为奇数。

连通偶图的Laplacian矩阵的第二大特征值

给出仅依赖阶数的连通偶图的Laplacian矩阵的第二大特征值的界 ,并刻划达到上。

图H_n(C_p,P_s,K_(1,q))的Laplacian谱刻画

针对图的谱确定问题,在图Cp,Ps,K1,q的基础上定义了一类新图,符号表示为Hn(Cp,Ps,K1,q),它是通过重合Ps的一个悬挂点与Cp的任意一个点、另一个悬挂点与K1,q的中心点得到的顶点数为n=p+q+s-1的图.首先,找到并证明了当s=2时此类图存在一对L-同谱图.然后,利用二分图的Laplacian谱与其对应线图的邻接谱的性质,证明了当s≥3且p为偶数时,图Hn(Cp,Ps,K1,q)由Laplacian谱确定.

图与其补图的Q谱半径之和的界

本文给出了图与其补图Q谱半径之和的一个上界,并给出了半正则二部图与其补图Q谱半径之和的上下界。

平方根图的一个充要条件

应用图与线图之间的特定联系,得出了平方根图的一个充要条件,进一步完善了平方根图的刻画。

关于二分图的线连通度的一个结论

在 Chartrand.G和 Lesniak关于图的线连通性定理的基础上 ,讨论二分图的线连通度问题 ,得到结论 :若 G =(X ,Y;E)是二分图 ,对任意一对不相邻的点 u、v,d(u) + d(v) >[p/ 2 ],则λ(G) =δ(G)

关于无爪图的线图的一个注记

根据无爪图及其线图的定义,发现无爪图线图的顶点数P与边数q满足q≤[(p2)/4.]

半正则混合图的线图的谱

给一个无向图的某些边定向得到的图称为混合图,它可能既存在无向边又存在有向边.一个无向半正则图 G 的线图 l(G)的邻接谱完全由 G 的邻接谱确定.主要推广了前面这个结果,证明了半正则混合图 G 的线图 l(G)的H-邻接谱完全由混合图 G 的H-邻接谱确定.

给定条件下的半正则连通二部图的刻画

主要研究在给定二部图两部顶点数的条件下,刻画了边数最少的半正则连通二部图.

基于改进齐套零件策略的车辆装配线新型物料配送调度

为了有效地解决汽车混流装配线物料供应的调度问题,提出了一种新型的基于线边超市的物料供应调度方法.首先,进行了问题域的形式化描述,同时确定了研究对象的一些假设,并建立了整数规划数学模型.而后,针对线边超市物料供应调度问题提出了改进齐套零件策略,为了求解该策略下物料超市补货任务的调度问题,构建了基于图论的模型以将调度问题转化为更容易精确定义和求解的数学问题,采用精确算法对目标函数进行优化.最后,对算法进行了仿真实验,结果表明调度算法是可行、有效的.