歐美韓國國貨護(hù)膚彩妝精油藥妝禮品。。doc資料.ppt

《歐美韓國國貨護(hù)膚彩妝精油藥妝禮品。。doc資料.ppt》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、歐美韓國國貨護(hù)膚彩妝精油藥妝禮品。。Euler(歐拉)1736年對(duì)這個(gè)問題，給出了否定的回答。將河岸和小島作為圖的頂點(diǎn)，七座橋?yàn)檫叄瑯?gòu)成一個(gè)無向重圖，問題化為圖論中簡單道路的問題：[定義]歐拉道路（回路）：Ｇ＝（Ｖ，Ｅ），稱包含Ｅ中所有邊的簡單道路為歐拉道路/EulerPath/E道路。包含Ｅ中所有邊的簡單回路為歐拉回路/EulerCircuit/E回路。9/4/20212[定理1]（歐拉定理）：沒有次為０的孤立頂點(diǎn)的無向圖存在歐拉道路的充要條件是：(1)圖是連通的；(2)圖中奇次頂點(diǎn)個(gè)數(shù)是０個(gè)或2個(gè)。9/4/20213證明：必要性：若存在

2、歐拉道路，且沒有０次頂點(diǎn)，則每個(gè)頂點(diǎn)都有邊關(guān)聯(lián)，而邊又全在歐拉道路上，故所有頂點(diǎn)都連通。除了起點(diǎn)，終點(diǎn)外，歐拉道路每經(jīng)過一個(gè)頂點(diǎn)，使頂點(diǎn)的次增加２，故只有起點(diǎn)和終點(diǎn)才可能成為奇次頂點(diǎn)，而一個(gè)奇次頂點(diǎn)是不可能的，當(dāng)無奇次頂點(diǎn)時(shí)，是歐拉回路。充分性：若(1），(2)成立,構(gòu)造歐拉道路.9/4/20214若圖Ｇ存在奇次頂點(diǎn)，任取一個(gè)作為起點(diǎn)，若不存在，則任取一個(gè)頂點(diǎn)作為起點(diǎn)。若此圖有ｎ條邊，總次為２ｎ。每進(jìn)入或離開一個(gè)頂點(diǎn)，讓此頂點(diǎn)的次減１，由于除了兩個(gè)（或沒有）奇次頂點(diǎn)外，其余頂點(diǎn)次為偶數(shù)，只要進(jìn)得去，一定出得來，直至進(jìn)入另一個(gè)奇次頂點(diǎn)（或起點(diǎn)

3、）作為終點(diǎn)。這樣構(gòu)造的是簡單道路，如果經(jīng)過所有的邊，即得到一條歐拉道路。不然，記走過的簡單道路為ｐ1，ｐ1上頂點(diǎn)集Ｖ1，邊集Ｅ1，Ｇ1＝（Ｖ1，Ｅ1）是Ｇ的子圖。9/4/20215若Ｇ2＝（Ｖ2，Ｅ2）是Ｇ1的關(guān)于Ｇ的余圖，Ｅ2＝Ｅ－Ｅ1，但Ｖ1∩Ｖ2≠φ，否則Ｇ不連通，設(shè)Ｃ∈Ｖ1∩Ｖ2，從Ｃ出發(fā)，用上面方法作Ｇ2的簡單回路ｐ2回到Ｃ,這能做到。因?yàn)樽骱茫?后，留下頂點(diǎn)的次都是偶次。若ｐ1∪ｐ2經(jīng)過所有邊，則歐拉道路是ｐ1走到Ｃ時(shí)，先把ｐ2走完，最后走完ｐ1的余下道路。若ｐ1∪ｐ2仍未經(jīng)過所有邊，將ｐ1∪ｐ2視為ｐ1重復(fù)上述過程，由于Ｅ邊有

