Re: [中學] 車站轉乘
※ 引述《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
推
10/10 21:58, , 1F
10/10 21:58, 1F
→
10/10 21:59, , 2F
10/10 21:59, 2F
→
10/10 22:28, , 3F
10/10 22:28, 3F
→
10/10 22:59, , 4F
10/10 22:59, 4F
→
10/10 23:00, , 5F
10/10 23:00, 5F
推
10/10 23:06, , 6F
10/10 23:06, 6F
→
10/10 23:06, , 7F
10/10 23:06, 7F
→
10/11 00:13, , 8F
10/11 00:13, 8F
→
10/11 00:14, , 9F
10/11 00:14, 9F
→
10/11 00:17, , 10F
10/11 00:17, 10F
推
10/11 07:51, , 11F
10/11 07:51, 11F
→
10/11 07:52, , 12F
10/11 07:52, 12F
→
10/11 09:06, , 13F
10/11 09:06, 13F
→
10/11 09:06, , 14F
10/11 09:06, 14F
討論串 (同標題文章)