自然界和人类社会中大量的复杂现象都可以用图来表示。如何区分这些复杂结构的拓扑形状是计算机、信息、分子生物等众多领域共同关注的一个基本研究课题。受这一应用驱动，本项目拟综合运用代数、数论以及概率分析等工具探索复杂结构识别中的图谱方法。我们拟围绕图谱理论中最基本、但长期未解决的问题—图谱确定问题展开研究。该问题最早源于Hückel的分子化学理论，其不仅在计算复杂性理论中有着重要应用，也与Kac的著名“听音辨鼓”问题密切相关。现有的图谱确定研究方法严重依赖于图的特殊结构，无法应用到一般的图。与已有方法完全不同，本项目拟发展对称整数矩阵的有理正交相似理论，在此基础上进一步发展新的图谱确定性判定准则，探索谱确定图的渐近分布规律，致力于从根本上回答“图谱在多大程度上可以识别图？”，特别是“几乎所有图都是谱确定的吗？”这一基本问题。项目所得结果可望对上述应用领域的研究产生重要的影响和指导作用。

Many complex structures in nature and society can be modeled as graphs. How to distinguish between these complex structures is a fundamental research problem in computer science, information science and molecular biology and so on. Motivated by the above applications, this proposal aims at exploring how to use graph spectra to distinguish these complex structures, by exploiting various tools from algebra, number theory and probability theory. We shall focus on the long standing open question in spectral graph theory — "Which graphs are determined by their spectra (DS for short)?" . The problem originates from Hückel’s molecular theory in chemistry, which has many applications in the theory of computational complexity, as well as the famous question of Kac "Can one hear the shape of a drum?" . The previous methods in proving that a graph is determined by its spectrum depend heavily on the special structures of the graphs, and cannot be applied to general graphs. Totally different from the existing methods, in this proposal, we shall develop the theory of the rational orthogonal similarity of symmetric integral matrices, based on which we shall propose new criteria and methods for determining and constructing DS graphs, and shall explore the asymptotic behavior of DS graphs, and shall devote to answering such fundamental questions as "To what extent is a graph DS?" and in particular, "Are almost all graphs DS?". The results obtained in this project are expected to exert important influences on the above applied research fields.