Bài giảng Toán rời rạc - Chương: Đồ thị Hamilton - Trần Vĩnh Đức

rtex in the graph has degree two, then
 both edges that are incident with this vertex must be part of any Hamilton circuit. Also, note
 that when a Hamilton circuit is being constructed and this circuit has passed through a vertex,
 then all remaining edges incident with this vertex, other than the two used in the circuit, can be
 removed from consideration. Furthermore, a Hamilton circuit cannot contain a smaller circuit
 within it.
Định nghĩa (Đồ thị Hamilton)
 ▶ Một chu trình trong đồ thị G được gọi là chu trình Hamilton
 nếu nó chứa tất cả các đỉnh của G.
 ▶ Một đồ thị được gọi là đồ thị Hamilton nếu nó có chu trình
 Hamilton.
Nói cách khác, đồ thị Hamilton là đồ thị có chu trình bao trùm.
 8 / 24
 10.5 Euler and Hamilton Paths 699
 (a) (b)
 FIGURE 9 A Solution to
 FIGURE 8 Hamilton’s “A Voyage Round the the “A Voyage Round the
 World” Puzzle. World” Puzzle.
 Because the author cannot supply each reader with a wooden solid with pegs and string, we
 will consider the equivalent question: Is there a circuit in the graph shown in Figure 8(b) that
 passes through each vertex exactly once? This solves the puzzle because this graph is isomorphic
 to the graph consisting of the vertices and edges of the dodecahedron. A solution of Hamilton’s
 puzzle is shown in Figure 9.
EXAMPLE 5 Which of the simple graphs in Figure 10 have a Hamilton circuit or, if not, a Hamilton path?
 Solution: G1 has a Hamilton circuit: a,b,c,d,e,a. There is no Hamilton circuit in G2 (this can
 be seen by noting that any circuit containing every vertex must contain the edge a,b twice),
 { }
 but G2 does have a Hamilton path, namely, a,b,c,d. G3 has neither a Hamilton circuit nor a
 Hamilton path, because any path containing all vertices must contain one of the edges a,b ,
 Ví dụ { }
 e, f , and c, d more than once. L
 Đồ{ thị} nào{ dưới} đây là Hamilton?
 a b a b a b g
 e c
 d c d c e f
 G1 G2 G3
 d
 FIGURE 10 Three Simple Graphs.
 CONDITIONS FORTHE EXISTENCE OF HAMILTON CIRCUITS Is there a simple way
 to determine whether a graph has a Hamilton circuit or path? At first, it might seem that there
 should be an easy way to determine this, because there is a simple way to answer the similar
question of whether a graph has an Euler circuit. Surprisingly, there are no known simple
 9 / 24
 necessary and sufficient criteria for the existence of Hamilton circuits. However, many theorems
 are known that give sufficient conditions for the existence of Hamilton circuits. Also, certain
 properties can be used to show that a graph has no Hamilton circuit. For instance, a graph with a
 vertex of degree one cannot have a Hamilton circuit, because in a Hamilton circuit, each vertex
 is incident with two edges in the circuit. Moreover, if a vertex in the graph has degree two, then
 both edges that are incident with this vertex must be part of any Hamilton circuit. Also, note
 that when a Hamilton circuit is being constructed and this circuit has passed through a vertex,
 then all remaining edges incident with this vertex, other than the two used in the circuit, can be
 removed from consideration. Furthermore, a Hamilton circuit cannot contain a smaller circuit
 within it.
700 10 / Graphs Ví dụ
 Đồ thị nào dưới là Hamilton? Nếu không, có là nửa Hamilton?
 a d e a d
 c
 b c b e
 GH
 FIGURE 11 Two Graphs That Do Not Have a Hamilton Circuit.
EXAMPLE 6 Show that neither graph displayed in Figure 11 has a Hamilton circuit.
 10 / 24
 Solution: There is no Hamilton circuit in G because G has a vertex of degree one, namely, e.
 Now consider H . Because the degrees of the vertices a, b, d, and e are all two, every edge
 incident with these vertices must be part of any Hamilton circuit. It is now easy to see that no
 Hamilton circuit can exist in H , for any Hamilton circuit would have to contain four edges
 incident with c, which is impossible. L
