線性代數在圖論的應用

Abstract

圖G 的鄰接矩陣A、拉普拉斯矩陣L 及正拉普拉斯矩陣Q 有許多應用，而它們 的特徵值洩漏許多圖G 的訊息，因此被稱為圖的值譜。此計畫將研究G 的值譜或 部分值譜所告訴我們的訊息，及可能的應用。這些訊息可能是圖的度數、第二平均 度數、著色數、連通數、甚至唯一決定G。這些結果可應用於繪圖、資料探索及辨 識、蛋白質結構探索等方面。

Let G be a graph. The adjacency matrix A, Laplace matrix L and signless Laplace matrix Q are used in many applications. Their eigenvalues, which are also call the spectra of G, can tell many things about Q, including the bounds of degrees, second average degrees, chromatic number and connectivity. In some cases G is uniquely determined by its spectra or part of its spectra. We aim to study the properties of G that are determined by the spectra of G. The project involves two different disciplines in mathematics, linear algebra and graph theory, which not only has mathematical interests but also has many applications, like plotting, data mining, and protein structure prediction.