Số hóa bởi Trung tâm Học liệu

i
ĐẠI HỌC THÁI NGUYÊN
TRƢỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG LUẬN VĂN THẠC SỸ KHOA HỌC MÁY TÍNH Nguyễn Tam Hùng CÁC THUẬT TOÁN VỀ ĐƢỜNG ĐI VÀ
CHU TRÌNH EULER VÀ ỨNG DỤNG Ngành: Công nghệ thông tin
Chuyên ngành: Khoa học máy tính
Mã số: 60.48.01

Người hướng dẫn khoa học: PGS TSKH Nguyễn Xuân Huy
Số hóa bởi Trung tâm Học liệu

ii
LỜI CAM ĐOAN

Học viên xin cam đoan, toàn bộ nội dung liên quan tới đề tài được trình bày
trong luận văn là bản thân học viên tự tìm hiểu và nghiên cứu, dưới sự hướng
dẫn khoa học của Thầy giáo PGS TSKH Nguyễn Xuân Huy.
Các tài liệu, số liệu tham khảo được trích dẫn đầy đủ nguồn gốc. Học viên
xin chịu trách nhiệm trước pháp luật lời cam đoan của mình.

Thái Nguyên, ngày 15 tháng 5 năm 2014
Học viên thực hiện Nguyễn Tam Hùng
Số hóa bởi Trung tâm Học liệu

iii
MỤC LỤC
LỜI CẢM ƠN I
LỜI CAM ĐOAN II
MỤC LỤC III
DANH MỤC CÁC BẢNG IV


DANH MỤC CÁC BẢNG

Trang
Bảng 1.1 Ma trận kề của đồ thị G hình 1.7 12
Bảng 1.2 Ma trận liên thuộc của đồ thị G hình 1.7 14
Bảng 1.3 Danh sách cạnh của đồ thị G hình 1.7 14
Bảng 2.1 Các bước thực hiện thuật toán Hierholzer để tìm chu trình Euler 29
Bảng 2.2 Các bước thực hiện thuật toán Hierholzer để tìm đường đi Euler 30
Bảng 3.1 Kết quả của đồ thị Domino 38
Bảng 3.2 Số cạnh nối thêm giữa các cặp đỉnh bậc lẻ 42
Bảng 3.3 Cách chọn cặp đỉnh bậc lẻ và số cạnh nối thêm 43
Bảng 3.4 Chu trình Euler tìm được với đồ thị G
T
45

Số hóa bởi Trung tâm Học liệu

vi

DANH MỤC CÁC HÌNH VẼ, ĐỒ THỊ
Trang
Hình 1.1 Đồ thị vô hướng với 7 đỉnh và 8 cạnh 4
Hình 1.2 Đồ thị đầy đủ với 5 đỉnh 5
Hình 1.3 Đồ thị có vectơ bậc [3, 3, 2, 2] 6
Hình 1.4 Đồ thị có vectơ bậc [5, 4, 4, 3, 3, 3, 2] 8
Hình 1.5 Đồ thị vô hướng liên thông 9
Hình 1.6 Đồ thị vô hướng G với 7 đỉnh 8 cạnh 10
Hình 1.7 Đồ thị vô hướng G với 5 đỉnh 8 cạnh 12
Hình 2.1 Đồ thị G với 6 đinh 8 cạnh 15


1
LỜI MỞ ĐẦU

Những vấn đề cơ bản của lý thuyết đồ thị được đề xuất từ thế kỷ XVIII,
bắt đầu từ bài báo của Euler công bố năm 1736 liên quan đến lời giải bài toán nổi
tiếng về các cây cầu ở Königsberg. Tại thành phố Königsberg nước Đức có sông
Pregel bao quanh 2 đảo lớn. Hai đảo này được nối với các vùng đất thành phố
bởi 7 cây cầu. Cư dân thành phố đặt ra bài toán: có thể xuất phát tại một điểm và
đi qua 7 cây cầu, mỗi cây cầu chỉ được đi qua đúng một lần, và trở về điểm xuất
phát được không? Và nhà toán học L.Euler đã trả lời trọn vẹn cho bài toán này.
Người ta lấy tên cho bài toán trên là tên của nhà toán học Euler. Tuy nhiên, cho
tới nay mối quan tâm đến lý thuyết đồ thị không hề suy giảm. Lý do của sự quan
tâm ấy chính là sự vận dụng rộng rãi của đồ thị trong rất nhiều lĩnh vực khác
nhau. Chẳng hạn, đồ thị có thể xác định các mạch vòng trong vấn đề giải tích
mạch điện. Chúng ta có thể phân biệt các hợp chất hóa học hữu cơ khác nhau với
cùng công thức phân tử nhưng khác nhau về cấu trúc phân tử nhờ đồ thị. Chúng
ta có thể xác định xem hai máy tính trong mạng có thể trao đổi thông tin được
với nhau hay không nhờ mô hình đồ thị mạng máy tính. Đồ thị có trọng số trên
các cạnh có thể sử dụng để giải các bài toán như: Tìm đường đi ngắn nhất giữa
hai thành phố trong một mạng giao thông. Chúng ta cũng còn sử dụng đồ thị để
giải các bài toán về lập lịch, thời khóa biểu, và phân bố tần số cho các trạm phát
thanh truyền hình
Hiện nay, một vài tài liệu viết về nội dung này được đưa vào giảng dạy như
Toán rời rạc ứng dụng trong tin học (bản dịch) của tác giả Kenneth H.Rosen [1]
hay Toán rời rạc của Nguyễn Đức Nghĩa, Nguyễn Tô Thành [2]. Trong cuốn