EXAMPLE 7 Show that Kn has a Hamilton circuit whenever n 3.
 ≥
 Solution: We can form a Hamilton circuit in Kn beginning at any vertex. Such a circuit can be
 built by visiting vertices in any order we choose, as long as the path begins and ends at the same
 vertex and visits each other vertex exactly once. This is possible because there are edges in Kn
 between any two vertices. L
 Although no useful necessary and sufficient conditions for the existence of Hamilton circuits
 are known, quite a few sufficient conditions have been found. Note that the more edges a graph
 has, the more likely it is to have a Hamilton circuit. Furthermore, adding edges (but not vertices)
 to a graph with a Hamilton circuit produces a graph with the same Hamilton circuit. So as we
 add edges to a graph, especially when we make sure to add edges to each vertex, we make it
 WILLIAM ROWAN HAMILTON (1805–1865) William Rowan Hamilton, the most famous Irish scien-
 tist ever to have lived, was born in 1805 in Dublin. His father was a successful lawyer, his mother came
 from a family noted for their intelligence, and he was a child prodigy. By the age of 3 he was an excel-
 lent reader and had mastered advanced arithmetic. Because of his brilliance, he was sent off to live with
 his uncle James, a noted linguist. By age 8 Hamilton had learned Latin, Greek, and Hebrew; by 10 he had
 also learned Italian and French and he began his study of oriental languages, including Arabic, Sanskrit, and
 Persian. During this period he took pride in knowing as many languages as his age. At 17, no longer de-
 voted to learning new languages and having mastered calculus and much mathematical astronomy, he began
 original work in optics, and he also found an important mistake in Laplace’s work on celestial mechanics.
Before entering Trinity College, Dublin, at 18, Hamilton had not attended school; rather, he received private tutoring. At Trinity, he
was a superior student in both the sciences and the classics. Prior to receiving his degree, because of his brilliance he was appointed
the Astronomer Royal of Ireland, beating out several famous astronomers for the post. He held this position until his death, living
and working at Dunsink Observatory outside of Dublin. Hamilton made important contributions to optics, abstract algebra, and
dynamics. Hamilton invented algebraic objects called quaternions as an example of a noncommutative system. He discovered the
appropriate way to multiply quaternions while walking along a canal in Dublin. In his excitement, he carved the formula in the stone
of a bridge crossing the canal, a spot marked today by a plaque. Later, Hamilton remained obsessed with quaternions, working to
apply them to other areas of mathematics, instead of moving to new areas of research.
In 1857 Hamilton invented “The Icosian Game” based on his work in noncommutative algebra. He sold the idea for 25 pounds
to a dealer in games and puzzles. (Because the game never sold well, this turned out to be a bad investment for the dealer.) The
“Traveler’s Dodecahedron,” also called “A Voyage Round the World,” the puzzle described in this section, is a variant of that game.
Hamilton married his third love in 1833, but his marriage worked out poorly, because his wife, a semi-invalid, was unable to
cope with his household affairs. He suffered from alcoholism and lived reclusively for the last two decades of his life. He died from
gout in 1865, leaving masses of papers containing unpublished research. Mixed in with these papers were a large number of dinner
plates, many containing the remains of desiccated, uneaten chops.
Ví dụ
Chứng minh rằng đồ thị đầy đủ Kn có chu trình Hamilton với mọi
n ≥ 3.
 11 / 24
Mệnh đề
Nếu G = (V, E) có chu trình Hamilton, vậy thì với mọi tập đỉnh
khác rỗng S ⊆ V, đồ thị thu được từ G bằng cách xóa các đỉnh
thuộc S chỉ có nhiều nhất |S| thành phần liên thông.
Chứng minh.
 12 / 24
Ví dụ
Đồ thị sau có phải là Hamilton không?
 13 / 24
Ví dụ
Đồ thị sau đây chỉ ra rằng điều kiện cần trước không phải điều
kiện đủ. Tại sao?
 14 / 24
