離散數(shù)學(xué)英文講義：8-5 Euler and Hamilton Paths

1、L o g oL o g o1Discrete MathematicsSouth China University of TechnologyDr. Han HuangL o g oL o g o2Section 8.5Chapter 8. GraphsL o g oL o g oContentsEuler Paths and Circuit1Hamilton Paths and Circuit2L o g oL o g oEuler Paths and CircuitL o g oL o g oKonigsberg Seven Bridges ProblemL o g oL o g oKon

2、igsberg Seven Bridges ProblemvThe Swiss mathematician Leonhard Euler solved this problem. His solution, published in 1736, may be the first use of graph theory.vEuler studied the problem by using a multiple graph.The original problemEquivalent multigraphL o g oL o g oEuler circuitvDefinition 1: vAn

3、Euler circuit in a graph G is simple circuit containing every edge of G.vAn Euler path in G is a simple path containing every edge of G.No solution!L o g oL o g oExample 1adbceG1vThe graph G1 has an Euler circuit, for example a, e, c, d, e, b, a.L o g oL o g oExample 1vG2 does not have an Euler circ

4、uit.vG2 does not have an Euler path, either.adbceG2L o g oL o g oExample 1adbceG3vG3 does not have an Euler circuit.vG3 has an Euler path: a, c, d, e, b, d, a, b.L o g oL o g oNecessary and Sufficient ConditionsvThere are simple criteria for determining whether a multiple has an Euler circuit and Eu

5、ler path.vAn Euler circuit begins with a vertex a and continues with an edge incident to a, say a,b.vThe edge a, b contributes one to deg(a).vEach time the circuit passes through a vertex it contributes two to the vertexs degree, since the circuit enters via an edge incident with this vertex and lea

6、ves via another such edge.L o g oL o g oNecessary and Sufficient ConditionsvTherefore, deg(a) must be even, because the circuit contributes two every time when it passes through a.vWe conclude that if a connected graph has an Euler circuit, then every vertex must have even degree.vTherefore, if a co

7、nnected graph has an Euler circuit, then every vertex must have even degree.Necessary condition!L o g oL o g oNecessary and Sufficient ConditionsvIs this necessary condition for the existence of an Euler circuit also sufficient?vAn Euler circuit exists in a connected multigraph if all vertices have

8、even degree?vThe proof is given with a construction.vSuppose that the degree of every vertex of G is even. vWe can build a simple path x0,x1,x1,x2,xn-1,xn where x0=a is an arbitrary vertex.L o g oL o g ovIt begins at a with an edge of the form a, x, and it terminates at a with an edge of the form y,

9、 a.vEach time the path goes through a vertex with even degree, it uses only one edge to enter this vertex,vSo that at least one edge remains for the path to leave the vertex.abcfaedL o g oL o g ovAn Euler circuit has been constructed if all the edges have been used.vOtherwise, consider the subgraph

10、H obtained from G by deleting the edges already used and vertices that are not incident with any edges.vWhen we delete the circuit a, f, c, b, a from the graph in Figure 5, we obtain the subgraph labeled as H.L o g oL o g ovSince G is connected, H has at least one vertex in common with the circuit t

11、hat has been deleted. Let w be such a vertex.cedabcfaedGHL o g oL o g ovEvery vertex in H has even degree. vH may not be connected. vBeginning at w, construct a simple path in H by choosing edges as long as possible, as was done in G.vThis path must terminate at w.vFor instance, c, d, e, c is a path

12、 in H. Form a circuit in G by splicing the circuit in H with the original circuit in G.L o g oL o g ovForm a circuit in G by splicing the circuit in H with the original circuit in G. This can be done since w is one of the vertices in this circuit.vWhen this is done in the graph in Figure 5, we obtai

13、n the circuit a, f, c, d, e, c, b, a.cedabcfaedGHL o g oL o g ovContinue this process until all edges have been used.vThe process must terminate since there are only a finite number of edges in the graph.vThis produces an Euler circuit .vIf the vertices of a connected multigraph all have even degree

14、, then the graph has an Euler circuit.L o g oL o g ovTheorem 1: A connected multigraph has an Euler circuit if and only if each of its vertices has even degree.v4 vertices of odd degree, it does not have an Euler circuit.L o g oL o g oExample 2vH1 does not have an Euler circuit.vH1 does not have an

15、Euler path, either.adbcH1L o g oL o g oExample 2vH2 has an Euler circuit: a, g, c, b, g, e, d, f, aadbcH2feL o g oL o g oExample 2vH3 does not have an Euler circuit.vH3 has an Euler path: c, a, b, c, d, bcadbH3L o g oL o g oMore examplesv(a) and (c) does not have an Euler circuit.v(a) and (c) does n