Số hóa bởi Trung tâm Học liệu

2

Lý thuyết đồ thị đã được khoa học phát triển từ rất lâu nhưng lại có nhiều
ứng dụng hiện đại. Đặc biệt trong khoảng vài mươi năm trở lại đây, cùng với sự
ra đời của máy tính điện tử và sự phát triển nhanh chóng của tin học, lý thuyết đồ
thị càng được quan tâm đến nhiều hơn. Ví dụ như trong kiến trúc máy tính, tổ
chức và tìm kiếm dữ liệu trên mạng …
Trong chương 1 sẽ trình bày những khái niệm tổng quan cơ bản về lý thuyết
đồ thị như: định nghĩa một đồ thị, bậc của đồ thị, tính liên thông, đường đi, chu
trình của đồ thị …
1.1 Đồ thị vô hướng
Định nghĩa 1.1
Đồ thị vô hướng: G = (V, E) gồm một tập V các đỉnh và tập E các cạnh [2]
Mỗi cạnh e E được liên kết với một cặp đỉnh v, w ( không kể thứ tự) như hình
sau

Số hóa bởi Trung tâm Học liệu

4

Hình 1.1 Đồ thị vô hướng với 7 đỉnh và 8 cạnh

Hình 1.1 là một đồ vô hướng bao gồm:
- Tập đỉnh V = {1; 2; 3; 4; 5; 6;7}
- Tập cạnh E = {(1, 1); (1, 2); (2, 3); (3, 4); (4; 5); (4; 6); (1, 5)}
1.2 Bậc của đồ thị
Cho đồ thị G = (V, E)
Định nghĩa 1.2
Bậc của đỉnh v V là tổng số cạnh liên thuộc với nó và ký hiệu là d(v). Nếu đỉnh
có khuyên thì mỗi khuyên được tính là 2 khi tính bậc, như vậy
d(v) = số cạnh liên thuộc + 2* Số khuyên
Từ định nghĩa suy ra đỉnh cô lập trong đồ thị đơn là đỉnh có bậc bằng 0

là đồ thị đơn, đủ n đỉnh ( mỗi cặp đỉnh đều có duy nhất 1 cạnh liên
kết)
Ví dụ 1.2.2

Hình 1.2 Đồ thị đầy đủ với 5 đỉnh
Trong Hình 1.2 đồ thị K là một đồ thị đầy đủ có tất cả 5 đỉnh, mỗi cặp đỉnh đều có
duy nhất 1 cạnh liên kết.
Mệnh đề 1.1 Mọi đỉnh của đồ thị K
n
có bậc n – 1 và K
n
có n(n – 1) / 2 cạnh
1
2
3
4
5

Số hóa bởi Trung tâm Học liệu

6
Định nghĩa 1.5
Cho đồ thị G. Vectơ bậc d(V) của đồ thị G là dãy các bậc của tất cả các đỉnh của G
sắp xếp giảm dần.
Vectơ v gồm các số tự nhiên gọi là Vectơ đồ thị. Nếu tồn tại đơn thì đồ thị có vectơ bậc
là v.
Ghi chú: Từ bổ đề bắt tay suy ra trong vectơ đồ thị số thành phần lẻ là số chẵn.
Ví dụ 1.2.3
Vectơ [3, 3, 2, 2] là Vectơ đồ thị vì nó là vectơ bậc của đồ thị sau


là vectơ đồ thị.
1
2
3
4

