论文部分内容阅读
谱图理论主要研究图的谱性质和图的结构性质之间的关系，期望通过谱性质来刻画结构性质．图的邻接谱与Laplace谱一直是谱图理论中的研究热点．利用谱(尤其是谱半径)来刻画一些特殊的图类是国内外学者的关注的焦点．谱图理论在图像处理中发挥有效的作用．利用图的特征值与特征向量的性质，可以给出两幅图像特征点之间的对应关系． 本文主要研究两个方面的问题：(1)在所有给定最大度和阶数的树中，刻画具有最大谱半径的树；(2)利用图的最小生成树及其Laplace谱性质，给出图像特征点的匹配算法． 近年来，研究者对如下问题非常有兴趣，即在给定某个图参数的情形下，刻画极端的谱性质，如谱半径，代数连通度等．这些工作包括：在给定直径的树中，Kirkland与Neumann给出了代数连通度的一个下界，Fallat，Kirkland刻画出分别具有最大，最小代数连通度的树，Guo与Shao按照邻接谱半径对树进行排序；在给定最大度的树中，Lin与Guo刻画了具有最小邻接谱半径的树，并把树的排序进一步扩展，zhang，Li，Guo则根据Laplace谱半径对树进行排序． 在给定最大度的树中，我们应用顶点赋值的思想，给出了寻找具有最大邻接谱半径Laplacian谱半径的一种简单方法．相对于已有工作对图的特征多项式的大量计算，我们的方法避免了计算，运用纯粹组合安排的想法．此外，相对于已有结论对最大度的限制，我们的结果对一般的最大度成立． Scott和Longuet-Higgins首次将图谱方法应用于图像匹配分析．此方法后来被Shapiro，Brandy，Carcassoni，Myers等推广．这些工作的主要想法是：(1)构造赋权完全图，(2)获取赋权完全图的谱信息以刻画特征信息． 我们认为：赋权完全图强调任意两个节点之间都有权，信息丰富，但太多的信息往往会增加问题处理的复杂性。因此，从节约的角度，我们从赋权完全图中找出其最小生成树，对最小生成树获取其Laplace谱信息，进而实现特征匹配．模拟实验表明该算法对平移，旋转，缩放，仿射，射影变换都能有较好的匹配效果，而且对于真实的图像序列也能够获得较高的匹配精度．