16、ot have an Euler path, either.v(b) has both an Euler circuit and an Euler path.L o g oL o g oAlgorithmvAlgorithm 1 gives the constructive procedure for finding Euler circuits given in the discussion preceding Theorem 1.vThe algorithm specifies the steps of the procedure more precisely.L o g oL o g o

17、Algorithm 1 Constructing Euler CircuitvProcedure Euler (G: connected mutilgraph with all vertices of even degree)v1: circuit := a circuit in G beginning at an arbitrarily chosen vertex with edges successively added to form a path that returns to this vertex. v2: H := G with the edges of this circuit

18、 removed L o g oL o g oAlgorithm 1 Constructing Euler Circuitv3: while H has edgesvBeginv subcircuit := a circuit in H beginning at a vertex in H that also is the endpoint of an edge of circuit H := H with edges of subcircuit and all isolated vertices removed circuit := circuit with subcircuit inser

19、ted at the appropriate vertexEnd the circuit is an Euler circuit.L o g oL o g oExample vC1 in G：v1 v2 v3 v4 v5 v1vC2 in GC1 : v1 v3 v5 v2 v4 v1vv1 is the shared vertex of C1 and C2.vThe Euler circuit is : v1 v2 v3 v4 v5 v1 v3 v5 v2 v4 v1L o g oL o g oExample 3vMohammed s scimitarsvEvery vertex has e

20、ven degree.vTherefore, we can use algorithm 1 to solve its Euler circuit.acbedfiggjkGL o g oL o g oExample 3acbedfighjk1、a, b, d, c, b, e, i, f, e, a in G2、d, g, h, j, i, h, k, g, f, d in H3、 a, b, d, g, h, j, i, h, k, g, f, d, c, b, e, i, f, e, a GHL o g oL o g ovTheorem 2: A connected multigraph h

21、as an Euler path but not an Euler circuit if and if only if it has exactly two vertices of odd degree.v vMain idea of the proof :vEvery time the path goes through a there is path contributes one to the degree of a.vThe terminal and the beginning vertices have odd degree.L o g oL o g oExample 4vG1 co

22、ntains exactly two vertices of odd degree, namely, b and d.vEuler path: d, a, b, c, d, badbcG1L o g oL o g oExample 4vG2 contains exactly two vertices of odd degree, namely, b and d.vEuler path: b, a, g, f, e, d, c, g, b, c, f, dabgcG2fdeL o g oL o g ovG3 has no Euler path since it six vertices of o

23、dd degree.adbceG3L o g oL o g ov4 vertices of odd degree, it does not have an Euler path, such trip is impossible.L o g oL o g oApplication of Euler pathvChinese postman problemvIf a postman can find an Euler path in the graph that represents the streets the postman needs to cover, this path produce

24、s a route that traverses each street of the route exactly one.vIf no Euler path exists, some streets will have to be traversed more than once.L o g oL o g oHamilton Paths and CircuitL o g oL o g o( Hamilton PathsvAn Euler circuit in a graph G is a simple circuit containing every edge of G.vAn Euler

25、path in G is a simple path containing every edge of G.vA Hamilton circuit is a circuit that traverses each vertex in G exactly once.vA Hamilton path is a path that traverses each vertex in G exactly once. )L o g oL o g oHamilton PathsvDefinition 2: vA path x0, x1, , xn-1, xn in the graph G = is call

26、ed a Hamilton path if V = x0, x1, xn-1, xn and xixj for 0ijn.vA circuit x0, x1, , xn-1, xn is a Hamilton path.L o g oL o g oSource of the terminologyvHamilton path comes from a game, called Voyage Round the word puzzle, invented by Irish mathematician Sir William Rowan Hamilton.vThe puzzle was to st

27、art at a city and travel along the edges of the dodecahedron, visiting each of the other 19 cities exactly once, and back for the first city.L o g oL o g oExample 5vG1 has a Hamilton circuit: a, b, c, d, e, a.aebcdG1L o g oL o g oExample 5vG2 does not have a Hamilton circuit.vG2 has a Hamilton path:

28、 a, b, c, d.abcdG2L o g oL o g oExample 5vG3 does not have a Hamilton circuit.vG3 does not have a Hamilton path.abcdG3gefL o g oL o g ovSurprisingly, there are no known simple necessary and sufficient criteria for the existence of Hamilton circuits. vHowever, some sufficient criteria are know.v1、a g

29、raph with a vertex of degree one cannot have a Hamilton circuit.v2、a Hamilton circuit cannot contain a smaller circuit within it.L o g oL o g oExample 6vThere is no Hamilton circuit in Gvsince G has a vertex of degree one.abdceGL o g oL o g oExample 6HvAll vertices have two degree.vBut H has no Hami

