漆圖的組合問題

Abstract

本篇論文的主要部分是學習一些有關漆圖的組合性質。所謂的漆圖是指在一個圖的點上我們可以塗上黑或白兩種顏色，但在這裡我們總是限制每一個圖至少要有一個黑點。然後我們考慮一個運算，它可以使得一個圖轉換成另一個圖，藉由這個運算我們就可以定義一個等價關係。假如一個圖可以藉由一連串的上述的運算而轉換成另一個圖的話，那我們就說這兩個圖是等價的。之後我們的工作就是去研究是否一個圖可以包含一種或以上的漆法但在這些種漆法之下這個圖沒辦法等價於只擁有單一黑點的圖。在最後一個章節我們探討square integrable harmonic forms在一維的複數空間上的一些結果。

The major part of this thesis studies some combinatorial properties of graph painting. A painting on a graph is an assignment of the color black or white to each vertex of the graph. We consider an algorithm which converts a painted graph to another. Two graphs are said to be equivalent if one can be transformed to the other by a sequence of such algorithms. We then study whether a graph admits a painting which is not equivalent to one with just a single black vertex. We also include a chapter on the square integrable harmonic forms on the one dimensional complex space.