歐美韓國國貨護膚彩妝精油藥妝禮品

歐美韓國國貨護膚彩妝精油藥妝禮品7.1圖的概念/IntroductionofGraph7.2圖的術(shù)語/GraphTerminology7.3圖的表示與同構(gòu)/RepresentingGraphandGraphIsomorphism7.4連通性/Connectivity7.5歐拉道路與哈密爾頓道路/EulerandHamiltonPaths7.6最短道路問題/ShortestPathProblem7.7平面圖/PlanarGraphs7.8圖的著色/GraphColoring12/30/202327.5EulerandHamiltonPathKonigsberg(哥尼斯堡)七橋問題問題：能否從河岸或小島出發(fā)，通過每一座橋，而且僅僅通過一次回到原地。12/30/20233

Euler(歐拉)1736年對這個問題，給出了否定的回答。將河岸和小島作為圖的頂點，七座橋為邊，構(gòu)成一個無向重圖，問題化為圖論中簡單道路的問題：[定義]歐拉道路（回路）：Ｇ＝（Ｖ，Ｅ），稱包含Ｅ中所有邊的簡單道路為歐拉道路/EulerPath/E道路。包含Ｅ中所有邊的簡單回路為歐拉回路/EulerCircuit/E回路。12/30/20234[定理1]（歐拉定理）：沒有次為０的孤立頂點的無向圖存在歐拉道路的充要條件是：(1)圖是連通的；(2)圖中奇次頂點個數(shù)是０個或2個。12/30/20235證明：必要性：若存在歐拉道路，且沒有０次頂點，則每個頂點都有邊關(guān)聯(lián)，而邊又全在歐拉道路上，故所有頂點都連通。除了起點，終點外，歐拉道路每經(jīng)過一個頂點，使頂點的次增加２，故只有起點和終點才可能成為奇次頂點，而一個奇次頂點是不可能的，當(dāng)無奇次頂點時，是歐拉回路。充分性：若(1），(2)成立,構(gòu)造歐拉道路.12/30/20236

若圖Ｇ存在奇次頂點，任取一個作為起點，若不存在，則任取一個頂點作為起點。若此圖有ｎ條邊，總次為２ｎ。每進入或離開一個頂點，讓此頂點的次減１，由于除了兩個（或沒有）奇次頂點外，其余頂點次為偶數(shù)，只要進得去，一定出得來，直至進入另一個奇次頂點（或起點）作為終點。這樣構(gòu)造的是簡單道路，如果經(jīng)過所有的邊，即得到一條歐拉道路。

不然，記走過的簡單道路為ｐ1，ｐ1上頂點集Ｖ1，邊集Ｅ1，Ｇ1＝（Ｖ1，Ｅ1）是Ｇ的子圖。12/30/20237

若Ｇ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ù)上述過程，由于Ｅ邊有限，故存在歐拉道路。12/30/20238例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）12/30/20239（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＝{E，F(xiàn)，G，H，I，J}E∈（Ｖ1

Ｖ2）12/30/202310（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），再加入即得歐拉道路。12/30/202311說明：哥尼斯堡七橋問題，由于四個頂點都是齊次的，不可能有歐拉道路。應(yīng)用與推廣：（1）一筆畫問題；

（2）如果齊次頂點個數(shù)為2K個，此問題是K筆畫問題。

