符号图论文：符号图的零维数.doc

符号图论文：符号图的零维数【中文摘要】图的零维数定义为其邻接谱中零特征值的重数.若图的零维数大于零,则称该图是奇异的.图的零维数研究起源于量子化学领域.二十世纪五十年代,Longuet-Higgins发现：对于一个二部图,若其零维数大于零,则这种图所代表的交替烃分子结构是不稳定的.1957年,Collatz等人在研究分子结构稳定性时提出了刻画奇异图(或非奇异图)问题.在过去的三十年里,图的零维数问题引起了诸多化学家和数学家的兴趣,成为谱图理论一个热点研究问题.在图的每条边上指定一个正号(+)或负号(-),所得的图被称为符号图.Harary在研究社会心理学方面首先引入符号图来研究社会平衡理论.随后,诸多图论问题被拓展到符号图中去.本文讨论了符号图的零维数问题,得到了带有悬挂树的符号图零维数分解定理.利用该定理：刻画了零维数分别为n-2,n-3,n-4,n-5,n-6,n-7的单圈符号图,零维数分别为n-2,n-3的双圈符号图,以及零维数为n-4的带有悬挂树的双圈符号图.本文的组织结构如下.第一章,我们首先介绍邻接谱理论和零维数问题的以及本文所用到的一些概念和术语,随后介绍了本文的研究问题与进展,以及本文的主要结论.第二章首先给出了带有悬挂数的符号图零维数分解定理,随后刻画了零维数分别为n-2,n-3,n-4,n-5,n-6,n-7单圈符号图.第三章刻画了零维数分别为n-2,n-3的双圈符号图,以及零维数为n-4的带有悬挂树的双圈符号图.【英文摘要】The nullity of a graph is defined to be the multiplicity of the zero eigen-value in the adjacency spectrum of the graph, which origins from quantum chemistry. A graph is called nonsingular if its nullity is positive. In the fifties of last century, Longuet-Higgins found:If G is biparite and its nullity is positive, the alternant hydrocarbon corresponding to G is unstable. In 1957, Collatz et.al. first posed the problem of characterizing nonsingular or singular graphs for discussing the stability of the molecular structure. In past thirty years, this problem has received a lot of attention in chemistry and mathematics, has been a hot topic in spectral graph theory.A signed graph is a graph with a sign(+or-) attached to each of its edges. Signed graphs were introduced by Harary in connection with the study of the theory of social balance in social psychology. Subsequently, a number of problems of graphs were extended to those of signed graphs. In this thesis, we introduce the nullity of signed graphs, and give some results on the nullity of signed graphs with pendant trees. Using these results, we characterize the unicyclic signed graphs of order n with nullity n-2, n-3, n-4, n-5, n-6, n-7, respectively, the bicyclic signed graphs of order n with nullity n-2, n-3, respectively, and the bicyclic signed graphs of order n and nullity n-4 which contains pendant trees.This thesis is organized as follows. In Chapter one, we introduce a brief background of the adjacency spectral theory and the nullity of graphs, give some notations which we will be used in the following sections, introduce the problems and its development, and list the main results we obtained in this thesis. In Chapter two, we give the nullity decomposition theorem of signed graphs with pendant trees and characterize the unicyclic signed graphs of order n with nullity n-2,n-3,n-4,n-5,n-6,n-7, respectively. In final Chapter, the classification of bicyclic graphs with pendant trees is given. Using this classification and nullity decomposition theorem, we characterize the bicyclic signed graphs of order n with nullity n-2,n-3, respectively, and characterize the bicyclic signed graphs of order n and nullity n-4 which contains pendant trees.【关键词】符号图 单圈图 双圈图 零维数 悬挂树【英文关键词】Signed graph unicyclic graph bicyclic graph nullity pendant tree【目录】符号图的零维数摘要3-4ABSTRACT4-5符号说明6-8第一章 引言8-191.1 研究背景8-