Bài tập
 Alice và Bob nhìn trộm đề thi Toán Rời Rạc của thầy Đức. Alice
 thấy thầy đang mô tả một đồ thị với 17 đỉnh và 129 cạnh; còn
 Bob thấy thầy hỏi xem đồ thị này có chu trình Hamilton không.
 - Bob nói rằng: ”không cần biết chi tiết đồ thị thầy đang vẽ thế
 nào, chắc chắn đồ thị này có chu trình Hamilton.”
 - Còn Alice nói: ”Nếu không biết chi tiết thì không thể quyết định
 được đồ thị này có chu trình Hamilton hay không.”
 Ai đúng, ai sai? Bạn hãy giải thích.
 15 / 24
Định lý (Ore)
Giả sử G là một đơn đồ thị với n ≥ 3 đỉnh thỏa mãn: với mọi cặp
đỉnh không liền kề u và v, ta có
 deg(u) + deg(v) ≥ n,
khi đó G là đồ thị Hamilton.
 16 / 24
Chứng minh định lý Ore
 ▶ Giả sử định lý không đúng.
 ▶ Tồn tại đồ thị G = (V, E) với n đỉnh và có nhiều cạnh nhất
 thỏa mãn điều kiện của định lý Ore nhưng không là Hamilton.
 Tại sao?
 ▶ Vì G có nhiều cạnh nhất có thể nên đồ thị thu được bằng
 cách thêm một cạnh mới nối hai đỉnh không kề nhau phải có
 chu trình Hamilton chứa cạnh thêm đó. Tại sao?
 ▶ Vậy giữa hai đỉnh bất kỳ trong G có thể nối với nhau bằng
 một đường Hamilton.
 17 / 24
Chứng minh (tiếp)
 ▶
 Vì đồ thị Kn có chu trình Hamilton nên G ≠ Kn.
 ▶
 Vậy tồn tại hai đỉnh v1 và vn không kề nhau trong G,
 ▶ và tồn tại đường Hamilton:
 v1 v2 vn−1 vn
 ...
 18 / 24
Chứng minh (tiếp)
 ▶ ···
 Giả sử v1 kề với k đỉnh là: vi1 , vi2 , , vik và
 2 = i1 < i2 < ··· < ik
 ▶ ≤ ≤
 Đỉnh vn không thể kề với đỉnh vij−1 nào (2 j k) vì nếu
 không sẽ tồn tại chu trình Hamilton:
 −
 v1 v2 vij 1 vij vn−1 vn
 ... ...
 19 / 24
Chứng minh (tiếp)
 −
 v1 v2 vij 1 vij vn−1 vn
 ... ...
 ▶ { }
 Vậy vn không kề với ít nhất k đỉnh vi1−1, vi2−1,..., vik−1, .
 Tức là
 deg(vn) ≤ n − 1 − k
 ▶ Nhưng vậy thì
 n ≤ deg(v1) + deg(vn) ≤ k + (n − 1 − k) = n − 1 
 20 / 24
Định lý (Dirac)
Nếu G là một đồ thị với n ≥ 3 đỉnh thỏa mãn: bậc của mỗi đỉnh ít
nhất bằng n/2, khi đó G là đồ thị Hamilton.
Chứng minh.
 ▶ Với hai đỉnh không kề nhau bất kỳ u và v ta có
 deg(u) + deg(v) ≥ n/2 + n/2 = n
 ▶ Suy ra, G thỏa mãn các điều kiện của định lý Ore, vì thế nó
 có chu trình Hamilton.
 21 / 24
Bài tập
 ▶ Hãy chỉ ra rằng các điều kiện trên không phải điều kiện cần.
 ▶ Có nghĩa rằng: chỉ ra tồn tại đồ thị không thỏa mãn điều kiện
 Dirac mà vẫn có chu trình Hamilton.
 22 / 24
