Re: [中學] 車站轉乘

[LPH66 (1597463007)]

※ 引述《dayjay (數學小老師)》之銘言：
: 小明所在的城市有六條地鐵線路，每兩條線路恰相交於一個換乘車站
: 每個換乘車站只有兩條線路經過，如果小明想從家出發，在每個換乘車站
: 都至少進行一次換乘，最後再回到家。小明家的地鐵站不是一個換乘車站
: 那麼他想要達到目的，至少要換乘多少次 ?
: ans: 18次
: 想法:大致上可以畫出應該是一個六角形的線路結構，
: 但為什麼18次就想不是很明白。
轉換問題成以下形式:

  在完全圖 K6 上以一筆畫由一點出發至少經過所有邊一次並回到原點

  至少需要經過幾條邊？

概念上有點像是「點」「邊」互換

原題的「地鐵線路」在這裡以「點」代表

原題的「轉乘車站」在這裡以連接兩點的「邊」代表

於是「所有轉乘車站都走過一次」即變成了「經過所有邊一次」

「回到原點」的要求則是表示小明最後要回到同一條地鐵線路上

這是一個 N 筆畫問題

由於 K6 的全部六個點都是奇點, 要不重覆的畫完全部 15 個邊至少需要 3 筆畫

然後又要求最後要回到原點, 因此將這 3 筆畫全部連接起來至少要額外經過 3 條邊

全部經過的邊數 (= 原題轉乘次數) 至少就要是 18 #

--
理論上以原題的形式應該也能得出所有轉乘車站至少得分三批經過

不過那比較類似旅行推銷員問題, 這種結論不太好獲得就是

--
  'You've sort of made up for it tonight,' said Harry. 'Getting the
sword. Finishing the Horcrux. Saving my life.'
  'That makes me sound a lot cooler then I was,' Ron mumbled.
  'Stuff like that always sounds cooler then it really was,' said
Harry. 'I've been trying to tell you that for years.'
                               -- Harry Potter and the Deathly Hollows, P.308

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 123.195.39.85
※ 文章網址: http://www.ptt.cc/bbs/Math/M.1412947548.A.DF6.html
推 dayjay      : 不好意思  我對這個K6圖沒概念  上網查也查不到
→ dayjay      : 可以給個關鍵字嗎?  因為沒畫面有點難了解
→ coolbetter33: complete graph
→ LPH66       : 中文就是我擺在 K6 前面的三個字「完全圖」
→ LPH66       : 這是指所有點兩兩之間都有一條邊  K6 表示是 6 個點
推 dayjay      : 大致上知道了  剩下不懂的是怎麼從6個奇點去推18次
→ dayjay      : 我只知道奇點可以不可同時當起點終點  偶點可以同時
→ LPH66       : 就是我文中的推理: 6 奇點 => 至少 3 筆畫
→ LPH66       : 要連成一筆又回到原點 => 至少加 3 條邊
→ XII         : 應該是中國郵差問題,不是旅行推銷員問題...
推 yw1002      : 圖論離散這些非連續分析領域的 都歸於topology?
→ yw1002      : 交大也都有ocw
→ LPH66       : 中國郵差問題是我這邊變形的問題, 我是指原題的形式
→ LPH66       : 比較類似旅行推銷員問題...