Số hóa bởi Trung tâm Học liệu

7
Sử dụng định lý Hakimi- Havel ta có thể đưa ra thuật toán kiểm tra xem 1 vectơ có
phải là vectơ đồ thị không như sau
Thuật toán 1.1 Kiểm tra vectơ đồ thị
* Đầu vào: vectơ v= [d
1
, d
2
, , d
n
] gồm n số nguyên giảm dần
* Đầu ra: kết luận v là vectơ đồ thị hay v không là vectơ đồ thị
* Các bước:
Bước 0( khởi tạo): Đặt k: = n và u: = v = [d
1
, d
2
, , d
n
]
Bước 1: Nếu u có thành phần lơn hơn ( k – 1) hoặc nhỏ hơn 0, thì sang bước 4.
Bước 2: Nếu các thành phần của u đều là số 0 thì sang bước 5

Kết luận v là vectơ đồ thị. Đồ thị sau có vectơ bậc là v = [5, 4, 4, 3, 3, 3, 2]

Số hóa bởi Trung tâm Học liệu

8

Hình 1.4 Đồ thị có vectơ bậc [5, 4, 4, 3, 3, 3, 2]

1.3 Đường đi, chu trình, tính liên thông
Định nghĩa 1.7
Cho đồ thị G = (V, E).
Dây từ đỉnh v đến đỉnh w là dãy các đỉnh và cạnh nối tiếp nhau bắt đầu từ đỉnh v
và kết thúc tại đỉnh w. Số cạnh trên dãy gọi là độ dài của dãy .
Dây từ đỉnh v đến đỉnh n được biểu diễn như sau
= (v, e
1
, v
1
, e
2
, v
2
, …, v
n-1
, e
n
, w)
trong đó v
i
(i = 1, …, n-1) là các đỉnh trên dãy và e

w.
ii) Trong đồ thị có hướng mỗi dãy có hướng từ đỉnh v đến w chứa đương đi có
hướng sơ cấp từ v đến w.
Định lý 1.9 Đồ thị G lưỡng phân khi và chỉ khi G không chứa chu trình độ dài lẻ
Định nghĩa 1.10
Cho đồ thị G = (V, E). Đồ thị G’ = (V’, E’) gọi là đồ thị con của G nếu
V’ V  E’ E
Nếu V’ = V thì G’ gọi là đồ thì con phủ của G.
6
4
5
1
2
3

Số hóa bởi Trung tâm Học liệu

10
Nếu F E, thì ký hiệu G-F là đồ thị con (V, E-F) của G gồm tập đỉnh V và tập
cạnh (cung) E-F.
Nếu U V, thì ký hiệu G-U là đồ thị con của G thu được từ G sau khi loại bỏ các
đỉnh trong U và các cạnh liên thuộc chúng.
Cho U V. Đồ thị con của G sinh bởi U, ký hiệu <U>, là đồ thị (U, E
U
) với
E
U
= {e E / e liên thuộc đỉnh trong U}
Đồ thị con G’ = (V’, E’) của đồ thị (có hướng) G = (V, E) gọi là thành phần liên
thông (mạnh) của đồ thị G, nếu nó là đồ thị con liên thông (mạnh) tối đại của G, tức là

7

Số hóa bởi Trung tâm Học liệu