702 10 / Graphs
 complexity would be a major accomplishment because it has been shown that this problem
 is NP-complete (see Section 3.3). Consequently, the existence of such an algorithm would
 imply that many other seemingly intractable problems could be solved using algorithms with
 polynomial worst-case time complexity.
 Applications of Hamilton Circuits
 Hamilton paths and circuits can be used to solve practical problems. For example, many appli-
 cations ask for a path or circuit that visits each road intersection in a city, each place pipelines
 intersect in a utility grid, or each node in a communications network exactly once. Finding a
 Hamilton path or circuit in the appropriate graph model can solve such problems. The famous
 traveling salesperson problem or TSP (also known in older literature as the traveling sales-
 man problem) asks for the shortest route a traveling salesperson should take to visit a set of
 cities. This problem reduces to finding a Hamilton circuit in a complete graph such that the total
 weight of its edges is as small as possible. We will return to this question in Section 10.6.
 We now describe a less obvious application of Hamilton circuits to coding.
EXAMPLE 8 Gray Codes The position of a rotating pointer can be represented in digital form. One way to
 do this is to split the circle into 2n arcs of equal length and to assign a bit string of length n to
 each arc. Two ways to do this using bit strings of length three are shown in Figure 12.
 The digital representation of the position of the pointer can be determined using a set of n
 contacts. Each contact is used to read one bit in the digital representation of the position. This
 is illustrated in Figure 13 for the two assignments from Figure 12.
 When the pointer is near the boundary of two arcs, a mistake may be made in reading its
 position. This may result in a major error in the bit string read. For instance, in the coding
 scheme in Figure 12(a), if a small error is made in determining the position of the pointer, the
 bit string 100 is read instead of 011. All three bits are incorrect! To minimize the effect of an
 error in determining the position of the pointer, the assignment of the bit strings to the 2n arcs
 should be made so that only one bit is different in the bit strings represented by adjacent arcs.
 This is exactly the situation in the coding scheme in Figure 12(b). An error in determining the
 position of the pointer gives the bit string 010 instead of 011. Only one bit is wrong.
 A Gray code is a labeling of the arcs of the circle such that adjacent arcs are labeled with bit
 strings that differ in exactly one bit. The assignment in Figure 12(b) is a Gray code. We can find
 a Gray code by listing all bit strings of length n in such a way that each string differs in exactly
 Mã Gray one position from the preceding bit string, and the last string differs from the first in exactly one
 position. We can model this problem using the n-cube Qn. What is needed to solve this problem
 is a Hamilton circuit in Qn. Such Hamilton circuits are easily found. For instance, a Hamilton
 ▶ Chia đường tròn thành 2n cung có độ dài bằng nhau, và gán
 mỗi xâu bít độ dài n cho một cung.
 (a) (b)
 111 000 100 000
 110 001 101 001
 101 010 111
 011
 100 011 110 010
 ▶ Tìm cáchFIGURE gán đảm 12 bảoConverting rằng hai the cung Position cạnh nhau of a Pointer chỉ khác into Digital Form.
 nhau một bit.
 23 / 24
 10.5 Euler and Hamilton Paths 703
Third bit is 1 here
Second bit is 1 here Third bit is 1 here
Second bit is 1 here
Third bit is 1 here
First bit is 1 here
Third bit is 1 here
First bit is 1 here Mã Gray 2
 110 111
Third bit is 1 here
Third bit is 1 here 100
 101
 010
 011
Second bit is 1 here 000 001
FIGURE 13 The Digital Representation of the FIGUREA Hamilton 14 24 / 24
Position of the Pointer. Circuit for Q3.
circuit for Q3 is displayed in Figure 14. The sequence of bit strings differing in exactly one bit
produced by this Hamilton circuit is 000, 001, 011, 010, 110, 111, 101, 100.
Gray codes are named after Frank Gray, who invented them in the 1940s at AT&T Bell
Laboratories to minimize the effect of errors in transmitting digital signals. L
Exercises
In Exercises 1–8 determine whether the given graph has an 3. a b 4. a
Euler circuit. Construct such a circuit when one exists. If
no Euler circuit exists, determine whether the graph has an
Euler path and construct such a path if one exists. f b
e
1. bc
 d
c d
a d
 e c
e 5. a b
2. a bc
 c
e
d f
e d
g h i