Giáo trình toán rời rạc và lý thuyết đồ thị (HCMUTE)

NGUYỄN THÀNH SƠN - ĐẶNG TRƯỜNG SƠN - LÊ VĂN VINH
TRẦN CÔNG TÚ - NGUYỄN QUANG NGỌC - NGUYỄN PHƯƠNG

GIÁO TRÌNH

TOÁN RỜI RẠC
VÀ LÝ THUYẾT ĐỒ THỊ

Nguyễn Thành Sơn, Đặng Trường Sơn, Lê Văn Vinh, Trần Công Tú,
Nguyễn Quang Ngọc, Nguyễn Phương

Giáo trình

TOÁN RỜI RẠC
VÀ LÝ THUYẾT ĐỒ THỊ

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

LỜI NÓI ĐẦU
Toán rời rạc và Lý thuyết đồ thị là môn học tích hợp từ hai môn
Toán rời rạc và môn Lý thuyết đồ thị. Đây 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. Nội
dung “Toán rời rạc” trang bị cho người học những kiến thức cơ bản về
logic mệnh đề, logic vị từ, suy diễn logic, quan hệ tương đương, quan hệ
thứ tự, dàn, đại số Bool và cung cấp cho người học kiến thức và kỹ năng
trong việc phân tích, nhìn nhận vấn đề, cũng như trong việc xác định
công thức đa thức tối tiểu bằng phương pháp biểu đồ Karnaugh. Còn 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 kiến thức về 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.
Toán rời rạc và 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 Toán rời rạc và Lý thuyết đồ thị, sinh viên
sẽ có khả năng phân tích, giải thích, tư duy và lập luận giải quyết các vấn
đề về toán rời rạc và lý thuyết đồ thị. Sinh viên sẽ được cung cấp kiến
thức để hiểu và vận dụng được những quy 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à khả năng phân tích, nhìn nhận vấn đề một
cách khoa học, không phiến diện hay tư duy theo lối mòn. Ngoài ra, sinh
viên sẽ biết cách 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ó 11 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 vấn đề cơ bản của toán rời rạc và 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 Toán rời rạc và Lý
thuyết đồ thị tại trường đại học,
...

...
n Tô Thành (1999), Toán rời rạc, NXB
Giáo Dục.
[2]. Kenneth H. Rosen (1997), Toán học rời rạc ứng dụng trong tin
học, NXB Khoa học và Kỹ thuật.
[3]. Robert Sedgewick (2004), Cẩm nang thuật toán, NXB Khoa học và
Kỹ thuật.
[4]. Lê Tự Hỷ (2005), Toán rời rạc, NXB Giáo Dục.
[5]. Reinhard Diestel (2005), Graph theory, Springer-Velag.
[6]. Nguyễn Hữu Anh (2003), Toán rời rạc, ĐH KHTN TP HCM.

231

GIÁO TRÌNH NHÀ XUẤT BẢN
TOÁN RỜI RẠC VÀ ĐẠI HỌC QUỐC GIA THÀNH PHỐ HỒ CHÍ MINH
LÝ THUYẾT ĐỒ THỊ Khu phố 6, Phường Linh Trung, Quận Thủ Đức, TP Hồ Chí Minh
TS. NGUYỄN THÀNH SƠN
TS. ĐẶNG TRƯỜNG SƠN
ThS. LÊ VĂN VINH
ThS. TRẦN CÔNG TÚ
ThS. NGUYỄN QUANG NGỌC
TS. NGUYỄN PHƯƠNG

Dãy C, số 10-12 Đinh Tiên Hoàng, Phường Bến Nghé, Quận
1, TP. Hồ Chí Minh
ĐT: 862726361 - 862726390
E-mail: [email protected]
PHÒNG PHÁT HÀNH
Dãy C, số 10-12 Đinh Tiên Hoàng, Phường Bến Nghé, Quận
1, TP. Hồ Chí Minh
ĐT: 862726361 - 862726390
Website: www.nxbdhqghcm.edu.vn
TRUNG TÂM SÁCH ĐẠI HỌC
Dãy C, số 10-12 Đinh Tiên Hoàng, Phường Bến Nghé, Quận
1, TP. Hồ Chí Minh
ĐT: 8362726350 - 0942810361
Website: www.nxbdhqghcm.edu.vn

Xuất bản năm 2016

Số lượng 300 cuốn,
Khổ: 16x24 cm,
ĐKKHXB số: 2310-2016/CXBIPH/
02-147/ĐHQGTPHCM,
Quyết định XB số: 175/QĐ
của NXB ĐHQG-HCM
cấp ngày 19-07-2016.
In tại: Cty TNHH
In và Bao bì Hưng Phú
Địa chỉ: 162A/1 KP1A, P. An Phú,
TX. Thuận An, Tỉnh Bình Dương
Nộp lưu chiểu: Quý III năm 2016

Chịu trách nhiệm nội dung:
NGUYỄN HOÀNG DŨNG
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. HỒ CHÍ
MINH
Biên tập:
LÊ THỊ MINH HUỆ
Sửa bản in:
THANH HÀ
Trình bày bìa:
TRƯỜNG ĐẠI HỌC SƯ PHẠM KỸ THUẬT TP. HỒ CHÍ
MINH
GIÁO TRÌNH
TOÁN RỜI RẠC VÀ LÝ THUYẾT ĐỒ THỊ

NXB ĐHQG-HCM

Nhà xuất bản ĐHQG-HCM và tác
giả/đối tác liên kết giữ bản quyền©
Copyright © by VNU-HCM
Publishing House and author/copartnership
All rights reserved

Chịu trách nhiệm xuất bản:
NGUYỄN HOÀNG DŨNG

ISBN: 978-604-73-4457-4

Giáo trình
TOÁN RỜI RẠC VÀ LÝ THUYẾT ĐỒ THỊ

TS. NGUYỄN THÀNH SƠN
TS. ĐẶNG TRƯỜNG SƠN
ThS. LÊ VĂN VINH
ThS. TRẦN CÔNG TÚ
ThS. NGUYỄN QUANG NGỌC
TS. NGUYỄN PHƯƠNG

Bản tiếng Việt ©, TRƯỜNG ĐẠI HỌC SƯ PHẠM KỸ THUẬT TP. HỒ CHÍ MINH, NXB ĐHQGHCM và TÁC GIẢ
Bản quyền tác phẩm đã được bảo hộ bởi Luật xuất bản và Luật Sở hữu trí tuệ Việt Nam. Nghiêm
cấm mọi hình thức xuất bản, sao chụp, phát tán nội dung khi chưa có sự đồng ý của tác giả và Nhà
xuất bản.
ĐỂ CÓ SÁCH HAY, CẦN CHUNG TAY BẢO VỆ TÁC QUYỀN!

ISBN: 978-604-73-4457-4

9 786047 344574