有限个或至多可数个存在某种关系的对象都可以用图模型来表示.图论主要研究这种模型所蕴藏的内部结构性质并借助图参数予以表达,但一些具有广泛应用前景的参数的计算复杂度属NPH或NPC问题.鉴于此,代数组合分析的方法在图的结构性质讨论中有着非常重要的意义.谱图理论即是借助图的矩阵表示的谱及特征空间,来刻画图自身的结构参数,是现代数学表示论观点的体现.本论文主要研究图的矩阵表示的极小非零特征值所对应的特征向量的组合结构性质,并推广到一般的特征向量.此外,本文把特征向量的组合结构性质应用于图划分问题.图的极端特征值,如谱半径和极小非零特征值,在刻画图参数方面发挥很好的作用.这些极端特征值的特征向量在刻画图的整体结构性质方面也发挥着同等的作用.1975年Fiedler给出了图的Laplace矩阵的次小特征值(称为代数连通度)所对应的特征向量(称为Fiedler向量)的组合结构性质.图的Fiedler向量的符号变化和数值增减变化可以窥测图的结构性质.1987年Merris根据Fiedler向量的符号变化提出特征集的概念(其中的元素称为特征元),证明了：任一个树的特征集都恰含一个特征元,并且该特征元与Fiedler向量的选取无关.1998年Bapat和Pati把特征集的概念推广至一般图,并给出特征集基数的一个上界.特别地对单圈图的Fiedler向量的结构性质给予刻画.在上述工作中,特征集定义于图的Laplace矩阵的次小特征值所对应的特征向量.2002年Pati把特征集引入到树的第三小特征值所对应的特征向量.然而,这些特征向量不再具有树的Fiedler向量所具有的性质,即特征集以及其基数与特征向量的选取有关.对于一个n阶图G,其Laplace特征值排序为：对应于G的特征向量Y,其特征集记为C(G,Y).为了讨论方便,我们称特征向量Y为图G的k-向量,如果Y对应于λk(G)且λk(G)>λk-1(G).因此,Fiedler向量是一个2-向量.Fiedler证明了：对一个树T,若其特征向量Y不含零分量且对应于λk(T),则λk膏(T)是单的且|C(T，Y)|=k-1.注意此结论中的Y是一个k-向量.事实上,对树的任一个k-向量Y,1≤|C(T,Y)|≤k-1.本文的工作之一是研究特征集或其基数的不变性.对于任意给定的k,是否存在树T,使得对任意的k-向量Y都有|C(T,Y)|=1?称满足上述条件的树为k-单树.我们的回答是肯定的,并给出了k-单树的等价条件.同时,我们发现,对于k-单树T,C(T,Y)也是不变的.这和Fielder向量的性质是一致的,因为任一个树都是2-单树.本文的另一个工作是研究特征集基数的极大性.对于树的不同k-向量,特征集可能是变化的.如果仅考虑极大基数的k-向量,其特征集是否还是变化的?称上述向量为k-极大向量.我们证明了：任一个k-向量的特征集都含于k-极大向量的特征集,因此k-极大向量的特征集是不变的.该结论和Fielder向量的性质也是一致的,因为Fielder向量是一个2-极大向量.混合图就是对简单图的部分边进行定向后所得到的图,在现实生活中有很多的应用背景.1999年Bapat等人引入了混合图的Laplace矩阵,并推广了经典的矩阵-树定理.2002年张晓东和李炯生讨论了混合图的Laplace谱,给出了谱半径的一些上界.考虑到奇异混合图的Laplace谱在本质上等同于经典的Laplace谱,2005年范益政讨论了非奇异的混合图的的最小特征值,并给出对应特征向量的组合结构性质.在该文中作者提出了一个公开问题,即给定腰长的非奇异单圈混合图的最小特征值达到极小的极图的刻画.本文专注于上述问题,把特征集拓展到非奇异混合图的Laplace最小特征值所对应的特征向量.我们给出了特征集的可能基数,并对特征元进行了刻画；应用该性质,获得了特征向量的符号变化；最终解决了范益政论文中所提的公开问题.本文的最后一部分就是把图的k-向量应用于图划分问题.图划分的目标就是把一个图分解成若干子图并受某种平衡约束,使得子图之间的互联代价或权值最小,在图像分割和聚类中得到了广泛应用.把一个图分成两个部分(即二划分),可采用经典的最大流-最小割定理.但考虑分割大小的平衡性,1992年Hagen和Kahng提出了比值割的度量准则,并利用图的Fiedler向量的结构性质给出分割方法.针对k-划分问题,1994年Chan，Schlag, Zien推广了比值割准则,应用图的Laplace矩阵的前k个特征向量实现划分.此外,2000年Shi和Malik提出了规范割的度量准则,应用图的规范Laplace矩阵的次小特征值的特征向量实现分割.本文应用k-向量的符号变化性质,提出一种新的k-划分方法.相比Fiedler向量只能实现二划分,k-向量可实现k-划分；与Chan-Schlag-Zien的方法相比,本方法节约运算量.实验也反映本算法有很好的划分效果.