資源描述：
《最新歐美韓國國貨護膚彩妝精油藥妝禮品 ..99ppt課件.ppt》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。
1、歐美韓國國貨護膚彩妝精油藥妝禮品..997.5EulerandHamiltonPathKonigsberg(哥尼斯堡)七橋問題問題：能否從河岸或小島出發(fā)，通過每一座橋，而且僅僅通過一次回到原地。8/3/20212DerenChen,ZhejiangUniv.Euler(歐拉)1736年對這個問題，給出了否定的回答。將河岸和小島作為圖的頂點，七座橋為邊，構(gòu)成一個無向重圖，問題化為圖論中簡單道路的問題：[定義]歐拉道路（回路）：Ｇ＝（Ｖ，Ｅ），稱包含Ｅ中所有邊的簡單道路為歐拉道路/EulerPath/E道路。包含Ｅ中所有邊
2、的簡單回路為歐拉回路/EulerCircuit/E回路。8/3/20213DerenChen,ZhejiangUniv.若Ｇ2＝（Ｖ2，Ｅ2）是Ｇ1的關(guān)于Ｇ的余圖，Ｅ2＝Ｅ－Ｅ1，但Ｖ1∩Ｖ2≠φ，否則Ｇ不連通，設(shè)Ｃ∈Ｖ1∩Ｖ2，從Ｃ出發(fā)，用上面方法作Ｇ2的簡單回路ｐ2回到Ｃ,這能做到。因為作好ｐ1后，留下頂點的次都是偶次。若ｐ1∪ｐ2經(jīng)過所有邊，則歐拉道路是ｐ1走到Ｃ時，先把ｐ2走完，最后走完ｐ1的余下道路。若ｐ1∪ｐ2仍未經(jīng)過所有邊，將ｐ1∪ｐ2視為ｐ1重復(fù)上述過程，由于Ｅ邊有限，故存在歐拉道路。8/3/20217
3、DerenChen,ZhejiangUniv.例1：（1）頂點的次：A(3),B(2),C(4),D(2),E(6),F(2),G(6),H(2),I(4),J(3）。其中奇次頂點A，J（2）從A出發(fā)，走一條道路（A,C,E,A,B,C,D,E,G,J）8/3/20218DerenChen,ZhejiangUniv.（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)），
4、（F，G），（E，J），（G，H），（G，I），（I，J），（H，I）}Ｖ2＝{E，F(xiàn)，G，H，I，J}E∈（Ｖ1?Ｖ2）8/3/20219DerenChen,ZhejiangUniv.（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），再加入即得歐拉道路。8/3/202110DerenChen,ZhejiangUniv.說明：哥尼斯堡七橋問題，由于四個頂點都是齊次的，不可能
5、有歐拉道路。應(yīng)用與推廣：（1）一筆畫問題；（2）如果齊次頂點個數(shù)為2K個，此問題是K筆畫問題。8/3/202111DerenChen,ZhejiangUniv.例８個頂點均為3次，至少要４筆。8/3/202112DerenChen,ZhejiangUniv.[推論]（歐拉定理）：沒有次為０的孤立頂點的無向圖存在歐拉回路的充要條件是：(1)圖是連通的；(2)圖中沒有奇次頂點。8/3/202113DerenChen,ZhejiangUniv.定理2（有向圖的歐拉定理）：不含出/入次為０的孤立頂點的有向圖具有歐拉道路的充要條
6、件是：(1）弱連通；(2)除了可能有２個頂點，一個入次比出次大１，一個出次比入次大１，其余頂點出次等于入次。推論不含出/入次為０的孤立頂點的有向圖具有歐拉回路的充要條件是：（1）弱連通；（2）所有頂點出次等于入次。8/3/202114DerenChen,ZhejiangUniv.Hamilton(哈密頓)道路問題：１８５９年發(fā)明的一種游戲。在一個實心的正十二面體，20個頂點標(biāo)上世界著名大城市的名字，要求游戲者從某一城市出發(fā)，遍歷各城市一次，最后回到原地。這就是“繞行世界”問題。即找一條經(jīng)過所有頂點（城市）的基本道路（回
7、路）。8/3/202115DerenChen,ZhejiangUniv.[定義]哈密頓道路/回路：Ｇ＝（Ｖ，Ｅ），G中經(jīng)過Ｖ中所有頂點的基本道路稱為哈密頓道路/HamiltonPath，簡稱Ｈ道路。Ｇ＝（Ｖ，Ｅ），G中經(jīng)過Ｖ中所有頂點的基本回路稱為哈密頓回路/HamiltonCircuit，簡稱Ｈ回路。8/3/202116DerenChen,ZhejiangUniv.圖Ａ每個頂點都是奇次的，不存在歐拉道路，但有Ｈ道路。圖Ｂ存在歐拉道路，不存在Ｈ道路。8/3/202117DerenChen,ZhejiangUniv.[定
8、理3]：設(shè)Ｇ＝（Ｖ，Ｅ）是ｎ個頂點的簡單圖，如果任何一對頂點的次之和≥ｎ－１，則Ｇ中一定有Ｈ道路（n>=2）。證明：1、Ｇ一定連通，否則Ｇ分為二個不連通的分圖Ｇ1，Ｇ2，其中Ｇ1有ｎ1個頂點，Ｇ2有ｎ2個頂點，Ｇ1中每個頂點次≤ｎ1－１，Ｇ2中每個頂點次≤ｎ2－１，從Ｇ1中取一個頂點，Ｇ2中取一個頂點，這一對頂點之和≤ｎ1－１＋ｎ