4、限，故存在歐拉道路。9/4/20216例1：（1）頂點(diǎn)的次：A(3),B(2),C(4),D(2),E(6),F(2),G(6),H(2),I(4),J(3）。其中奇次頂點(diǎn)A，J（2）從A出發(fā)，走一條道路（A,C,E,A,B,C,D,E,G,J）9/4/20217（3）Ｇ1＝（Ｖ1，Ｅ1）Ｖ1＝{A，B，C，D，E，G，J}Ｅ1＝{（A，B），（B，C），（A，C），（C，D），（C，E），（D，E），（E，G），（G，J）}Ｇ2＝（Ｖ2，Ｅ2）Ｅ2＝{（E，F(xiàn)），（F，G），（E，J），（G，H），（G，I），（I，J），（H，I）}Ｖ2

5、＝{E，F(xiàn)，G，H，I，J}E∈（Ｖ1?Ｖ2）9/4/20218（4）從E出發(fā)回到E的回路（E，F(xiàn)，G，I，J，E），加入到P1中Ｐ1?＝（A，C，E，F(xiàn)，G，I，J，E，A，B，C，D，G，J）（5）還有未經(jīng)過的邊，重復(fù)上述過程，從G出發(fā)，（G，H，I，G），再加入即得歐拉道路。9/4/20219說明：哥尼斯堡七橋問題，由于四個(gè)頂點(diǎn)都是齊次的，不可能有歐拉道路。應(yīng)用與推廣：（1）一筆畫問題；（2）如果齊次頂點(diǎn)個(gè)數(shù)為2K個(gè)，此問題是K筆畫問題。9/4/202110例８個(gè)頂點(diǎn)均為3次，至少要４筆。9/4/202111[推論]（歐拉定理）：沒有

6、次為０的孤立頂點(diǎn)的無向圖存在歐拉回路的充要條件是：(1)圖是連通的；(2)圖中沒有奇次頂點(diǎn)。9/4/202112定理2（有向圖的歐拉定理）：不含出/入次為０的孤立頂點(diǎn)的有向圖具有歐拉道路的充要條件是：(1）弱連通；(2)除了可能有２個(gè)頂點(diǎn)，一個(gè)入次比出次大１，一個(gè)出次比入次大１，其余頂點(diǎn)出次等于入次。推論不含出/入次為０的孤立頂點(diǎn)的有向圖具有歐拉回路的充要條件是：（1）弱連通；（2）所有頂點(diǎn)出次等于入次。9/4/202113Hamilton(哈密頓)道路問題：１８５９年發(fā)明的一種游戲。在一個(gè)實(shí)心的正十二面體，20個(gè)頂點(diǎn)標(biāo)上世界著名大城市的名

7、字，要求游戲者從某一城市出發(fā)，遍歷各城市一次，最后回到原地。這就是“繞行世界”問題。即找一條經(jīng)過所有頂點(diǎn)（城市）的基本道路（回路）。9/4/202114[定義]哈密頓道路/回路：Ｇ＝（Ｖ，Ｅ），G中經(jīng)過Ｖ中所有頂點(diǎn)的基本道路稱為哈密頓道路/HamiltonPath，簡稱Ｈ道路。Ｇ＝（Ｖ，Ｅ），G中經(jīng)過Ｖ中所有頂點(diǎn)的基本回路稱為哈密頓回路/HamiltonCircuit，簡稱Ｈ回路。9/4/202115圖Ａ每個(gè)頂點(diǎn)都是奇次的，不存在歐拉道路，但有Ｈ道路。圖Ｂ存在歐拉道路，不存在Ｈ道路。9/4/202116[定理3]：設(shè)Ｇ＝（Ｖ，Ｅ）是ｎ個(gè)頂點(diǎn)

8、的簡單圖，如果任何一對(duì)頂點(diǎn)的次之和≥ｎ－１，則Ｇ中一定有Ｈ道路（n>=2）。證明：1、Ｇ一定連通，否則Ｇ分為二個(gè)不連通的分圖Ｇ1，Ｇ2，其中Ｇ1有ｎ1個(gè)頂點(diǎn)，Ｇ2有ｎ2個(gè)頂點(diǎn)，Ｇ