Giáo trình Lý thuyết đồ thị (HCMUTE)

BOÄ GIAÙO DUÏC VAØ ÑAØO TAÏO

TRÖÔØNG ÑAÏI HOÏC SÖ PHAÏM KYÕ THUAÄT THAØNH PHOÁ HOÀ CHÍ MINH
NAÊM XAÂY DÖÏNG VAØ PHAÙT TRIEÅN

50

ĐẶNG TRƯỜNG SƠN - LÊ VĂN VINH

GIÁO TRÌNH

LÝ THUYẾT ĐỒ THỊ

NHAØ XUAÁT BAÛN
ÑAÏI HOÏC QUOÁC GIA TP. HOÀ CHÍ MINH

BỘ GIÁO DỤC VÀ ĐÀO TẠO

TRƢỜNG ĐẠI HỌC SƢ PHẠM KỸ THUẬT
THÀNH PHỐ HỒ CHÍ MINH
*******************

ĐẶNG TRƢỜNG SƠN
LÊ VĂN VINH

GIÁO TRÌNH

LÝ THUYẾT ĐỒ THỊ

NHÀ XUẤT BẢN ĐẠI HỌC QUỐC GIA
THÀNH PHỐ HỒ CHÍ MINH

2

LỜI NÓI ĐẦU
Lý thuyết đồ thị là một trong những môn học căn bản và quan trọng
trong lĩnh vực ứng dụng toán trong tin học. Trong một vài trƣờng hợp Lý
thuyết đồ thị còn đƣợc coi nhƣ là một thành phần của Toán rời rạc. Kiến
thức về Lý thuyết đồ thị có ứng dụng đa dạng trong cuộc sống. Nó cung
cấp các công cụ, phƣơng pháp, thuật toán và hỗ trợ chúng ta xây dựng
các mô hình nhằm giải quyết nhiều bài toán thực tiễn. Lý thuyết đồ thị
hiện là môn học bắt buộc trong chƣơng trình đào tạo các ngành Công
nghệ thông tin, Toán tin, Khoa học máy tính, …
Sau khi học xong môn Lý thuyết đồ thị, sinh viên sẽ có kiến thức
để hiểu và vận dụng đƣợc những qui trình, giải thuật trên đồ thị, có kỹ
năng trong việc lập trình để giải quyết các bài toán trên đồ thị. Một năng
lực quan trọng khác là sinh viên sẽ biết sử dụng đồ thị nhƣ một công cụ
mô hình hóa trong việc mô phỏng các vấn đề thực tế để chuyển thành các
bài toán có thể giải đƣợc trên đồ thị.
Nội dung giáo trình gồm có 8 chƣơng, bao quát hầu hết các vấn đề
cốt lõi của môn học. Giáo trình không đi sâu vào các vấn đề lý thuyết mà
tập trung vào các giải thuật cũng nhƣ tính ứng dụng của môn học. Cuối
mỗi chƣơng đều có phần bài tập để sinh viên có thể tự kiểm tra kiến thức
của mình. Các thuật toán trong giáo trình hầu hết đƣợc trình bày dƣới
dạng mã giả. Phần phụ lục có mã nguồn của một số thuật toán.
Với kinh nghiệm nhiều năm giảng dạy môn Lý thuyết đồ thị tại
trƣờng đại học, chúng tôi đã cố gắng đem những kiến thức và kinh
nghiệm của mình để trình bày các vấn đề nêu trong giáo trình một cách
rõ ràng và đơn giản nhất. Tuy nhiên, cũng không tránh khỏi những thiếu
sót. Trong quá trình biên soạn giáo trình này chúng tôi đã nhận đƣợc
nhiều lời động viên và góp ý của các đồng nghiệp. Chúng tôi xin chân
thành cám ơn và mong muốn tiếp tục nhận đƣợc ý kiến đóng góp của các
giảng viên và các bạn sinh viên để giáo trình ngày càng hoàn thiện hơn.
Mọi ý kiến đóng góp xin vui lòng gửi theo địa chỉ email:
[email protected]
Đặng Trƣờng Sơn – Lê Văn Vinh

3


...

...
ruoc[d]

d[e],
Truoc[e]

d[f],
Truoc[f]

d[g],
Truoc[g]

1

3, a

12, a

∞, a

∞, a

∞, a

∞, a

2