11
Ghi chú: Đồ thị là liên thông khi và chỉ khi số thành phần liên thông của nó bằng 1
Định lý 1.11 Cho đồ thị đơn G = (V, E) với n đỉnh, và k thành phần liên thông. Khi đó
số cạnh m của đồ thị thỏa bất đẳng thức
n – k m
2
)1)(( knkn

Hệ quả 1.2 Mọi đơn đồ thị n đỉnh với số cạnh lớn hơn
2
)2)(1( nn
là liên thông.
Định nghĩa 1.12
Cho đồ thị G = (V, E) liên thông.
Tập cạnh F E gọi là tập hợp tách cạnh của đồ thị liên thông G, nếu G-F không
liên thông. Hơn nữa, nếu F là tập hợp tách cạnh cực tiểu(tức không tồn tại F’ F, F’
F, F’ là tập tách cạnh), thì F gọi là tập cắt cạnh. Nếu tập cắt cạnh chỉ có 1 cạnh, thì
cạnh đó gọi là cầu.
Đại lượng
(G) = min{card(F) / F là tập tách cạnh của G}
gọi là số liên thông cạnh của G.
Đồ thị G gọi là k cạnh liên thông, nếu mọi tập tách cạnh có ít nhất k cạnh.
Ghi chú. Từ định nghĩa ta có
(G) k k, G là k cạnh liên thông
Và (G) = max{k / G là k cạnh liên thông}
1.4 Biểu diễn đồ thị vô hướng

Mệnh đề 1.2. Cho đồ thị G = (V, E) với ma trận kề (a
ij
). Khi đó
d(v
i
) =
n
j 1
a
ij
+a
ii
=
n
j 1
a
ji
+a
ii
v
i,j


5
1
0
1
1
0
1
2
1
0
0
1
0
3
1
0
0
1
1
4
0
1
1
0
1
5
1
0
1

} và ma trận kề của đồ thị
G là ma trận A = (a
ij
)
nxn
. Ký hiệu
T = A + A
2
+ …+ A
n-1
.
Khi đó đồ thị G liên thông khi và chỉ khi các phần tử ngoài đường chéo
chính của ma trận T đều lớn hơn 0.
+ Chú ý. Nếu đồ thị có 2 thành phần liên thông thì ta có thể đánh số lại các đỉnh và ma
trận kề có dạng

2
1
0
0
A
ANếu đồ thị là lưỡng phân thì ta có thể đánh số lại các đỉnh và ma trận kề có
dạng

0
0
T

ij
= 1 nếu cạnh e
j
nối với đỉnh v
i

Thí dụ 1.4.2.1

Giả sử e
1
={1, 2}; e
2
={1, 3}; e
3
={1, 5}; e
4
={2, 4}; e
5
={2, 4}; e
6
={3, 5}; e
7
={3, 5};

Số hóa bởi Trung tâm Học liệu

14
Khi đó ma trận liên thuộc tương ứng sẽ là:

e

0
1
0
0
1
1
0
4
0
0
0
1
1
0
1
5
0
0
1
0
0
1
1
Bảng 1.2 Ma trận liên thuộc của đồ
thị G hình 1.7

1.4.3 Danh sách kề
Biểu diễn đồ thị bởi danh sách kề là liệt kê tất cả các đỉnh liền kề với mỗi đỉnh của
đồ thị. [2]
Thí dụ 1.4.3.1

Cho đồ thị G = (V, E).
Chu trình Euler là chu trình qua mọi cạnh và mọi đỉnh của đồ thị, mỗi cạnh không
quá 1 lần.
Đường đi Euler là đường đi qua mọi cạnh và mọi đỉnh của đồ thị, mỗi cạnh không
quá 1 lần.
Cho đồ thị có hướng G = (V, E).
Đồ thị chứa chu trình Euler gọi là Đồ thị Euler.
Thí dụ 2.1.1 Đồ thị

Hình 2.1 Đồ thị G với 6 đinh 8 cạnh
Có chu trình Euler là: (1, 2, 3, 4, 2, 5, 6, 3, 1).
1
2
3
6
5
5
5
4

Số hóa bởi Trung tâm Học liệu

16
2.1.2 Điều kiện cần và đủ.
Định lý 2.1 (Định lý Euler)
Đồ thị G có chu trình Euler khi và chỉ khi G liên thông và mọi đỉnh có bậc chẵn.
Chứng minh :
(i) : Giả sử G có chu trình Euler và v là một đỉnh bất kì của G. Khi đó chu trình
Euler đến v theo cạnh e thì ra khỏi v bằng cạnh e’ e. Do đó bậc của G phải là số chẵn.
G hiển nhiên liên thông.

, G
2
có chu trình Euler C
2
. Ta xây dựng
chu trình Euler của G như sau:

Số hóa bởi Trung tâm Học liệu

17
Xuất phát từ đỉnh a ta đi theo chu trình C
1
, quay về a sau đó ta đi theo cạnh x=(a,
b) đến đỉnh b, rồi từ b đi theo chu trình C
2
quay về b, sau đó đi theo cạnh z = (b, c),
y=(c, a) quay về a.
*/ G’ có 3 thành phần liên thông G
1
, G
2
và G
3
. Không mất tính tổng quát giả sử G
1

chứa a, G
2
chứa b và G
3

và y ta thu được chu trình Euler C của G.
*/ G’ có 2 thành phần liên thông G
1
và G
2
. Không mất tính tổng quát giả sử G
1

chứa a, G
2
chứa b và c. G
1
có chu trình Euler C
1
, G
2
có chu trình Euler C
2
. Ta xây dựng
chu trình Euler của G như sau:
Thay cạnh z
2
C
bằng các cạnh x và y ta có chu trình C
2
’. Nối C
2
’ với C
1
ta thu