Download presentation
Presentation is loading. Please wait.
1
一筆畫問題 記 得 在 小 學 的 時 侯 ， 常 常 和 同 學 一 起 玩 一 筆 畫 遊 戲 。 我 們 只 是 畫 了 些 圖 ， 看 誰 能 把 圖 一 筆 畫 。 就 好 像 個 『 田 』 字 ， 我 們 花 了 不 少 時 間 也 未 能 把 它 畫 成 呀 。 現 在 才 知 道 ，它 是 沒 有 解 的 。
2
什麼是一筆畫？ 任 何 由 實 線 條 組 成 的 圖 形 ， 都 可 以 進 行 一 筆 畫 遊 戲 ， 我 們 從 圖 的 任 何 一 點 開 始 ， 繪 畫 該 圖 形 ， 其 間 不 能 重 復 任 何 線 段 斷 （ 點 是 可 以 重 復 的 ） ， 一 氣 呵 成 把 圖 畫 成 就 算 成 功 。
3
一筆畫的歷史 從 遠 古 開 始 ， 在 歐 洲 已 經 有 許 多 人 對 一 筆 畫 的 問 題 感 到 興 趣 。 在 １ ７ ５ ９ 年 ， 著 名 的 數 學 家 歐 拉 提 出 一 條 有 關 一 筆 畫 的 問 題 ， 使 一 筆 畫 成 為 當 時 的 熱 門 話 題 。 歐 拉 提 出 的 就 是 著 名 的 『 七 橋 問 題 』
4
哥尼斯堡七座橋問題 原來在當時的東普魯士有一個小城鎮叫哥尼斯堡，有一條普雷格爾河橫貫市內，河中心有二個小島。在當時有七座橋把這小島和對岸聯結起來。
5
在週末當地的市民喜歡在城裏蹓躂，有人曾想法子從家裏出發，走過所有的橋回到家裏，他們想是否能每座橋只走過一次。許多人試過都不成功。
6
現在是否有一個方法能走過?歐拉的朋友知道這個青年人很聰明，並且喜歡思考問題，就告訴他這個 「哥尼斯堡七橋問題」，要他想法子解決。
7
歐拉並沒有跑到哥尼斯堡去走走。他把這個問題化成了這樣的問題來看:把二岸和小島縮成一點，橋化為邊，二個頂無有邊聯結，當且僅當(if and only if)這點代表的地區有橋聯結起來。這樣歐拉就得到了一個圖了。
8
歐拉現在考慮這個圖是否能一筆畫完成，如果能夠的話，對應的「七橋問題」也就解決了。他先研究一般能一筆畫完成的圖應該具有什麼性質
歐拉現在考慮這個圖是否能一筆畫完成，如果能夠的話，對應的「七橋問題」也就解決了。他先研究一般能一筆畫完成的圖應該具有什麼性質?他發現它們大體上有二類，不是全都是偶點就是有二個奇點。
9
這個情形是可以這樣的看:如果一個圖能一筆畫成，那麼一定有一個起點開始畫，也有一個終點。有一條邊進這點，那麼就要有一條邊出去，不可能是有進無出，它就會變成終點，也不可能有出無進，它就會變成起點。
10
因此在「過路點」進出的邊總數應該是偶數，即「過路點」是偶點。如果起點和終點是同一點，那麼它也是屬於「有進有出」的類型，因此必須是偶點，這樣圖上全體的點是偶點。
11
如果起點和終點是不一樣，那麼它們必須是奇點了。因此這圖最多只能有二個奇點。現在對應七橋問題的圖，所有的頂點都是奇點，共有四個，故這個圖肯定不能一筆畫成。
12
理論 如 果 有 ｎ 條 線 連 接 到 一 個 點 ， 有 一 隻 螞 蟻 從 其 中 一 條 線 來 到 這 點 ， 然 後 從 另 一 條 路 離 開 ， 餘 下 就 有 （ ｎ － ２ ） 條 線 讓 螞 蟻 爬 過 。 要 是 螞 蟻 不 停 地 通 過 這 點 ， 餘 下 的 線 就 會 不 斷 減 少 ， 如 果 ｎ 是 雙 數 ， 最 後 餘 下 的 線 數 量 為 ２ ， 在 最 後 一 次 通 過 這 點 時 ， 會 以 最 後 還 沒 有 行 的 路 離 開 。
13
但 如 果 ｎ 是 單 數 ， 在 不 斷 減 少 後 ， 最 後 會 減 至 １ ， 也 就 是 說 ， 當 螞 蟻 最 後 一 次 進 入 這 點 ， 牠 並 不 可 能 找 到 一 個 還 沒 有 走 過 的 路 離 開 ， 所 以 這 一 點 一 定 要 成 為 起 點 或 終 點 。 總 括 來 說 ， 所 有 有 單 數 線 連 接 的 分 叉 點 必 定 是 起 點 或 終 點 。
15
http://calculus. nctu. edu
看七座橋的圖
Similar presentations