3, a

12, a

-1, b

∞, a

∞, a,

16, c

3

3, a

12, a

-1, b

18, d

14, d

5, d

4

3, a

12, a

-1, b

16, f

12, g

5, d

5

3, a

12, a

-1, b

14, f

12, g

5, d

6

3, a

12, a

-1, b

14, f

12, g

5, d

d[b],
Truoc
[b]

d[c],
Truoc
[c]

d[d],
Truoc
[d]

d[e],
Truoc
[e]

d[f],
Truoc
[f]

d[g],
Truoc
[g]

d[h],
Truoc
[h]

1

3, a

∞, a

15, a

∞, a

∞, a

∞, a

∞, a

2

-

9, b

8, b

12, b

∞, a

17, b

∞, a

3

-

9, b

-

11, d

∞, a

17, b

∞, a

4

-

-

-

11, d

∞, a

13, c

∞, a

5

-

-

-

-

∞, a

13, c

13, e

Câu 2:

144

6

-

-

-

-

20, g

-

13, e

7

-

-

-

-

20, g

-

-

3, a

9, b

8, b

11, d

20, g

3, c

13, e

Câu 3:
Đáp án:

5
8

-2
6

-1
7

2
1

0
0

0
1

6

4

5

2

0

2

Ma trận D

Ma trận P

Câu 7:
Hƣớng dẫn: Chuyển bài toán về dạng đồ thị, mỗi tỉnh, thành phố là
một đỉnh, mỗi con đƣờng là một cạnh, giá trị chi phí đi lại là trọng số của
cạnh. Bài toán trở thành tìm đƣờng đi ngắn nhất từ một đỉnh đến các đỉnh
còn lại của đồ thị.
Chƣơng VIII
Câu 1:
Luồng cực đại: f = 27.
Tìm đƣợc lát cắt hẹp nhất (X, X*) với: X = {s, a, b, c, d}, X* = {t}

145

146

TÀI LIỆU THAM KHẢO
[1]. Nguyễn Đức Nghĩa &amp Nguyễn Tô Thành, Toán rời rạc. NXB Giáo
dục, 1999.
[2]. Kenneth H. Rosen, Toán học rời rạc ứng dụng trong tin học, NXB
Khoa học &amp Kỹ thuật, 1997.
[3]. Robert Sedgewick, Cẩm nang thuật toán, NXB Khoa học &amp Kỹ
thuật, 2004
[4]. Lê Tự Hỷ, Toán rời rạc, NXB Giáo dục, 2005.
[5]. Reinhard Diestel, Graph theory. Springer-Velag. 2005.

147

Giáo trình

LÝ THUYẾT ĐỒ THỊ
TS. Đặng Trường Sơn – ThS. Lê Văn Vinh
NHÀ XUẤT BẢN ĐẠI HỌC QUỐC GIA TP HỒ CHÍ MINH
Khu phố 6, Phường Linh Trung, Quận Thủ Đức, TPHCM
Số 3 Công trường Quốc tế, Quận 3, TP. HCM
ĐT: 38 239 172 - 38 239 170
Fax: 38 239 172
E-mail: [email protected]


Chịu trách nhiệm xuất bản
TS. HUỲNH BÁ LÂN
Tổ chức bản thảo và chịu trách nhiệm về tác quyền
TRƯỜNG ĐẠI HỌC SƯ PHẠM KỸ THUẬT TP. HCM
Biên tập
PHẠM ANH TÚ
Sửa bản in
PHẠM THỊ BÌNH
Thiết kế bìa
TRƯỜNG ĐẠI HỌC SƯ PHẠM KỸ THUẬT TP. HCM
GT.01.KTh (V)
ĐHQG.HCM-12

155-2012/CXB/560-08/ĐHQGTPHCM
KTh.GT.531-13 (T)

In 300 cuốn khổ 16 x 24cm, tại Công ty TNHH In và Bao bì Hưng
Phú. Số đăng ký kế hoạch xuất bản: 155-2012/CXB/56008/ĐHQGTPHCM. Quyết định xuất bản số: 174/QĐ-ĐHQGTPHCM cấp
ngày 22/11/2012 của Nhà xuất bản ĐHQGTPHCM. In xong và nộp lưu
chiểu Quí IV năm 2012.

ISBN: 978-604-73-1284-9

9 786047 312849