30、lton circuit, for any possible Hamilton circuit have to pass c twice.adbceL o g oL o g oExample 7vWe can form a Hamilton circuit in Kn beginning at any vertex.vSuch a circuit can be built by visiting vertices in any order we choose, which is possible since there are edges in Kn between any two verti

31、ces.L o g oL o g oHamiltonian Path TheoremsvDiracs theorem: If (but not only if) G is connected, simple, has n 3 vertices, and v deg(v) n/2, then G has a Hamilton circuit.vOres theorem : If G is connected, simple, has n3 nodes, and deg(u)+deg(v)n for every pair u,v of non-adjacent nodes, then G has

32、a Hamilton circuit. L o g oL o g o Ores theorem： G是是n階簡(jiǎn)單圖，階簡(jiǎn)單圖，n3，則：，則： (1)如任兩不相鄰結(jié)點(diǎn)如任兩不相鄰結(jié)點(diǎn)u、vV，均有，均有d(u)d(v)n1，則，則在在G中存在一條哈密爾頓路。中存在一條哈密爾頓路。 (2)如任兩不相鄰結(jié)點(diǎn)如任兩不相鄰結(jié)點(diǎn)u、vV，均有，均有d(u)d(v)n，則，則G是哈密爾頓圖。是哈密爾頓圖。 證明證明 (1)先證先證G是連通的。若是連通的。若G不連通，設(shè)不連通，設(shè)G1、G2為其兩為其兩個(gè)連通分支，個(gè)連通分支，u、v分別是分別是G1、G2的結(jié)點(diǎn)，則的結(jié)點(diǎn)，則u、v在在G中不相鄰中不相鄰且有且有

33、d(u)d(v)|V(G1)|1|V(G2)|1n2，與已知矛盾，與已知矛盾，所以所以G是連通的。是連通的。Proof in ChineseL o g oL o g o 再證再證G中存在一條哈密爾頓路。設(shè)中存在一條哈密爾頓路。設(shè) ：v1v2vs是是G的最的最長(zhǎng)的基本路，則長(zhǎng)的基本路，則sn。若。若sn，先證，先證G中必有經(jīng)過中必有經(jīng)過v1、v2、vs的回路。的回路。 若若v1與與vs鄰接，則鄰接，則 與邊與邊v1，vs構(gòu)成一個(gè)回路。若構(gòu)成一個(gè)回路。若v1與與vs不鄰接，因?yàn)椴秽徑?，因?yàn)?：v1v2vs是是G的最長(zhǎng)的基本路，所以的最長(zhǎng)的基本路，所以v1與與vs的的鄰接結(jié)點(diǎn)都在鄰接結(jié)點(diǎn)都在 上。上

34、。 L o g oL o g o設(shè)設(shè)v1的鄰接結(jié)點(diǎn)依的鄰接結(jié)點(diǎn)依 上的順序?yàn)樯系捻樞驗(yàn)?，(2i1iks1)，若，若vs與與 中的結(jié)點(diǎn)都不鄰接，則中的結(jié)點(diǎn)都不鄰接，則d(vs)sk1，于是，于是d(v1)d(vs)ksk1n1，矛盾。，矛盾。所以，存在所以，存在j 1，2，k，使，使vs與鄰接，這時(shí)與鄰接，這時(shí) 構(gòu)成一個(gè)回路。構(gòu)成一個(gè)回路。L o g oL o g o 由由G是連通的，而是連通的，而sn，所以存在，所以存在G的不在的不在 上的結(jié)點(diǎn)上的結(jié)點(diǎn)v，v至少與至少與 上的某個(gè)結(jié)點(diǎn)鄰接。不妨設(shè)上的某個(gè)結(jié)點(diǎn)鄰接。不妨設(shè)v與與vr鄰接，若鄰接，若rij1，則則 構(gòu)成長(zhǎng)度為構(gòu)成長(zhǎng)度為s的基本路；若的基本路；若 ，則則構(gòu)成長(zhǎng)度為構(gòu)成長(zhǎng)度為s的基本路，與的基本路，與 的選取矛盾。的選取矛盾。所以所以sn。 ：v1v2vs就是就是G的一條哈密爾頓路的一條哈密爾頓路. L o g oL o g o(2)(2)如任兩不相鄰結(jié)點(diǎn)如任兩不相鄰結(jié)點(diǎn)u u、v vV V，均有，均有d d( (u u) )d d( (v v)n n，則，則G G是哈密爾頓圖。是哈密爾頓圖。(2)(2)證明：設(shè)證明：設(shè) ：v v1 1v v22vnvn是是G G中的哈密爾頓路，若中的哈密爾頓路，若v v1 1與與vnvn鄰接，則鄰