圖 論 報 告.

Presentation on theme: "圖 論 報 告."— Presentation transcript:

1 圖 論 報 告

2 a={1,2} ; b={1,3}; c={1,4}; d={1,5} ; e={1,6} ; f={2,3};
題目敘述: 試畫出KG(6,2)並且在其上找出一條Euler circuit。 (附註: ) 解題過程與想法: 利用KG(6,2)的定義，將各點找出 a={1,2} ; b={1,3}; c={1,4}; d={1,5} ; e={1,6} ; f={2,3}; s={2,4} ; h={2,5} ; i={2,6} ; j={3,4} ; k={3,5}; l={3,6}; m={4,5}; n={4,6}; o={5,6}

3 a→j、k、l、m、n、o b→s、h、i、m、n、o c→f、h、i、k、l、o d→f、s、i、j、l、n e→f、s、h、j、k、m
將每個點與之相連的點找出，並且畫出圖形 a→j、k、l、m、n、o b→s、h、i、m、n、o c→f、h、i、k、l、o d→f、s、i、j、l、n e→f、s、h、j、k、m f→c、d、e、m、n、o s→b、d、e、k、l、o h→b、c、e、j、l、n

4 i→b、c、d、j、k、m j→a、d、e、h、i、o k→a、c、e、s、i、n l→a、c、d、s、h、m m→a、b、e、f、i、l n→a、b、d、f、h、k o→a、b、c、f、s、j

5 123

6 利用老師給的程式碼，找出Euler circuit

7 KG(6,2)的 Euler circuit

8 題目敘述: 解題過程與想法: 2. 試畫出KG(6,2)並且在其上找出一條Hamilton cycle。

9 KG(6,2)的 Hamilton cycle

10 先將5x5的棋盤在紙上畫出，並且將每個位置標號，再將每個位置上騎士可攻擊的位置標出。
題目敘述: 6.請在 5×5的西洋棋盤上放置一些騎士使得棋盤上的每一個格子至少存在一個騎士能”攻擊”這個位置(注意：每一個騎士自己所在的位置也算是它本身的攻擊位置)，我們希望騎士放置的數目能越少越好。如果可以的話，請找出騎士放置最少的情形。 解題過程與想法: 先將5x5的棋盤在紙上畫出，並且將每個位置標號，再將每個位置上騎士可攻擊的位置標出。 將每個位置對應成點，並且將每個位置上騎士可攻擊的位置(點)連邊

11 將位置對應成點，並將每個點可攻擊到的位置(點)連邊

12 1→(8、12)；2→(9、11、13)；3→(6、10、12、14)；4→ (7、13、15)；5→(8、14)；6→(3、13、17)；7→(4、14、 16、18)；8→(1、5、11、15、17、19)；9→(2、12、18、20)；10→(3、13、19)；11→(2、8、18、22)；12→(1、3、9、 19、21、23)；13→(2、4、6、10、16、20、22、24)； 14→(3、5、7、17、23、25)；15→(4、8、18、24)；16→ (7、13、23)；17→(6、8、14、24)；18→(7、9、11、15、21、23)；19→(8、10、12、22)；20→(9、13、23)；21→(12、18)；22→(11、13、19)；23→(12、14、16、20)；24→(13、15、17) 25→(14、18)

13

14 由上面個數得知不可能由三個集合聯集得到所有的元素。接著我們試著一個一個去試試看可不可以利用4個集合聯集出所有的元素，最後試不出來。有些利用程式先試試相加起來剛好25的試出沒有，其餘四個相加起來超過25的我們就一個一個慢慢試，所以證明出最少集合數會大於4，且我們找出五個集合聯集就可找到所有元素，因此最少要放五個騎士才攻擊到每個位置。

15 經過大家努力的嘗試之後，發現分成四種(8，12，13)、(8，13，14)、(12，13，18)、(13，14，18)如果選(8，12，13)已知8攻擊到(1、5、8、11、15、17、19)；12攻擊到(1、3、9、12、19、21、23)；13攻擊到(2、4、6、10、13、16、20、22、24)所以只會剩下7、14、18、25這四個點沒被打到，不過再任選一個就會只剩下一個沒被打到，這時再選取剩下的那一個就可以打完全部的點。同樣的方法(8，13，14)、(12，13，18)、(13，14，18)也適用。這樣計算下來就有80種放5顆棋子的方法。