离散数学英文讲义：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阶简单图，阶简单图，n3，则：，则： (1)如任两不相邻结点如任两不相邻结点u、vV，均有，均有d(u)d(v)n1，则，则在在G中存在一条哈密尔顿路。中存在一条哈密尔顿路。 (2)如任两不相邻结点如任两不相邻结点u、vV，均有，均有d(u)d(v)n，则，则G是哈密尔顿图。是哈密尔顿图。 证明证明 (1)先证先证G是连通的。若是连通的。若G不连通，设不连通，设G1、G2为其两为其两个连通分支，个连通分支，u、v分别是分别是G1、G2的结点，则的结点，则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中存在一条哈密尔顿路。设中存在一条哈密尔顿路。设 ：v1v2vs是是G的最的最长的基本路，则长的基本路，则sn。若。若sn，先证，先证G中必有经过中必有经过v1、v2、vs的回路。的回路。 若若v1与与vs邻接，则邻接，则 与边与边v1，vs构成一个回路。若构成一个回路。若v1与与vs不邻接，因为不邻接，因为 ：v1v2vs是是G的最长的基本路，所以的最长的基本路，所以v1与与vs的的邻接结点都在邻接结点都在 上。上

34、。 L o g oL o g o设设v1的邻接结点依的邻接结点依 上的顺序为上的顺序为 ，(2i1iks1)，若，若vs与与 中的结点都不邻接，则中的结点都不邻接，则d(vs)sk1，于是，于是d(v1)d(vs)ksk1n1，矛盾。，矛盾。所以，存在所以，存在j 1，2，k，使，使vs与邻接，这时与邻接，这时 构成一个回路。构成一个回路。L o g oL o g o 由由G是连通的，而是连通的，而sn，所以存在，所以存在G的不在的不在 上的结点上的结点v，v至少与至少与 上的某个结点邻接。不妨设上的某个结点邻接。不妨设v与与vr邻接，若邻接，若rij1，则则 构成长度为构成长度为s的基本路；若的基本路；若 ，则则构成长度为构成长度为s的基本路，与的基本路，与 的选取矛盾。的选取矛盾。所以所以sn。 ：v1v2vs就是就是G的一条哈密尔顿路的一条哈密尔顿路. L o g oL o g o(2)(2)如任两不相邻结点如任两不相邻结点u u、v vV V，均有，均有d d( (u u) )d d( (v v)n n，则，则G G是哈密尔顿图。是哈密尔顿图。(2)(2)证明：设证明：设 ：v v1 1v v22vnvn是是G G中的哈密尔顿路，若中的哈密尔顿路，若v v1 1与与vnvn邻接，则邻