當前位置:編程學習大全網 - 編程語言 - 七橋問題解法

七橋問題解法

七橋連線

這個問題看似簡單,然而許多人作過嘗試始終沒有能找到答案。因此,壹群大學生就寫信給當時年僅20歲的大數學家歐拉,請他分析壹下。歐拉從千百人次的失敗中,以深邃的洞察力猜想,也許根本不可能不重復地壹次走遍這七座橋。為了證明這種猜想是正確的,歐拉用簡單的幾何圖形來表示陸地和橋。他是這樣解決問題的:既然陸地是橋梁的連接地點,不妨把圖中被河隔開的陸地看成A、B、C、D 4個點,7座橋表示成7條連接這4個點的線,如圖“七橋連線”所示。

七橋連線簡化圖

再把它簡化成圖形,就成了右圖“七橋連線簡化圖”。

在說歐拉的推論前,我們先說說偶點和奇點的問題。

奇偶數點圖

什麽是偶點呢?壹個點如果有偶數條邊,它就是偶點。如下面“奇偶數點圖”的A、B、E、F點。反之,如果壹個點有奇條邊數,它就是奇點。如圖中的C、D這兩點。

偶點和奇點與能不能壹次通過這座橋有關系嗎?別急,我們慢慢來說。

歐拉認為,如果壹個圖能壹筆畫成,那麽壹定有壹個起點開始畫,也有壹個終點。圖上其它的點是“過路點”——畫的時候要經過它。

“過路點”有什麽特點呢?它應該是“有進有出”的點,有壹條邊進這點,那麽就要有壹條邊出這點,不可能是有進無出或有出無進。如果只進無出,它就是終點;如果有出無進,它就是起點。因此,在“過路點”進出的邊總數應該是偶數,即“過路點”是偶點。

如果起點和終點是同壹點,那麽它也是屬於“有進有出”的點,因此必須是偶點,這樣圖上全體點都是偶點。

如果起點和終點不是同壹點,那麽它們必須是奇點,因此這個圖最多只能有二個奇點。

把上面所說的歸納起來,說簡單點就是:

能壹筆畫的圖形只有兩類:壹類是所有的點都是偶點。另壹類是只有二個奇點的圖形。

現在對照七橋問題的圖,我們回過頭來看看圖3,A、B、C、D四點都連著三條邊,是奇數邊,並且***有四個,所以這個圖肯定不能壹筆畫成。

歐拉對“七橋問題”的研究是圖論研究的開始,同時也為拓撲學的研究提供了壹個初等的例子。

事實上,中國民間很早就流傳著這種壹筆畫的遊戲,從長期實踐的經驗,人們知道如果圖的點全部是偶點,可以任意選擇壹個點做起點,壹筆畫成。如果是有二個奇點的圖形,那麽就選壹個奇點做起點以順利的壹筆畫完。要是不信的話,妳可以試試上圖“奇偶數點圖”,選擇C、D兩個奇點來畫,肯定能壹筆畫成。只是很可惜,長期以來,人們只把它作為壹類有趣的遊戲,沒有對它引起重視,也沒有數學家對它進行經驗總結和研究,這不能不說是壹種遺憾。

  • 上一篇:溫度計是根據什麽原理制成的?是誰發明的溫度計呢?
  • 下一篇:非標機械、專機設計要註意哪些方面?
  • copyright 2024編程學習大全網