相鄰路線與歐拉遍歷

MoAI - 您的AI助手

建立於 2026年11月10日

學習重點 把車站標示轉成「車站是點、相鄰關係是線」的路線圖，依共同站名串接，判斷沿途先後順序。 分清楚「兩站相鄰」與「兩站位於同一路線」：相鄰表示中間沒有其他車站，不能任意插入或跳過車站。 利用頂點度數的奇偶性，判斷能否從指定起點一筆畫到指定終點。 以「所有線段各走一次的長度＋必要重複路段的最短長度」，求出遍歷所有線段的最短總長。 核心觀念 一、相鄰標示如何轉成路線順序 車站標示提供的是局部的相鄰關係。例如知本與太麻里相距11.7公里、與康樂相距7.0公里，在沒有分岔的路線中，可整理成「太麻里—知本—康樂」，也可反向寫成「康樂—知本—太麻里」。兩種寫法表示相同的相鄰關係，實際搭乘順序則由起點與目的地方向決定。 解題時，應先把各張標示整理成短路線，再利用重複出現的站名接合。若某張標示顯示甲站的鄰站是乙、丙，另一張顯示丙站的鄰站是甲、丁，便可串成「乙—甲—丙—丁」。共同站名是接合位置，不能在接合後把同一站重複列出。 列出相鄰配對：每一筆資料都寫成「站名—站名」，並保留對應距離。 接合共同站名：讓已知的相鄰關係同時成立，排成完整路線。 決定行進方向：找到起點與終點，從起點朝終點讀出站序。 回查標示：逐一確認每組相鄰站都緊靠，沒有顛倒、漏站或多插車站。 判斷方向的技巧：起點知本有兩個鄰站，一個（太麻里）只出現在知本的標示中、不再往下延伸，另一個（康樂）則會在其他標示中繼續接出下一站，往目的地方向就是沿著「能一直接下去」的那一側走。目的地鹿野通常只以「鄰站」身分出現，表示它是這段串接的末端。 依此串接臺東地區的路線，可得： 方向串接結果 知本往鹿野知本→康樂→臺東→山里→鹿野 知本另一側（不經過）太麻里 若只問沿途車站的順序，通常不必先加總公里數；距離是相鄰兩站之間的長度，不能把距離大小當成站序。作答可用箭頭寫出完整搭乘路線，並清楚標明起點與終點；若另外列「中途經過站」，則將兩端車站排除（即康樂、臺東、山里）。 二、把一筆畫問題轉成圖形的邊與點 在圖論模型中，連接位置稱為頂點，兩個頂點之間的線段稱為邊。某頂點所連接的邊數，稱為該點的度數。度數為奇數的稱為奇點，為偶數的稱為偶點。 一筆畫表示筆不離開圖形、連續走完指定線段。除了起點與終點外，每到一個中途頂點，都必須有一次進入及一次離開，因此使用到的邊會成對出現。這就是判斷度數奇偶性的原因。 要求連通圖恰好走過每條邊一次的條件 起點與終點相同所有頂點都是偶點。 起點與終點不同恰有兩個奇點，且這兩點必須分別是起點與終點。 歐拉路徑的重點是每條邊恰走一次，不是每個頂點只經過一次。同一頂點可以多次經過，只要仍符合邊的使用要求。若原圖不符合條件，但題目允許重畫部分線段，就要加入必要的重複路段。 三、重複路段如何改變奇偶性 把一條邊多走一次，可視為在圖上增加一條同樣的邊；該邊兩端的度數各增加1，所以兩端的奇偶性都會翻轉。若重複的是一整條路徑，路徑內部各點增加2次連接，奇偶性不變，只有路徑兩端的奇偶性翻轉。 因此，指定從某點出發、到另一點結束時，最終必須讓起終點為奇點，其餘各點為偶點。應先找出哪些點需要翻轉奇偶性，再尋找連接它們的最短重複路徑，而不是憑直覺從起點附近挑一條邊重畫。 四、正方形加兩條對角線的最短遍歷 設正方形ABCD依序排列，邊長為1，並畫出兩條對角線AC、BD。原有六條線段，包括四條邊及兩條對角線。由畢氏定理，每條對角線長為√2，因此六條線段各走一次的基本總長為4＋2√2。 在四個角點中，每點都連接兩條正方形邊與一條對角線，度數均為3，所以共有四個奇點。若只准每條線段走一次，無法一筆畫完成；允許重複時，便須將指定起終點以外的另外兩個奇點改成偶點。 指定起終點需要變成偶點的角點最短重複路段最短總長 A到B：相鄰兩點C、D邊CD，長15＋2√2 A到C：相對兩點B、D對角線BD，長√24＋3√2 相鄰起終點的情形，重複CD後，A、B仍為奇點，C、D變成偶點。例如走法「A→C→D→A→B→C→D→B」，能涵蓋六條線段，且只有CD使用兩次。 相對起終點的情形，重複BD後，A、C仍為奇點，B、D變成偶點。例如走法「A→B→D→A→C→B→D→C」，能涵蓋六條線段，且只有BD使用兩次。這些走法也確認了每條線段最多畫兩次的限制確實可以滿足。 最短性的理由是：需要翻轉奇偶性的兩點必須由重複路徑連接。C、D之間直接走邊CD長1最短；B、D之間直接走對角線BD長√2，比沿正方形兩邊繞行的長度2更短。因此上述增加的長度均已達到必要的最小值。 申論作答建議寫出三步：①算出原長4＋2√2；②說明四角皆為奇點，指出需修正的兩點；③寫出重複路段與一條實際走法，再給最短總長。 常考陷阱 把標示上的排列方向當成行車方向：標示先提供相鄰關係，完整路線可以反向閱讀；必須依起點與終點決定作答方向。 把起點另一側的鄰站寫進路線：從知本往鹿野不會經過太麻里，太麻里在反方向。 依公里數由小到大排列車站：距離較近不代表先經過。站序要靠相鄰關係串接，不能靠數字排序。 看到四個奇點就認定完全不能一筆畫：四個奇點表示無法讓每條邊恰走一次；若允許重複部分邊，仍可能完成。 只記「兩個奇點」，忽略指定端點：最終的兩個奇點必須正好是題目要求的起點與終點，不能任選。 直接重複起點到終點的線段：本例應保留起終點的奇性，修正另外兩個奇點；重複錯誤的邊，會得到不符合要求的端點。 只算六條線段的總長：4＋2√2只是全部各走一次的長度，尚未加入為了連續遍歷而必須重複的部分。 把對角線當成邊長或沿邊距離：單位正方形的對角線長為√2，沿兩條邊繞行才是2。 把交叉處誤算成奇點：若把兩條對角線的交點視為可轉向的頂點，其度數為4，是偶點，不會消除四個角點原有的奇性。 誤以為每條線段都要畫兩次：「最多兩次」是上限。求最短時，只重複必要路段，並確認沒有任何線段超過兩次。 記憶口訣 站序：先接鄰站，再定方向，最後回查。 一筆畫：回原點，全為偶；不同端，兩端奇。 求最短：原長先算，奇偶修正，重複取短。 正方形：相鄰補一邊（＋1），相對補對角（＋√2）。