距離圖

Abstract

將一個集合的吾素循著一定的規則去做分割，是數學上一種基本的處理手法；例如， 著色問題可視為一種圖上的點分割。一個圖G上的（點）著色即為對G上每一個點指定 一種顏色，使得任意有邊相連的兩點所指定的顏色皆不相同。第一個也是這類問題中 最富盛名的是平面圖的四色問題，這個問題可追溝到1852年，它是在1976年被Appel 和Haken兩位先生解決。除此之外，著色問題在本世紀以許多不同的風貌展現，許多 有趣的結困被發掘，同時，也對圖論中其他題材有深刻的影響。 對歐氏平面上所有的點著色，使得任意兩個距離為1的點都著不同顏色，這樣所需要 的最少顏色數為何？對這問題，我們僅有的結果是七色足夠，而四色不可免。這問題 真正的解答至今仍沒有人知道，由此問題出發，Eggleton定義了廣義的距離圖，本篇 論文中共探討了三類的距離圖。 在第二章中，我們將質距離圖推廣到整數距離圖。本章的目的在對於一般的整數子集 合D，研究X（Z,D）為何。事實上我們對於有限集合D，證明了X（Z,D）│D│+1。 對特殊的包含三個元素的D，我們刻實際的著色數。在本章末，我們對所有包含三個 元素的D給了一個正確點著色數的猜測。 在第三章中，我們討論了n維空間上1-narm的距離圖。我們討論了這類距離圖的距離 集、度數、分量等。本章也探討了單距離圖的點著色題，我們解答了 上的著色數。 對於奇數k，我們解答了n維格子點上的點著色數；對於偶數k，我們也解答了2維格子 點上的點著色數；除此之外，我們也對2維格子點上的雙距離圖找到了一些正確值和 上下界。 在第四章中，我們討論了n維空間上-norm的距離圖。如同在第三章中一般，我們對此 類距離圖的基本結構做了一番探討。對於著色問題方面，我們解答了上單距離圖的點 著色數；對於2維格子點上的雙距離圖，我們找到了精確的上下；同時，對於某些特 殊的例子，我們也找到了更好的上下界。