1  2  3  4  5  6  7  8  9  10  11  12   Contents

熱身運動之問題解答

1. 一筆畫

1. 試試看能不能用一筆畫畫出這樣的圖形？

2. 這樣呢？可以一筆畫嗎？

3. 這樣呢？可以一筆畫嗎？

此圖有四個奇點，無法一筆畫。

怎麼樣的圖才能一筆畫呢？

圖形為連通圖，而且奇點的個數為0或2。

 

2. 你能不能在下面這個地圖中，設計一個旅行路線——將每座橋各走過一次，並且回到起點？

A→E→D→C→A→D→B→A

 

3. 以下這些圖是否存在一條封閉路徑（起點和終點為同一點），並通過每一條邊恰好一次？如果有的話，你能找出這條路徑嗎？

1. 　

2. 　

3. 　

4. 　

5. 　

由於圖中有兩個奇數秩的點v₂, v₅，所以沒有尤拉迴圈。

　

4. 下圖是一個室內設計圖，你是否可以找到一條路徑，使自己由A房間走到E房間，途中經過每扇門各一次？

A→H→G→D→C→B→G→F→E

　

5. 以下這些圖是否存在一條封閉路徑（起點和終點為同一點），並通過每一個點恰好一次？如果有的話，你能找出這條路徑嗎？

1. 　

2. 　

3. 　

此圖中不存在哈米爾頓迴圈。

若有哈米爾頓迴圈，則每個點必與兩條邊相連，而既然b, d, e, f, g的秩都是2，則所有與它們相鄰的邊一定是哈米爾頓迴圈的一部分，如紅線部分。但是這卻使得c得與4條邊相接，產生矛盾。

4. 　

此圖中不存在哈米爾頓迴圈。

假設此圖有哈米爾頓迴圈，而a, c, g的秩都為2，所以與它們相鄰的邊一定都是哈米爾頓迴圈中的一部分，如上圖紅線部分。接著，既然{d, c}, {d, g}已經是哈米爾頓迴圈中的一部分，則{d, e}必然不在迴圈上，否則d就變成與三邊相連。同樣地，由於{b, a}, {b, c}已在迴圈上，所以{b, e}必然不是迴圈中的一部分。於是對於e而言，它只能與{e, f}相連，產生矛盾（哈米爾頓迴圈中的每一點都必須與兩條邊相連）。