由 asmobia 於 星期五 二月 22, 2008 10:49 am
結論一:原圖 G 的 Hamilton circle 裡,任取兩個連續的邊:AB、BC,在 line graph L(G) 裡會形成兩個點,(AB) 與 (BC)。這是 line graph 定義。
結論二:依據 line graph 的基本性質,任何座標裡面包含同一個 X 的兩點,必互相通;所有座標裡面包含同一個 X 的所有點,將形成一個 complete graph。
結論三:由於 L(G) 裡面的 (AB) 與 (BC) 點都有 B 這個字,這兩點在 L(G) 裡面必相連通。
結論四:重複結論一的動作,將原圖 G 的 Hamilton circle 裡面所有的邊通通找出來,這將會在 line graph L(G) 裡面形成許多點。依據結論三, 這些點將形成一個圓;這裡稱作基礎圓。
結論五:原圖 G 中所有點的座標,將會在 L(G) 的基礎圓中出現正好兩次。因為基礎圓中的所有點,就代表了 G 的 Hamilton circle 的所有邊;可以說是 Hamilton circle 的 line graph。
結論六:原圖 G 中所有不包含於 Hamilton circle 的邊,在 L(G) 裡仍然會形成一個點。假設該點的第一個座摽為 X 。依據結論二,我們知道該點與所有座標包含 X 的點會形成一個 complete graph。
結論七:依據結論五,我們知道 X 這個座標值會在基礎圓裡出現兩次;也就是說基礎圓上有兩個點的座標都具有 X 。這兩個點與其他座標包含 X 的所有點,將會形成一個 complete graph。(參考結論二)
結論八:依據 complete graph 的基本性質,我們可以用基礎圓上面具有 X 座標的兩點當做起點與終點,做出一條走訪所有具有 X 座標的點的 Hamilton path。
結論九:利用結論八的模式,我們可以將基礎圓上的一條邊,延長成一個走訪所有 X 座標的點的 Hamilton path。而這些 paths,藉由基礎圓的架構,會連成一個 Hamilton circle。
得證。
看看怎樣用數學歸納法將上面九條換成數學語言吧。。。痛苦死了。