數(shù)學(xué)欣賞-06數(shù)學(xué)之妙-c七橋問(wèn)題與圖論

數(shù)學(xué)欣賞Mathematics

Appreciation數(shù)學(xué)欣賞F數(shù)學(xué)之妙TheConsummateskillof

Mathematics名人說(shuō)……從十分清楚明白、根本無(wú)法懷疑的東西、最簡(jiǎn)單最容易認(rèn)識(shí)的對(duì)象開(kāi)始，一點(diǎn)一點(diǎn)逐步上升到對(duì)復(fù)雜對(duì)象的認(rèn)識(shí)。

——R.DESCARTES名人說(shuō)……數(shù)學(xué)是什么？大致說(shuō)來(lái)，數(shù)學(xué)和其它科學(xué)一樣，它的發(fā)展基于兩個(gè)原因：（一）奇怪的現(xiàn)象；（二）數(shù)學(xué)結(jié)果的應(yīng)用?！愂∩頂?shù)學(xué)之妙出神入化數(shù)學(xué)，雖然極其抽象，但卻被廣泛而有效的應(yīng)用于人類(lèi)社會(huì)的各個(gè)領(lǐng)域，其根本原因不僅是其對(duì)象為萬(wàn)物之本，更在于其思想方法的深刻性與普適性.由于人類(lèi)生理的原因，人類(lèi)能夠準(zhǔn)確認(rèn)識(shí)的對(duì)象只能是有限的、靜止的、平直的、離散的，但現(xiàn)實(shí)中人們又無(wú)法避免無(wú)限的、運(yùn)動(dòng)的、彎曲的、連續(xù)的.數(shù)學(xué)方法為人類(lèi)認(rèn)識(shí)這些對(duì)象提供了有效的可靠手段，奇妙無(wú)比，威力無(wú)限.InthisChapter數(shù)學(xué)歸納法原理1抽屜原理與聚會(huì)認(rèn)友

2七橋問(wèn)題與圖論

3數(shù)學(xué)與密碼4SZU第三節(jié)七橋問(wèn)題與圖論BDCA背景18世紀(jì)，位于現(xiàn)立陶宛內(nèi)的哥尼斯堡鎮(zhèn)，有一條河流叫普雷格爾河。河中有兩個(gè)相鄰的小島，島與島、島與陸地之間建有七座橋BDCA問(wèn)題：一個(gè)人能否一次無(wú)重復(fù)地走遍所有的七座橋，最后回到出發(fā)點(diǎn)？這就是著名的“七橋問(wèn)題”。1736年，一位小學(xué)教師寫(xiě)信給當(dāng)時(shí)的著名數(shù)學(xué)家歐拉（Euler），請(qǐng)教對(duì)七橋問(wèn)題的解答。歐拉用數(shù)學(xué)方法對(duì)七橋問(wèn)題進(jìn)行了深入的研究。歐拉的解答

——七橋問(wèn)題的數(shù)學(xué)模型歐拉研究后發(fā)現(xiàn)：(1)這不是一個(gè)代數(shù)問(wèn)題（代數(shù)問(wèn)題研究量的大小、關(guān)系）;(2)這也不是一個(gè)平面幾何問(wèn)題（平面幾何問(wèn)題研究角度的大小、線(xiàn)段的曲直、長(zhǎng)短等）。BDCA在這里，陸地、島嶼的大小、形狀均是無(wú)關(guān)緊要的，橋梁的曲直、長(zhǎng)短也對(duì)問(wèn)題的解答沒(méi)有影響；該問(wèn)題的解僅依賴(lài)于陸地、島嶼、橋梁等的具體個(gè)數(shù)及其相互位置關(guān)系。因此，可以將一塊陸地或一個(gè)島嶼看作一個(gè)“點(diǎn)”，將一座橋梁看作一條連接兩點(diǎn)的“線(xiàn)”。（如下頁(yè)圖）BDCABACD按照歐拉的思想，七橋問(wèn)題轉(zhuǎn)化為：一筆畫(huà)問(wèn)題在右圖中，能否從圖上某一點(diǎn)開(kāi)始，筆不離紙、不重復(fù)地畫(huà)出整個(gè)圖形？BACD這一重要思想，成為近代數(shù)學(xué)之一——圖論的基礎(chǔ)，同時(shí)也是近代數(shù)學(xué)——拓?fù)鋵W(xué)（位置幾何學(xué)）的奠基。

圖的基本概念

與基本結(jié)論1.圖—

