图的特征向量的组合结构
|
摘要
有限个或至多可数个存在某种关系的对象都可以用图模型来表示.图论主要研究这种模型所蕴藏的内部结构性质并借助图参数予以表达,但一些具有广泛应用前景的参数的计算复杂度属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的方法相比,本方法节约运算量.实验也反映本算法有很好的划分效果.
Finite or at most countable objects can be represented as a graph model if there exist relation between them. Graph theory mainly studies the nature of the internal structure of such a model and express using graph parameters. However, the computational complexity of some parameters for which have broad application prospects is NPH or NPC problem. Henceforth, the method of algebraic combinatorial analysis plays an important role on the reasch of the structural properties of a graph. Spectral graph theory describe its own structural parameters in terms of the spectrum and the eigenspace of the matrix corresponding to a graph, which reflects the view of the representation theory of modern mathematics. In this thesis, we mainly study the combinatorial structural properties of the eigenvectors corresponding to nonzero eigenvalues of the matrices of a graph, and extend those results to the general eigenvectors. In addition, the combinatorial structural properties of the eigenvectors will be applied on the graph partitioning problem.
The extreme eigenvalues, such as the spectral radius and the least nonzero eigenvalue, play an important role on the characterization of the graph parameters. Simultaneously, the eigenvectors corresponding to those extreme eigenvalues are also important to discuss the global structural properties of a graph. In 1975, Fiedler gives the combinatorial struc-tural properties of the eigenvectors (known as Fiedler vector) corresponding to the least nonzero eigenvalues(known as algebraic connectivity) of the Laplacian matrix of a graph. The structural property of a graph can be looked into the diversification of the signs and the values of its Fiedler vectors. Based on the changing of the signs of the Fiedler vec-tors, Merris introduce the concept the characteristic set in 1987(its elememts are called the characteristic elememts), and show that, for any tree, its characteristic set contains exactly one characteristic element, and such a characteristic element is fixed, regardless the chose of the Fiedler vectors. In 1998, Bapat and Pati extend the characteristic set to a general graph and give a upper bound on the cardinality of the characteristic set. In par-ticular, they also characterize the structural property of the Fiedler vectors of an unicyclic graph. In 2002, Pati extends the characteristic set to the eigenvectors corresponding to the third least eigenvalue of the Laplacian matrix of a graph. However, those eigenvectors of a tree no longer have the nature as that of its Fiedler vector, i.e., both the characteristic set and its cardinality are related on the chose of its eigenvectors.
For a graph G on n vertices, suppose its Laplacian eigenvalues are arranged as follows: Denote by C(G, Y) the characteristic set with respect to the eigenvector Y of G. For convenience, we call eigenvector Y is aκ-vector of G if the eigenvalueλκ(G) associated by Y satisfyingλκ(G)>λκ-1(G). Obviously, each Fiedler vector is a 2-vector. Fiedler show that, for a tree T,|C(T, Y)|=κ-1 if each entry of the eigenvector Y corresponding toλκ(T) is different to zero. Note that such an eigenvector Y is aκ-vector. In fact, with respect to anyκ-vector Y of a tree T, we have 1≤|C(T, Y)|≤κ-1.
Studying the invariance of the characteristic set and its cardinality is one of the main work of this thesis. For a given integerκ, whether there exists a tree T such that |C(T, Y)|= 1 with respect to its anyκ-vector Y? Such a tree is called aκ-simple tree. Our answer is positive and an equivalent condition forκ-simple trees is also expored. At the same time, we find that, for anyκ-simple tree T, C(T, Y) is fixed, which is consistent to the property of that of its Fiedler vector, since each tree is 2-simple.
Another main work of this thesis is investigation the maximality of the cardinality of the characteristic set. For a given tree, the characteristic set with respect to differentκ-vectors may change. However, whether the characteristic set would be change? If we only consider theκ-vectors for which maximizes the the cardinality of the characteristic set. The vector mentioned above is called theκ-maximal vector. We show that the characteristic set with respect to eachκ-vector is contained in the characteristic set with respect to anyκ-maximal vector. Hence, the characteristic set with respect to any k-maximal vector is fixed, which is consistent to the property of that of its Fiedler vector, since each Fiedler vector is a 2-maximal vector.
In our real life, there are many application backgrounds on the mixed graph, for which is obtained from a simple graph by oriented some of its edges. In 1999, Bapat et.al. introduce the Laplacian matrix of a mixed graph and generalize the classical Matrix-Tree Theorem. In 2002, X. D. Zhang and J. S. Li study the spectrum of a mixed graph and give a upper bound on its spectral radius. In 2005, taking into account the Laplace spectrum of singular mixed graph is essentially equivalent to the classical Laplace spectrum, Y. Z. Fan discuss the least eigenvector of nonsingular mixed graphs and characterize the com-binatorial structural properties of the eigenvectors corresponding to this eigenvalue. In addition, an open problem is posed in that paper, i.e., how to characterize the nonsingu-lar unicyclic mixed graph(s) which minimizes the least eigenvalue among all nonsingular unicyclic mixed graphs with fixed order and girth.
This thesis focuses on this question. We extend the characteristic set to the eigenvec-tor corresponding to the least eigenvalue of the Laplacian matrix of a mixed graph. We give the possible cardinality of the characteristic set and characterize its characteristic el-ements. Applying those properties, we obtained the change of the signs of this eigenvector and resolve this open problem finally.
In the last section, we apply the structural property of theκ-vectors on graph par-tition problem. The main goal of graph partition is to decompose a graph into several subgraphs and is subject to a balance constraint minizing the price or weight among them. It is widely used on the image segmentation and clustering. Based on the classical max-imum flow-minimum cut theorem, decomposition a graph into two subgraphs (i.e., two partition) can be accomplished. In 1992, considering the size of the balance decomposition, Hagen and Kahng propose the ratio cut criteria and introduce a graph partition method based on the structural property of Fiedler vectors. Forκ-partition problem, Chan, Schlag and Zien generalize the ratio cut criteria in 1994 and decompose a graph based on the first k eigenvectors of the Laplacian matrix of a graph. In addition, Shi and Malik propose the normal cut criteria in 2000, and decompose a graph based on the eigenvectorcorrespond-ing to least nonzero eigenvalue of the normal Laplacian matrix of a graph. based on the property of the change of the signs ofκ-vector, we propose a newκ-parpition method. Compared with Fiedler vector can only achieve two partition,κ-vector can accomplishκ-partition. Compared with Chan-Schlag-Zien method, our method can save computation. Experiment also reflects that our method has a good effect.
图的极端特征值,如谱半径和极小非零特征值,在刻画图参数方面发挥很好的作用.这些极端特征值的特征向量在刻画图的整体结构性质方面也发挥着同等的作用.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的方法相比,本方法节约运算量.实验也反映本算法有很好的划分效果.
Finite or at most countable objects can be represented as a graph model if there exist relation between them. Graph theory mainly studies the nature of the internal structure of such a model and express using graph parameters. However, the computational complexity of some parameters for which have broad application prospects is NPH or NPC problem. Henceforth, the method of algebraic combinatorial analysis plays an important role on the reasch of the structural properties of a graph. Spectral graph theory describe its own structural parameters in terms of the spectrum and the eigenspace of the matrix corresponding to a graph, which reflects the view of the representation theory of modern mathematics. In this thesis, we mainly study the combinatorial structural properties of the eigenvectors corresponding to nonzero eigenvalues of the matrices of a graph, and extend those results to the general eigenvectors. In addition, the combinatorial structural properties of the eigenvectors will be applied on the graph partitioning problem.
The extreme eigenvalues, such as the spectral radius and the least nonzero eigenvalue, play an important role on the characterization of the graph parameters. Simultaneously, the eigenvectors corresponding to those extreme eigenvalues are also important to discuss the global structural properties of a graph. In 1975, Fiedler gives the combinatorial struc-tural properties of the eigenvectors (known as Fiedler vector) corresponding to the least nonzero eigenvalues(known as algebraic connectivity) of the Laplacian matrix of a graph. The structural property of a graph can be looked into the diversification of the signs and the values of its Fiedler vectors. Based on the changing of the signs of the Fiedler vec-tors, Merris introduce the concept the characteristic set in 1987(its elememts are called the characteristic elememts), and show that, for any tree, its characteristic set contains exactly one characteristic element, and such a characteristic element is fixed, regardless the chose of the Fiedler vectors. In 1998, Bapat and Pati extend the characteristic set to a general graph and give a upper bound on the cardinality of the characteristic set. In par-ticular, they also characterize the structural property of the Fiedler vectors of an unicyclic graph. In 2002, Pati extends the characteristic set to the eigenvectors corresponding to the third least eigenvalue of the Laplacian matrix of a graph. However, those eigenvectors of a tree no longer have the nature as that of its Fiedler vector, i.e., both the characteristic set and its cardinality are related on the chose of its eigenvectors.
For a graph G on n vertices, suppose its Laplacian eigenvalues are arranged as follows: Denote by C(G, Y) the characteristic set with respect to the eigenvector Y of G. For convenience, we call eigenvector Y is aκ-vector of G if the eigenvalueλκ(G) associated by Y satisfyingλκ(G)>λκ-1(G). Obviously, each Fiedler vector is a 2-vector. Fiedler show that, for a tree T,|C(T, Y)|=κ-1 if each entry of the eigenvector Y corresponding toλκ(T) is different to zero. Note that such an eigenvector Y is aκ-vector. In fact, with respect to anyκ-vector Y of a tree T, we have 1≤|C(T, Y)|≤κ-1.
Studying the invariance of the characteristic set and its cardinality is one of the main work of this thesis. For a given integerκ, whether there exists a tree T such that |C(T, Y)|= 1 with respect to its anyκ-vector Y? Such a tree is called aκ-simple tree. Our answer is positive and an equivalent condition forκ-simple trees is also expored. At the same time, we find that, for anyκ-simple tree T, C(T, Y) is fixed, which is consistent to the property of that of its Fiedler vector, since each tree is 2-simple.
Another main work of this thesis is investigation the maximality of the cardinality of the characteristic set. For a given tree, the characteristic set with respect to differentκ-vectors may change. However, whether the characteristic set would be change? If we only consider theκ-vectors for which maximizes the the cardinality of the characteristic set. The vector mentioned above is called theκ-maximal vector. We show that the characteristic set with respect to eachκ-vector is contained in the characteristic set with respect to anyκ-maximal vector. Hence, the characteristic set with respect to any k-maximal vector is fixed, which is consistent to the property of that of its Fiedler vector, since each Fiedler vector is a 2-maximal vector.
In our real life, there are many application backgrounds on the mixed graph, for which is obtained from a simple graph by oriented some of its edges. In 1999, Bapat et.al. introduce the Laplacian matrix of a mixed graph and generalize the classical Matrix-Tree Theorem. In 2002, X. D. Zhang and J. S. Li study the spectrum of a mixed graph and give a upper bound on its spectral radius. In 2005, taking into account the Laplace spectrum of singular mixed graph is essentially equivalent to the classical Laplace spectrum, Y. Z. Fan discuss the least eigenvector of nonsingular mixed graphs and characterize the com-binatorial structural properties of the eigenvectors corresponding to this eigenvalue. In addition, an open problem is posed in that paper, i.e., how to characterize the nonsingu-lar unicyclic mixed graph(s) which minimizes the least eigenvalue among all nonsingular unicyclic mixed graphs with fixed order and girth.
This thesis focuses on this question. We extend the characteristic set to the eigenvec-tor corresponding to the least eigenvalue of the Laplacian matrix of a mixed graph. We give the possible cardinality of the characteristic set and characterize its characteristic el-ements. Applying those properties, we obtained the change of the signs of this eigenvector and resolve this open problem finally.
In the last section, we apply the structural property of theκ-vectors on graph par-tition problem. The main goal of graph partition is to decompose a graph into several subgraphs and is subject to a balance constraint minizing the price or weight among them. It is widely used on the image segmentation and clustering. Based on the classical max-imum flow-minimum cut theorem, decomposition a graph into two subgraphs (i.e., two partition) can be accomplished. In 1992, considering the size of the balance decomposition, Hagen and Kahng propose the ratio cut criteria and introduce a graph partition method based on the structural property of Fiedler vectors. Forκ-partition problem, Chan, Schlag and Zien generalize the ratio cut criteria in 1994 and decompose a graph based on the first k eigenvectors of the Laplacian matrix of a graph. In addition, Shi and Malik propose the normal cut criteria in 2000, and decompose a graph based on the eigenvectorcorrespond-ing to least nonzero eigenvalue of the normal Laplacian matrix of a graph. based on the property of the change of the signs ofκ-vector, we propose a newκ-parpition method. Compared with Fiedler vector can only achieve two partition,κ-vector can accomplishκ-partition. Compared with Chan-Schlag-Zien method, our method can save computation. Experiment also reflects that our method has a good effect.
引文
[1]W. N. Anderson and T. D. Morley. Eigenvalues of the Laplacian of a graph, Linear Algebra and Multilinear Algebra,18(1985):141-145.
[2]J.E. Atkins, E.G. Boman and B. Hendrickson, A spectral algorithm for seriation and the consecutive ones problem, SIAM J.Comput.28(1)(1998):297-310.
[3]R. Bach, M. I. Jordan, Learning spectral clustering. University of California at Berkeley Technical report UCB/CSD-03-1249.2003.
[4]R. B. Bapat,J. W. Grossman, D. M. Kulkarni, Generalized matrix tree theorem for mixed graphs, Linear and Multilinear Algebra,46(1999):299-312.
[5]R. B. Bapat, J. W. Grossman, D. M. Kulkarni, Edge version of the matrix tree theorem for trees, Linear and Multilinear Algebra,47(2000):217-229.
[6]R. B. Bapat and S. Pati, Algebraic connectivity and the characteristic set of a graph, Linear and Multilinear Algebra,45(1998):247-273.
[7]L. W. Beineke and R. J. Wilson,Selected Topics in Graph Theory, Academic Press, London, 1978.
[8]J. A. Bondy and U. S. R. Murty, Graph theory with applications, the Macmillan Press, London,1976.
[9]B. Bollobas, Modern Graph Theory, Springer Verlag, New York,1998.
[10]D. M. Cardoso, D.Cvetkovic, P. Rowlinson, S. K. Simi, A sharp lower bound for the least eigenvalue of the signless Laplacian of a non-bipartite graph, Linear Algebra Appl., 429(2009):2770-2780.
[11]P. K. Chan, M. D. F. Schlag, J. Y. Zien, Spectral k-way ratio-cut partitioning and clustering. IEEE Trans Comput-Aided Des Integr Circuits syst,13(9)(1994):1088-1096.
[12]M. F. Chen, F. Y. Wang, Cheeger's inequalities for general symmetric forms and existence criteria for spectral gap, The Annals of Probability,28(1)(2000):235-257.
[13]Fan R. K. Chung, Spectral Graph Theory, in CBMS,1997.
[14]D. Cvetkovic, P. Rowlinson, S.K. Simic, Signless Laplacians of finite graphs, Linear Algebra Appl.,423(2007):155-171.
[15]D. Cvetkovic, P. Rowlinson, S.K. Simic, Eigenvalue bounds for the signless Laplacian, Publ. Inst. Math. (Beograd),81(95)(2007):11-27.
[16]D. Cvetkovic, P. Rowlinson and S. Simic, Eigenspace of Graphs, Cambridge University Press, Cambridge,1997.
[17]D. Cvetkovic, Doctoral Thesis:Graphs and their spectra, Univ. Beograd, Publ. Elektrotehn. Fak.,Ser. Mat. Fiz.,354(1971):1-50.
[18]D. Cvetkovic. M. Doob,I. Gutman and A. Torgasev, Recent Results in the Theory of Graph Spectra, North Holland, Amersterdam,1988.
[19]D. Cvetkovic, M. Doob and H. Sachs, Spectra of graphs-Theory and Application,2nd ed., VEB Deutscher Verlag d.Wiss., Berlin,1982.
[20]D. Cvetkovic and I. Gutman, The algebraic multiplicity of the number zero in the spectrum of a bipartite graph, Mat. Vesnik,9(24)(1972):141-150.
[21]C. H. Q. Ding, X. He, H. Zha, et al. A min-max cut algorithm for graph partitioning and data clustering. In:Cercone N, Lin T Y,Wu X, eds. ICDM 2001. Los Alamitos, California: IEEE Computer Society,2001.107-114.
[22]C. H. Q. Ding, X, He, H. Zha, A spectral method to separate disconnected and nearly-disconnected web graph components. In:Provost F, Srikant R, eds. Proceedings of the Seventh ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York:Association for Computing Machinery,2001.275-280.
[23]Y.Z. Fan, S.C. Gong, Y. Wang and Y.B. Gao, On trees with exactly one characteristic element, Linear Algebra Appl,421(2007):233-242.
[24]Y. Z. Fan, Largest eigenvalue of a unicyclic mixed graph, Applied Mathematics A Journal of Chinese. Universities (English Series),19(2004):140-148.
[25]Y. Z. Fan, On the least eigenvalue of a unicyclic mixed graph, Linear and Multilinear Algebra,53(2005):97-113.
[26]Y. Z. Fan, On spectral integral variations of mixed graphs, Linear Algebra Appl.,374(2003): 307-316.
[27]Y. Z. Fan, S. C. Gong, Y, Wang, Y. B. Gao, First eigenvalue and first eigenvectors of a nonsingular unicyclic mixed graph,Discrete Math.,309(8)(2009):2479-2487.
[28]Y. Z. Fan, J. S. Li, On graphs with small number of Laplacian eigenvalue greater than two. Linear Algebra Appl,360(2003):207-213.
[29]Y. Z. Fan, H. Y. Hong, S. C. Gong and Y. Wang, Order unicyclic mixed graphs by spectral radius. Australasian Journal of Combinatiorics,37(2007):305-316.
[30]S. Fallat, S. Kirkland. Extremizing algebraic connectivity subject to graph theoretic con-straints, Electronic Journal of Linear Algebra,3(1998):48-74.
[31]S. Fallat, S. Kirkland and S. Pati, Minimizing algebraic connectivity over connected graphs with fixed girth, Discrete Mathematics,254(2002):115-142.
[32]S. Fallat, S. Kirkland and S. Pati, Maximizing algebraic connectivity over unicyclic graphs, Linear and Multilinear Algebra,51(2003):221-241.
[33]M. Fiedler, Algebraic connectivity of graphs, Czechoslovak Math.J.,23(1973):298-305.
[34]M. Fiedler, A property of eigenvectors of nonnegative symmetric matrices and its applica-tions to graph theory. Czechoslovak Math. J.,25(1975):607-618.
[35]S. Fiorini, I. Gutman, I. Sciriha. Trees with maximum nullity, Linear Algebra Appl. 397(2005):245-251.
[36]W. C. Forsrnan, Graph theory and the statistics and dynamics of polymer chains, J.Chem.Phys.,65(1976):4111-4115.
[37]C. Fowlkes. S. Belongie, F. Chung, et al. Spectral grouping using the Nystrom method. IEEE Trans Pattern Anal Mach Intell,26(2)(2004):214-25.
[38]C.D.Godsil, Algebraic Combiantorics, Chapman & Hall, New York,1993.
[39]S.C. Gong and Y.Z. Fan, The Property of Maximal Eigenvectors of Trees, Linear and Multilinear Algebra 58(1)(2010):105-111.
[40]S. C. Gong, Y. Z. Fan, On trees with exactly one characteristic element corresponding to k-vector, The Proceedings of the Seventh International conference on Matrix Theorey and its Applications,2006:300-303.
[41]S.C. Gong and Y.Z. Fan, On the cardinality of the characteristic set with respect to k-maximal vectors of a tree, sumitted.
[42]R. Grone and R. Merris, Algebraic connectivity of trees, Czechoslovak Mathematical Journal, 37:660-670(1987).
[43]J. M. Guo, S. W. Tan, A relation between the matching number and the Laplacian spectrum of a graph, Linear Algebra Appl., 325(2001):71-74.
[44]L. Hagen, A. B. Kahng, New spectral methods for ratio cut partitioning and clustering. IEEE Trans Comput-Aided Des Integr Circuits Syst,11(9)(1992):1074-1085.
[45]J.V.D. Heuvel, Hamilton cycles and eigenvalues of graphs, Linear Algebra Appl., 226/228(1995):723-730.
[46]B. Hendrickson R. Leland. An improved spectral graph partitioning algorithm for mapping parallel computations. SIAM Journal on Scientific Computing. Volume 16(2)(1995):234-245.
[47]R. A. Horn and C. R. Johnson, Matrix analysis, Cambridge University Press,1985.
[48]E. Huckel, Quantentheoretische Beitrage zum Benzolproblem, Z.Phys.,70(1931):204-286.
[49]A. Lubotzky, R. Phillips and P. Sarnak, Ramanujan graphs, Combinatorica,8(1988):261-278.
[50]R. Merris, Laplacian graph eigenvectors, Linear Algebra Appl.,278(1998):221-236.
[51]R. Merris, Laplacian matrices of graphs:a survey, Linear Algebra Appl.,197/198(1998): 143-176.
[52]R. Merris, Characteristic vertices of trees, Linear and Multilinear Algebra,22(1987):115-131.
[53]B. Mohar, Some applications of Laplacian eigenvalues of graphs, in:Graph Symmetry (G. Hahn and G. Sabidussi Eds), Kluwer Academic Publishers, Dordrecht,1997:225-275.
[54]B. Mohar, Some applications of Laplace eigenvalues of graphs, in Graph Symmetry, (G.Hahn and G.Sabidussi Ed.), Kluwer Academic Publishers, Dordrecht,1996.
[55]S. Kirkland and S. Fallat, Perron components and algebraic connectivity for weighted graphs, Linear and Multilinear Algebra,44(1998):131-138.
[56]S. Kirkland, M. Neumann, Algebraic connectivity of weighted trees under perturbation, Linear and Multilinear Algebra,42(1997):187-203.
[57]S. Kirkland, M. Neumann, B. Shader, Characteristic vertices of weighted trees via Perron values, Linear and Multilinear Algebra,40(1996):311-325.
[58]G. Kirchhoff, Uber die Auflosung der Gleichungen, auf welche man bel dar Untersuchung der linearen Verteilung galvanischer Strome gefuhrt wird, Ann. Phys. Chern.,72(1847):497-508.
[59]W. Q. Li, Graph theory with applications (in Chinese), Peiking Univ. Press,2001.
[60]H. C. Longuet-Higgins, Resonance structures and MO in unsaturated hydrocarbons, J. Chem. Phys.18(1950):265-274.
[61]B. Luo, R. C. Wilson, E. R. Hancock, Spectral embedding of graphs, Pattern Recognition, 36(2003):2213-2230.
[62]S. Parter, On the eigenvalues and eigenvectors of a class of matrices, J. Soc. Indust. Appl. Math 8 (1960):376-388.
[63]S. Pati, The third smallest eigenvalue of the Laplacian matrix, Electronic Journal of Linear Algebra,8(2001):128-139.
[64]A. Pothen, H. Simon, K. Liou, Partitioning sparse matrices with eigenvectors of graphs Source. SIAM Journal on Matrix Analysis and Applications, Volume 11(3)(1990)124-134.
[65]M. Nath, B. K. Sarma, On the null-spaces of acyclic and unicyclic singular graphs, Linear Algebra Appl.427(2007) 42-54.
[66]A. Sanfeliu, R. Alquezar, J. Andrade, J. Climent, F. Serratosa, J. Verges, Graphbased rep-resentations and techniques for image processing and image analysis, Pattern Recognition, 35(2002):639-650.
[67]I. Sciriha, I. Gutman, On the nullity of line graphs of trees, Discrete Math.232 (2001): 35-45.
[68]W. So, Rank One perturbation and its application to Laplacian spectrum of a graph, Linear Algebra and Multilinear Algebra,46:193-198(1999).
[69]I. Sciriha, On the contruction of graphs of nullity one, Discrete Math.181(1998):193-211.
[70]J. Shi and J. Malik, Normalized cuts and image and segmentation, IEEE Pattarn Anal. Mach. Intel.22(8)(2000):888-905.
[71]S. Umevama, An eigendecomposition approach to weighted graph matching problem. IEEE Pattern Anal. Mach. Intel.10(1988):695-703.
[72]Z. Wu and R. Leahy, "An Optimal Graph Theoretic Approach to Data Clustering:Theory and Its Application to Image Segmentation," IEEE Trans. Pattern Analysis and Machine Intelligence,15(11)(1993):1101-1113.
[73]E. P. Xing, M. I. Jordan, On semidefinite relaxation for normalized k-cut and connections to spectral clustering. University of California at Berkeley Technical report UCB/CSD-3-1265. 2003.
[74]X. D. Zhang, J. S. Li, The Laplacian spectrum of a mixed graph, Linear Algebra Appl., 343(2002):11-20.
[75]X. D. Zhang, R. Luo, The Laplacian eigenvalues of a mixed graph, Linear Algebra Appl., 353(2003):109-119.
[2]J.E. Atkins, E.G. Boman and B. Hendrickson, A spectral algorithm for seriation and the consecutive ones problem, SIAM J.Comput.28(1)(1998):297-310.
[3]R. Bach, M. I. Jordan, Learning spectral clustering. University of California at Berkeley Technical report UCB/CSD-03-1249.2003.
[4]R. B. Bapat,J. W. Grossman, D. M. Kulkarni, Generalized matrix tree theorem for mixed graphs, Linear and Multilinear Algebra,46(1999):299-312.
[5]R. B. Bapat, J. W. Grossman, D. M. Kulkarni, Edge version of the matrix tree theorem for trees, Linear and Multilinear Algebra,47(2000):217-229.
[6]R. B. Bapat and S. Pati, Algebraic connectivity and the characteristic set of a graph, Linear and Multilinear Algebra,45(1998):247-273.
[7]L. W. Beineke and R. J. Wilson,Selected Topics in Graph Theory, Academic Press, London, 1978.
[8]J. A. Bondy and U. S. R. Murty, Graph theory with applications, the Macmillan Press, London,1976.
[9]B. Bollobas, Modern Graph Theory, Springer Verlag, New York,1998.
[10]D. M. Cardoso, D.Cvetkovic, P. Rowlinson, S. K. Simi, A sharp lower bound for the least eigenvalue of the signless Laplacian of a non-bipartite graph, Linear Algebra Appl., 429(2009):2770-2780.
[11]P. K. Chan, M. D. F. Schlag, J. Y. Zien, Spectral k-way ratio-cut partitioning and clustering. IEEE Trans Comput-Aided Des Integr Circuits syst,13(9)(1994):1088-1096.
[12]M. F. Chen, F. Y. Wang, Cheeger's inequalities for general symmetric forms and existence criteria for spectral gap, The Annals of Probability,28(1)(2000):235-257.
[13]Fan R. K. Chung, Spectral Graph Theory, in CBMS,1997.
[14]D. Cvetkovic, P. Rowlinson, S.K. Simic, Signless Laplacians of finite graphs, Linear Algebra Appl.,423(2007):155-171.
[15]D. Cvetkovic, P. Rowlinson, S.K. Simic, Eigenvalue bounds for the signless Laplacian, Publ. Inst. Math. (Beograd),81(95)(2007):11-27.
[16]D. Cvetkovic, P. Rowlinson and S. Simic, Eigenspace of Graphs, Cambridge University Press, Cambridge,1997.
[17]D. Cvetkovic, Doctoral Thesis:Graphs and their spectra, Univ. Beograd, Publ. Elektrotehn. Fak.,Ser. Mat. Fiz.,354(1971):1-50.
[18]D. Cvetkovic. M. Doob,I. Gutman and A. Torgasev, Recent Results in the Theory of Graph Spectra, North Holland, Amersterdam,1988.
[19]D. Cvetkovic, M. Doob and H. Sachs, Spectra of graphs-Theory and Application,2nd ed., VEB Deutscher Verlag d.Wiss., Berlin,1982.
[20]D. Cvetkovic and I. Gutman, The algebraic multiplicity of the number zero in the spectrum of a bipartite graph, Mat. Vesnik,9(24)(1972):141-150.
[21]C. H. Q. Ding, X. He, H. Zha, et al. A min-max cut algorithm for graph partitioning and data clustering. In:Cercone N, Lin T Y,Wu X, eds. ICDM 2001. Los Alamitos, California: IEEE Computer Society,2001.107-114.
[22]C. H. Q. Ding, X, He, H. Zha, A spectral method to separate disconnected and nearly-disconnected web graph components. In:Provost F, Srikant R, eds. Proceedings of the Seventh ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York:Association for Computing Machinery,2001.275-280.
[23]Y.Z. Fan, S.C. Gong, Y. Wang and Y.B. Gao, On trees with exactly one characteristic element, Linear Algebra Appl,421(2007):233-242.
[24]Y. Z. Fan, Largest eigenvalue of a unicyclic mixed graph, Applied Mathematics A Journal of Chinese. Universities (English Series),19(2004):140-148.
[25]Y. Z. Fan, On the least eigenvalue of a unicyclic mixed graph, Linear and Multilinear Algebra,53(2005):97-113.
[26]Y. Z. Fan, On spectral integral variations of mixed graphs, Linear Algebra Appl.,374(2003): 307-316.
[27]Y. Z. Fan, S. C. Gong, Y, Wang, Y. B. Gao, First eigenvalue and first eigenvectors of a nonsingular unicyclic mixed graph,Discrete Math.,309(8)(2009):2479-2487.
[28]Y. Z. Fan, J. S. Li, On graphs with small number of Laplacian eigenvalue greater than two. Linear Algebra Appl,360(2003):207-213.
[29]Y. Z. Fan, H. Y. Hong, S. C. Gong and Y. Wang, Order unicyclic mixed graphs by spectral radius. Australasian Journal of Combinatiorics,37(2007):305-316.
[30]S. Fallat, S. Kirkland. Extremizing algebraic connectivity subject to graph theoretic con-straints, Electronic Journal of Linear Algebra,3(1998):48-74.
[31]S. Fallat, S. Kirkland and S. Pati, Minimizing algebraic connectivity over connected graphs with fixed girth, Discrete Mathematics,254(2002):115-142.
[32]S. Fallat, S. Kirkland and S. Pati, Maximizing algebraic connectivity over unicyclic graphs, Linear and Multilinear Algebra,51(2003):221-241.
[33]M. Fiedler, Algebraic connectivity of graphs, Czechoslovak Math.J.,23(1973):298-305.
[34]M. Fiedler, A property of eigenvectors of nonnegative symmetric matrices and its applica-tions to graph theory. Czechoslovak Math. J.,25(1975):607-618.
[35]S. Fiorini, I. Gutman, I. Sciriha. Trees with maximum nullity, Linear Algebra Appl. 397(2005):245-251.
[36]W. C. Forsrnan, Graph theory and the statistics and dynamics of polymer chains, J.Chem.Phys.,65(1976):4111-4115.
[37]C. Fowlkes. S. Belongie, F. Chung, et al. Spectral grouping using the Nystrom method. IEEE Trans Pattern Anal Mach Intell,26(2)(2004):214-25.
[38]C.D.Godsil, Algebraic Combiantorics, Chapman & Hall, New York,1993.
[39]S.C. Gong and Y.Z. Fan, The Property of Maximal Eigenvectors of Trees, Linear and Multilinear Algebra 58(1)(2010):105-111.
[40]S. C. Gong, Y. Z. Fan, On trees with exactly one characteristic element corresponding to k-vector, The Proceedings of the Seventh International conference on Matrix Theorey and its Applications,2006:300-303.
[41]S.C. Gong and Y.Z. Fan, On the cardinality of the characteristic set with respect to k-maximal vectors of a tree, sumitted.
[42]R. Grone and R. Merris, Algebraic connectivity of trees, Czechoslovak Mathematical Journal, 37:660-670(1987).
[43]J. M. Guo, S. W. Tan, A relation between the matching number and the Laplacian spectrum of a graph, Linear Algebra Appl., 325(2001):71-74.
[44]L. Hagen, A. B. Kahng, New spectral methods for ratio cut partitioning and clustering. IEEE Trans Comput-Aided Des Integr Circuits Syst,11(9)(1992):1074-1085.
[45]J.V.D. Heuvel, Hamilton cycles and eigenvalues of graphs, Linear Algebra Appl., 226/228(1995):723-730.
[46]B. Hendrickson R. Leland. An improved spectral graph partitioning algorithm for mapping parallel computations. SIAM Journal on Scientific Computing. Volume 16(2)(1995):234-245.
[47]R. A. Horn and C. R. Johnson, Matrix analysis, Cambridge University Press,1985.
[48]E. Huckel, Quantentheoretische Beitrage zum Benzolproblem, Z.Phys.,70(1931):204-286.
[49]A. Lubotzky, R. Phillips and P. Sarnak, Ramanujan graphs, Combinatorica,8(1988):261-278.
[50]R. Merris, Laplacian graph eigenvectors, Linear Algebra Appl.,278(1998):221-236.
[51]R. Merris, Laplacian matrices of graphs:a survey, Linear Algebra Appl.,197/198(1998): 143-176.
[52]R. Merris, Characteristic vertices of trees, Linear and Multilinear Algebra,22(1987):115-131.
[53]B. Mohar, Some applications of Laplacian eigenvalues of graphs, in:Graph Symmetry (G. Hahn and G. Sabidussi Eds), Kluwer Academic Publishers, Dordrecht,1997:225-275.
[54]B. Mohar, Some applications of Laplace eigenvalues of graphs, in Graph Symmetry, (G.Hahn and G.Sabidussi Ed.), Kluwer Academic Publishers, Dordrecht,1996.
[55]S. Kirkland and S. Fallat, Perron components and algebraic connectivity for weighted graphs, Linear and Multilinear Algebra,44(1998):131-138.
[56]S. Kirkland, M. Neumann, Algebraic connectivity of weighted trees under perturbation, Linear and Multilinear Algebra,42(1997):187-203.
[57]S. Kirkland, M. Neumann, B. Shader, Characteristic vertices of weighted trees via Perron values, Linear and Multilinear Algebra,40(1996):311-325.
[58]G. Kirchhoff, Uber die Auflosung der Gleichungen, auf welche man bel dar Untersuchung der linearen Verteilung galvanischer Strome gefuhrt wird, Ann. Phys. Chern.,72(1847):497-508.
[59]W. Q. Li, Graph theory with applications (in Chinese), Peiking Univ. Press,2001.
[60]H. C. Longuet-Higgins, Resonance structures and MO in unsaturated hydrocarbons, J. Chem. Phys.18(1950):265-274.
[61]B. Luo, R. C. Wilson, E. R. Hancock, Spectral embedding of graphs, Pattern Recognition, 36(2003):2213-2230.
[62]S. Parter, On the eigenvalues and eigenvectors of a class of matrices, J. Soc. Indust. Appl. Math 8 (1960):376-388.
[63]S. Pati, The third smallest eigenvalue of the Laplacian matrix, Electronic Journal of Linear Algebra,8(2001):128-139.
[64]A. Pothen, H. Simon, K. Liou, Partitioning sparse matrices with eigenvectors of graphs Source. SIAM Journal on Matrix Analysis and Applications, Volume 11(3)(1990)124-134.
[65]M. Nath, B. K. Sarma, On the null-spaces of acyclic and unicyclic singular graphs, Linear Algebra Appl.427(2007) 42-54.
[66]A. Sanfeliu, R. Alquezar, J. Andrade, J. Climent, F. Serratosa, J. Verges, Graphbased rep-resentations and techniques for image processing and image analysis, Pattern Recognition, 35(2002):639-650.
[67]I. Sciriha, I. Gutman, On the nullity of line graphs of trees, Discrete Math.232 (2001): 35-45.
[68]W. So, Rank One perturbation and its application to Laplacian spectrum of a graph, Linear Algebra and Multilinear Algebra,46:193-198(1999).
[69]I. Sciriha, On the contruction of graphs of nullity one, Discrete Math.181(1998):193-211.
[70]J. Shi and J. Malik, Normalized cuts and image and segmentation, IEEE Pattarn Anal. Mach. Intel.22(8)(2000):888-905.
[71]S. Umevama, An eigendecomposition approach to weighted graph matching problem. IEEE Pattern Anal. Mach. Intel.10(1988):695-703.
[72]Z. Wu and R. Leahy, "An Optimal Graph Theoretic Approach to Data Clustering:Theory and Its Application to Image Segmentation," IEEE Trans. Pattern Analysis and Machine Intelligence,15(11)(1993):1101-1113.
[73]E. P. Xing, M. I. Jordan, On semidefinite relaxation for normalized k-cut and connections to spectral clustering. University of California at Berkeley Technical report UCB/CSD-3-1265. 2003.
[74]X. D. Zhang, J. S. Li, The Laplacian spectrum of a mixed graph, Linear Algebra Appl., 343(2002):11-20.
[75]X. D. Zhang, R. Luo, The Laplacian eigenvalues of a mixed graph, Linear Algebra Appl., 353(2003):109-119.