可行遍性及賽題講解課件

可行遍性問題Euer圖中國(guó)郵遞員問題少Hamilton圖推銷員問題今建模案例:最佳災(zāi)情巡視路線文理學(xué)院數(shù)學(xué)系:徐艷xuyan555sina可行遍性問題11Euler圖1、圖的定義定義一個(gè)二元有序數(shù)組(V,E)稱為一個(gè)圖,記作G=(V,E)。V稱為頂點(diǎn),E為邊若每個(gè)邊對(duì)應(yīng)一個(gè)數(shù)F,稱(V,E,F)為賦權(quán)圖如果兩點(diǎn)是有序的,則稱有向圖,否則,無向圖。常用術(shù)語(1)端點(diǎn)相同的邊稱為環(huán)。(2)若一對(duì)頂點(diǎn)之間有兩條以上的邊聯(lián)結(jié),則這些邊稱為重邊。1Euler圖21Euler圖(3)有邊聯(lián)結(jié)的兩個(gè)頂點(diǎn)稱為相鄰的頂點(diǎn),有個(gè)公共端點(diǎn)的邊稱為相鄰的邊。(4)邊和它的端點(diǎn)稱為互相關(guān)聯(lián)的。(5)既沒有環(huán)也沒有重邊的圖稱為簡(jiǎn)單圖。(6)任意兩頂點(diǎn)都相鄰的簡(jiǎn)單圖,稱為完備圖1Euler圖3可行遍性及賽題講解課件41Euler圖例子哥尼斯堡(Konigsberg)七橋問題Euler在1736年訪問Konigsberg時(shí),他發(fā)現(xiàn)Konigsberg城中有一條名叫Pregel的河流,河上建有七座橋如圖所示:市民有趣的消遣活動(dòng)是星期六作一次走過所有七座橋的散步,每座橋只能經(jīng)過一次而且起點(diǎn)與終點(diǎn)必須是同一地點(diǎn),是否可能?5/481Euler圖51Euler圖每一塊陸地縮小為一個(gè)點(diǎn)連接陸地的橋表示為連線1Euler圖61Euler圖·分析:事實(shí)上,任何一點(diǎn)作為出發(fā)的頂點(diǎn),因?yàn)樗P(guān)聯(lián)的邊數(shù)是3條或5條,所以必然是先出后回,最后以出告終才能把與她關(guān)聯(lián)的邊每邊恰經(jīng)過次,可見不可能返回出發(fā)點(diǎn),就是這種思路,Euler作了一篇嚴(yán)謹(jǐn)?shù)臄?shù)學(xué)論文,證明了七橋問題無解。71481Euler圖7IEuler圖定義設(shè)G是無孤立頂點(diǎn)的圖,若存在一條跡(回路),經(jīng)過圖中每邊一次且僅一次,則稱此跡(回路)為該圖的一條Euler跡(環(huán)游)具有Euler環(huán)游的圖稱為Euler圖。注意:Euler跡(環(huán)游)是經(jīng)過圖所有邊的最短跡(回路)歐拉跡(環(huán)游)在我國(guó)亦稱“一筆畫問題”,即筆不離線,每條邊只畫一次而不許重復(fù)的畫完圖形。兩者完全等價(jià)8/8IEuler圖81Euler圖定理對(duì)于非空連通圖G,下列命題等價(jià)(1)G是Euler圖;(2)G無奇次數(shù)頂點(diǎn);(3)G的邊集能劃分為圈。1Euler圖91048104810可行遍性及賽題講解課件11可行遍性及賽題講解課件12可行遍性及賽題講解課件13可行遍性及賽題講解課件14可行遍性及賽題講解課件15可行遍性及賽題講解課件16可行遍性及賽題講解課件17可行遍性及賽題講解課件18可行遍性及賽題講解課件19可行遍性及賽題講解課件20可行遍性及賽題講解課件21可行遍性及賽題講解課件22可行遍性及賽題講解課件23可行遍性及賽題講解課件24可行遍性及賽題講解課件25可行遍性及賽題講解課件26可行遍性及賽題講解課件27可行遍性及賽題講解課件28可行遍性及賽題講解課件29可行遍性及賽題講解課件30可行遍性及賽題講解課件31可行遍性及賽題講解課件32可行遍性及賽題講解課件33可行遍性及賽題講解課件34可行遍性及賽題講解課件35可行遍性及賽題講解課件36可行遍性及賽題講解課件37可行遍性及賽題講解課件38可行遍性及賽題講解課件39可行遍性及賽題講解課件40可行遍性及賽題講解課件41可行遍性及賽題講解課件42可行遍性及賽題講解課件43可行遍性及賽題講解課件44可行遍性及賽題講解課件45可行遍性及賽題講解課件46可行遍性及賽題講解課件47可行遍性及賽題講解課件48可行遍性及賽題講解課件49可行遍性及賽題講解課件50可行遍性及賽題講解課件51可行遍性及賽題講解課件52可行遍性及賽題講解課件53可行遍性及賽題講解課件54可行遍性及賽題講解課件55可行遍性及賽題講解課件56可行遍性及賽題講解課件57可行遍性及賽題講解課件58可行遍性及賽題講解課件59可行遍性及賽題講解課件60可行遍性及賽題講解課件61可行遍性及賽題講解課件62可行遍性及賽題講解課件63可行遍性及賽題講解課件64可行遍性及賽題講解課件65可行遍性及賽題講解課件66可行遍性問題Euer圖中國(guó)郵遞員問題少Hamilton圖推銷員問題今建模案例:最佳災(zāi)情巡視路線文理學(xué)院數(shù)學(xué)系:徐艷xuyan555sina可行遍性問題671Euler圖1、圖的定義定義一個(gè)二元有序數(shù)組(V,E)稱為一個(gè)圖,記作G=(V,E)。V稱為頂點(diǎn),E為邊若每個(gè)邊對(duì)應(yīng)一個(gè)數(shù)F,稱(V,E,F)為賦權(quán)圖如果兩點(diǎn)是有序的,則稱有向圖,否則,無向圖。常用術(shù)語(1)端點(diǎn)相同的邊稱為環(huán)。(2)若一對(duì)頂點(diǎn)之間有兩條以上的邊聯(lián)結(jié),則這些邊稱為重邊。1Euler圖681Euler圖(3)有邊聯(lián)結(jié)的兩個(gè)頂點(diǎn)稱為相鄰的頂點(diǎn),有個(gè)公共端點(diǎn)的邊稱為相鄰的邊。(4)邊和它的端點(diǎn)稱為互相關(guān)聯(lián)的。(5)既沒有環(huán)也沒有重邊的圖稱為簡(jiǎn)單圖。(6)任意兩頂點(diǎn)都相鄰的簡(jiǎn)單圖,稱為完備圖1Euler圖69可行遍性及賽題講解課件701Euler圖例子哥尼斯堡(Konigsberg)七橋問題Euler在1736年訪問Konigsberg時(shí),他發(fā)現(xiàn)Konigsberg城中有一條名叫Pregel的河流,河上建有七座橋如圖所示:市民有趣的消遣活動(dòng)是星期六作一次走過所有七座橋的散步,每座橋只能經(jīng)過一次而且起點(diǎn)與終點(diǎn)必須是同一地點(diǎn),是否可能?5/481Euler圖711Euler圖每一塊陸地縮小為一個(gè)點(diǎn)連接陸地的橋表示為連線1Euler圖721Euler圖·分析:事實(shí)上,任何一點(diǎn)作為出發(fā)的頂點(diǎn),因?yàn)樗P(guān)聯(lián)的邊數(shù)是3條或5條,所以必然是先出后回,最后以出告終才能把與她關(guān)聯(lián)的邊每邊恰經(jīng)過次,可見不可能返回出發(fā)點(diǎn),就是這種思路,Euler作了一篇嚴(yán)謹(jǐn)?shù)臄?shù)學(xué)論文,證明了七橋問題無解。71481Euler圖73IEuler圖定義設(shè)G是無孤立頂點(diǎn)的圖,若存在一條跡(回路),經(jīng)過圖中每邊一次且僅一次,則稱此跡(回路)為該圖的一條Euler跡(環(huán)游)具有Euler環(huán)游的圖稱為Euler圖。注意:Euler跡(環(huán)游)是經(jīng)過圖所有邊的最短跡(回路)歐拉跡(環(huán)游)在我國(guó)亦稱“一筆畫問題”,即筆不離線,每條邊只畫一次而不許重復(fù)的畫完圖形。兩者完全等價(jià)8/8IEuler圖741Euler圖定理對(duì)于非空連通圖G,下列命題等價(jià)(1)G是Euler圖;(2)G無奇次數(shù)頂點(diǎn);(3)G的邊集能劃分為圈。1Euler圖751048104876可行遍性及賽題講解課件77可行遍性及賽題講解課件78可行遍性及賽題講解課件79可行遍性及賽題講解課件80可行遍性及賽題講解課件81可行遍性及賽題講解課件82可行遍性及賽題講解課件83可行遍性及賽題講解課件84可行遍性及賽題講解課件85可行遍性及賽題講解課件86可行遍性及賽題講解課件87可行遍性及賽題講解課件88可行遍性及賽題講解課件89可行遍性及賽題講解課件90可行遍性及賽題講解課件91可行遍性及賽題講解課件92可行遍性及賽題講解課件93可行遍性及賽題講解課件94可行遍性及賽題講解課件95可行遍性及賽題講解課件96可行遍性及賽題講解課件97可行遍性及賽題講解課件98可行遍性及賽題講解課件99可行遍性及賽題講解課件100可行遍性及賽題講解課件101可行遍性及賽題講解課件102可行遍性及賽題講解課件103可行遍性及賽題講解課件104可行遍性及賽題講解課件105可行遍性及賽題講解課件106可行遍性及賽題講解課件107可行遍性及賽題講解課件108可行遍性及賽題講解課件109可行遍性及賽題講解課件110可行遍性及賽題講解課件111可行遍性及賽題講解課件112可行遍性及賽題講解課件113可行遍性及賽題講解課件114可行遍性及賽題講解課件115可行遍性及賽題講解課件116可行遍性及賽題講解課件117可行遍性及賽題講解課件118可行遍性及賽題講解課件119可行遍性及賽題講解課件120可行