點(diǎn)（稱(chēng)為頂點(diǎn)）和將它們之間的某些點(diǎn)兩兩連接起來(lái)的線(xiàn)（稱(chēng)為邊）的集合，叫做圖。一個(gè)圖記為G（Graph）;一條邊記為e（edge），邊的集合記為E（Edge）；一個(gè)頂點(diǎn)記為v（vertex），頂點(diǎn)的集合記為V（Vertex）。DACB頂點(diǎn)邊環(huán)2重邊相鄰頂點(diǎn)圖的基本概念(1)2.頂點(diǎn)的次數(shù)：頂點(diǎn)v處引出的邊的條數(shù)叫做頂點(diǎn)v的次數(shù)，記為

d（v）。結(jié)論次數(shù)總和等于邊數(shù)總和的2倍(偶數(shù))。圖的基本概念(2)4階完全圖孤立點(diǎn)簡(jiǎn)單圖3次頂點(diǎn)2次頂點(diǎn)3.奇點(diǎn)、偶點(diǎn)——頂點(diǎn)次數(shù)為奇（偶）數(shù)的頂點(diǎn)叫奇（偶）點(diǎn)。

結(jié)論：奇點(diǎn)數(shù)必為偶數(shù)。

偶點(diǎn)：邊線(xiàn)有進(jìn)有出，進(jìn)出對(duì)應(yīng)；

奇點(diǎn)：有一條只進(jìn)不出或只出不進(jìn)的邊線(xiàn)。4.連通圖——任意兩點(diǎn)之間都有鏈相連的圖叫做連通圖。

圖的基本概念(3)鏈，連通圖奇點(diǎn)偶點(diǎn)圈一筆畫(huà)定理

——

七橋問(wèn)題的解決

1.一筆畫(huà)定理定理（一筆畫(huà)）

一個(gè)圖G可以一筆畫(huà)的充要條件是：G是連通的，并且奇點(diǎn)的個(gè)數(shù)為0或2。當(dāng)奇點(diǎn)數(shù)為2時(shí)，一個(gè)奇點(diǎn)為起點(diǎn)，另一個(gè)奇點(diǎn)為終點(diǎn)；當(dāng)奇點(diǎn)個(gè)數(shù)為0時(shí)，任取一個(gè)頂點(diǎn)，它是起點(diǎn)，也是終點(diǎn)。證明思想：(1)必要性若G能一筆畫(huà)，則G必是連通的，而且只有在起點(diǎn)處的邊才可能只出不進(jìn)（奇點(diǎn)），也只有在終點(diǎn)處的邊才有可能只進(jìn)不出（奇點(diǎn)）。故G是連通的，且沒(méi)有奇點(diǎn)或只有兩個(gè)奇點(diǎn)。(2)充分性若G是連通的，并且奇點(diǎn)的個(gè)數(shù)為0或2。我們通過(guò)對(duì)頂點(diǎn)的總次數(shù)n=2k(偶數(shù))用數(shù)學(xué)歸納法來(lái)證明G可以一筆畫(huà)。

n=2時(shí)，G是一條有兩個(gè)頂點(diǎn)（端點(diǎn)）的線(xiàn)段，或是一條有一個(gè)頂點(diǎn)的圓圈。因此可以一筆畫(huà)。

假設(shè)n=2k時(shí)結(jié)論成立，考慮n=2(k+1)=2k+2的情況。

如果該圖沒(méi)有奇點(diǎn)，則從中任意去掉一條邊.設(shè)此邊的兩端點(diǎn)分別為v0,v1,此時(shí)，該圖仍然是連通的（因?yàn)槠淙我豁旤c(diǎn)處至少有兩條邊通過(guò)，去掉一條后，還至少有一條邊與其它頂點(diǎn)相連），而且，其頂點(diǎn)的次數(shù)總和為2k,其中奇點(diǎn)數(shù)最多為2。此時(shí)剩余圖可以從v0出發(fā)到v1結(jié)束一筆畫(huà)，再?gòu)膙1到v0,即可將原圖一筆畫(huà)。

如果該圖有兩個(gè)奇點(diǎn)v0,v1,

去掉v0出發(fā)的一條邊。

若d(v0)>1,則剩余圖是一個(gè)奇點(diǎn)個(gè)數(shù)為0或2、頂點(diǎn)次數(shù)總和為2k的連通圖,因而可以一筆畫(huà)，從而原圖也可以一筆畫(huà)。若d(v0)=1，則剩余圖是一個(gè)奇點(diǎn)個(gè)數(shù)為0或2、頂點(diǎn)次數(shù)總和為2k的非連通圖，除去v0點(diǎn)后，該圖是連通圖，可以一筆畫(huà)，因此原圖也可以一筆畫(huà)