12/30/202312例８個頂點均為3次，至少要４筆。12/30/202313[推論]（歐拉定理）：沒有次為０的孤立頂點的無向圖存在歐拉回路的充要條件是：(1)圖是連通的；(2)圖中沒有奇次頂點。12/30/202314定理2（有向圖的歐拉定理）：不含出/入次為０的孤立頂點的有向圖具有歐拉道路的充要條件是：(1）弱連通；(2)除了可能有２個頂點，一個入次比出次大１，一個出次比入次大１，其余頂點出次等于入次。推論不含出/入次為０的孤立頂點的有向圖具有歐拉回路的充要條件是：（1）弱連通；（2）所有頂點出次等于入次。12/30/202315Hamilton(哈密頓)道路問題：

１８５９年發(fā)明的一種游戲。在一個實心的正十二面體，20個頂點標(biāo)上世界著名大城市的名字，要求游戲者從某一城市出發(fā)，遍歷各城市一次，最后回到原地。這就是“繞行世界”問題。即找一條經(jīng)過所有頂點（城市）的基本道路（回路）。12/30/202316[定義]哈密頓道路/回路：Ｇ＝（Ｖ，Ｅ），G中經(jīng)過Ｖ中所有頂點的基本道路稱為哈密頓道路/HamiltonPath，簡稱Ｈ道路。Ｇ＝（Ｖ，Ｅ），G中經(jīng)過Ｖ中所有頂點的基本回路稱為哈密頓回路/HamiltonCircuit，簡稱Ｈ回路。12/30/202317圖Ａ每個頂點都是奇次的，不存在歐拉道路，但有Ｈ道路。圖Ｂ存在歐拉道路，不存在Ｈ道路。12/30/202318[定理3]：設(shè)Ｇ＝（Ｖ，Ｅ）是ｎ個頂點的簡單圖，如果任何一對頂點的次之和≥ｎ－１，則Ｇ中一定有Ｈ道路（n>=2）。證明：1、Ｇ一定連通，否則Ｇ分為二個不連通的分圖Ｇ1，Ｇ2，其中Ｇ1有ｎ1個頂點，Ｇ2有ｎ2個頂點，Ｇ1中每個頂點次≤ｎ1－１，Ｇ2中每個頂點次≤ｎ2－１，從Ｇ1中取一個頂點，Ｇ2中取一個頂點，這一對頂點之和≤ｎ1－１＋ｎ2－１＝ｎ1＋ｎ2－２＝ｎ－２＜ｎ－１，與定理的假設(shè)矛盾。12/30/2023192、用歸納法證明Ｇ中存在Ｈ道路：(1)任取一條邊（Ｖ1，Ｖ2），是含２個頂點的基本道路。(2)如果已有ｐ個頂點的基本道路（Ｖ1，Ｖ2，…，Ｖp），（ｐ≤ｎ－１）必能構(gòu)造ｐ＋１個頂點的基本道路。ａ）如果在Ｖ－｛Ｖ1，Ｖ2，…Ｖp｝中存在與Ｖ1或Ｖp相鄰的頂點，則基本道路自然可以擴充一個頂點。ｂ）如果Ｖ1，Ｖp僅與｛Ｖ1，Ｖ2，…，Ｖp｝中頂點相鄰，則｛Ｖ1，Ｖ2，…，Ｖp｝必可適當(dāng)排列，形成回路。12/30/202320

如果Ｖ1與Ｖp相鄰，顯然成了環(huán)。不然，由于Ｖ1，Ｖp僅與｛Ｖ1，Ｖ2，…，Ｖp｝中頂點相鄰，Ｖ1，Ｖp的次≤ｐ－１。不妨設(shè)Ｖ1的次為ｋ≤ｐ－１，分別記相鄰頂點為Ｖi1，Ｖi2，…，Ｖik，它們前面的頂點（指在基本道路｛Ｖ1，Ｖ2，…，Ｖp｝中的序）為，Ｖp必與中某頂點相鄰，否則Ｖp的次≤ｐ－１－ｋ，Ｖ1與Ｖp的次之和≤ｋ＋ｐ－１－ｋ＝ｐ－１＜ｎ－１，與任一對頂點次之和≥ｎ－１矛盾。不妨Ｖp與Ｖj-1相鄰，Ｖ1與Ｖj相鄰。將Ｖ1與Ｖj連起來，Ｖp與Ｖj-1連起來，并將Ｖj-1到Ｖj的邊去掉，就形成一個環(huán)，如下圖所示。12/30/202321

又由Ｇ的連通性，總可在Ｖ－｛Ｖ1，Ｖ2，…，Ｖp｝中找到一個點Ｖx，與｛Ｖ1，Ｖ2，…，Ｖp｝中某一頂相鄰，不妨與Ｖk相鄰，Ｖk≠Ｖ1，Ｖk≠Ｖp，連上Ｖx與Ｖk的邊，去掉Ｖk-1到Ｖk的邊，可以從Ｖk-1為起點，一直走到Ｖk，再到Ｖx，這是一條ｐ＋１個頂點的基本道路。12/30/202322

如果ｐ＋１＜ｎ，仍繼續(xù)擴充基本道路內(nèi)的頂點，直至達到ｎ。注意:此定理條件顯然不是必要條件，如ｎ≥６的ｎ邊形，二個頂點次之和＝４，４＜ｎ－１，而ｎ邊形顯然有Ｈ道路。[推論]：Ｇ＝（Ｖ，Ｅ）是ｎ≥３的簡單圖，若任何一對頂點的次之和≥ｎ，則Ｇ必有哈密頓回路。12/30/202323

由于推論條件也必滿足定理3條件，存在Ｈ道路，可類似于定理一的方法找到一條回路。[定理4]：有向完全圖一定存在Ｈ道路。12/30/202324小結(jié)1、E圖：簡單道路+所有邊2、H圖：基本道路+所有頂點12/30/202325進一步的思考1、E圖/H圖的應(yīng)用2、E圖/H圖的判定12/30/202326

要判別一個圖不存在Ｈ道路，Ｈ回路，也不是很容易的，只能對無向圖給出一些必要條件：（1）Ｈ道路存在必要條件：１）連通２）至多只能有二個頂點的次＜２，其余頂點的次≥２。bcda12/30/202327（2）Ｈ回路存在必要條件：對Ｖ的任一非空真子集Ｓ，Ｇ－Ｓ的連通分圖個數(shù)≤|Ｓ|。12/30/202328解：取Ｓ＝｛A1，A