Một số bài toán đồ thị và ứng dụng.

ĐẠI HỌC ĐÀ NẴNG

TRƯỜNG ĐẠI HỌC SƯ PHẠM

KHOA TIN

----------

LÊ THỊ NGA

MỘT SỐ BÀI TOÁN ĐỒ THỊ VÀ ỨNG DỤNG

KHÓA LUẬN TỐT NGHIỆP

LỜI CẢM ƠN

Cầu thủ xuất sắc nhất của xứ sở hoa Tulip, Hà Lan – Johan Cruyiff đã từng nói:

“Sự may mắn không tự nó đến, cần phải tìm kiếm nó, và có lúc đổ cả mồ hôi và nước

mắt”. Đối với em, câu nói trên hoàn toàn chính xác vì những thành quả mà mỗi chúng

ta đạt được trước hết phải xuất phát từ nỗ lực của bản thân mình. Tuy nhiên, nếu

không nhờ sự giúp đỡ của những người xung quanh thì chúng ta sẽ không đạt được

mục tiêu như mong đợi.

Chính vì thế ngày hôm nay, khi hoàn tất xong bài luận văn này, em xin dành trang

đầu tiên của bài luận văn để bày tỏ lòng biết ơn đến tất cả các thầy cô giáo đã hết lòng

dạy dỗ, truyền đạt cho em những kiến thức và kinh nghiệm quý báu trong suốt 4 năm

học vừa qua, những người bạn đã luôn bên em giúp đỡ, động viên em cố gắng.

Với tấm lòng biết ơn sâu sắc, em xin chân thành cảm ơn thầy giáo PGS.TSKH Trần

Quốc Chiến, người thầy đã trực tiếp, tận tình giảng dạy và hướng dẫn em hoàn thành

bài luận văn này. Thầy đã giúp đỡ em rất nhiều trong việc hướng dẫn nội dung, cách

trình bày cũng như giới thiệu tài liệu tham khảo.

Và đặt biệt, con xin cảm ơn ba mẹ, gia đình đã nuôi dạy con nên người, và luôn là

chỗ dựa tinh thần vững chắc, giúp cho chúng con vượt qua mọi khó khăn, thử thách

trong cuộc sống.

Để đáp lại tấm chân tình của thầy cô, gia đình, bạn bè em xin hứa sẽ cố gắng vận

dụng những kiến thức mà mình đã học một cách hiệu quả nhất để đem lại lợi ích cho

mình và cho xã hội.

Đà Nẵng, tháng 5 năm 2012

Sinh viên: Lê Thị Nga

Ý KIẾN ĐÁNH GIÁ CỦA GIÁO VIÊN HƯỚNG DẪN

...........................................................................................................................................

...........................................................................................................................................

...........................................................................................................................................

...........................................................................................................................................

...........................................................................................................................................

...........................................................................................................................................

...........................................................................................................................................

...........................................................................................................................................

...........................................................................................................................................

...........................................................................................................................................

...........................................................................................................................................

...........................................................................................................................................

...........................................................................................................................................

Đà Nẵng, ngày tháng năm 2012

Giáo viên hướng dẫn

PGS.TSKH Trần Quốc Chiến

MỤC LỤC

MỞ ĐẦU.................................................................................................................. ….1

I. LÝ DO CHỌN ĐỀ TÀI................................................................................... .1

II. MỤC TIÊU, NHIỆM VỤ ............................................................................... 1

III. PHƯƠNG PHÁP NGHIÊN CỨU ................................................................ 1

Chương 1: MỘT SỐ VẤN ĐỀ CƠ BẢN CỦA ĐỒ THỊ ...................................... 2

I. CÁC ĐỊNH NGHĨA ĐỒ THỊ.......................................................................... 2

1. Định nghĩa đồ thị .......................................................................................... 2

2. Đồ thị vô hướng ............................................................................................ 2

3. Đồ thị có hướng............................................................................................. 2

II. MỘT SỐ MÔ HÌNH ĐỒ THỊ........................................................................ 3

1. Đồ thị “lấn tổ” trong sinh thái học.............................................................. 3

2. Đồ thị ảnh hưởng.......................................................................................... 3

3. Thi đấu vòng tròn ......................................................................................... 3

4. Đồ thị có ưu tiên trước sau .......................................................................... 4

III. CÁC KHÁI NIỆM CƠ BẢN ........................................................................ 4

1. Bậc đồ thị....................................................................................................... 4

a. Bậc đồ thị vô hướng................................................................................. 4

b. Bậc đồ thị có hướng.................................................................................. 5

2. Đường đi, chu trình, đồ thị liên thông ........................................................ 6

3. Một số dạng đồ thị đặt biệt.......................................................................... 7

a. Khái niệm .................................................................................................. 7

b. Một vài ứng dụng của đồ thị đặc biệt ..................................................... 9

IV. BIỂU DIỄN ĐỒ THỊ VÀ SỰ ĐẲNG CẤU ............................................... 11

1. Biểu diễn đồ thị ........................................................................................... 11

a. Ma trận kề ............................................................................................... 11

b. Ma trận liên thuộc .................................................................................. 12

2. Đồ thị đẳng cấu ......................................................................................... 114

Chương 2: CÁC BÀI TOÁN VỀ ĐƯỜNG ĐI..................................................... 15

I. ĐỒ THỊ EULER ............................................................................................. 15

1. Định nghĩa ................................................................................................... 15

2. Điều kiện cần và đủ .................................................................................... 16

3. Các thuật toán tìm chu trình Euler .......................................................... 16

II. ĐỒ THỊ HAMINTON .................................................................................. 18

1. Định nghĩa ................................................................................................... 18

2. Điều kiện cần và đủ .................................................................................... 19

a. Điều kiện cần ........................................................................................... 19

b. Điều kiện đủ ............................................................................................ 19

3. Một số bài toán ứng dụng .......................................................................... 19

a. Bài toán thi đấu bóng bàn...................................................................... 19

b. Bài toán mã đi tuần ................................................................................ 20

c. Bài toán sắp xếp chỗ ngồi....................................................................... 20

III. TÌM ĐƯỜNG ĐI TRONG MÊ CUNG ..................................................... 22

1. Phát biểu bài toán....................................................................................... 22

2. Thuật toán tìm đường đi trong mê cung .................................................. 22

3. Một số bài toán ứng dụng .......................................................................... 22

a. Bài toán sói, dê và cải ............................................................................. 22

b. Bài toán 3 ông chồng ghen ..................................................................... 23

c. Bài toán 3 thầy tu và 3 con quỷ.............................................................. 23

IV. TÌM ĐƯỜNG ĐI NGẮN NHẤT ................................................................ 23

1. Phát biểu bài toán....................................................................................... 23

2. Nội dung các thuật toán ............................................................................. 24

3. Các ứng dụng .............................................................................................. 39

a. Ứng dụng trong truyền tin..................................................................... 39

b. Ứng dụng trong việc lập lịch thi công của một công trình ................. 41

4. Bài toán người du lịch ................................................................................ 44

a. Giới thiệu bài toán .................................................................................. 44

b. Phương pháp nhánh cận........................................................................ 44

e. Mệnh đề.................................................................................................... 45

f. Phân nhánh .............................................................................................. 45

g. Tính cận ................................................................................................... 46

h. Thủ tục ngăn chặn hành trình con........................................................ 46

k. Tính chất tối ưu ...................................................................................... 46

Chương 3: CÂY...................................................................................................... 49

I. CÁC KHÁI NIỆM VÀ TÍNH CHẤT CƠ BẢN........................................... 48

1. Định nghĩa ................................................................................................... 49

2. Định lý tương đương .................................................................................. 50

3. Cây m-phân................................................................................................. 50

4. Các ứng dụng .............................................................................................. 50

a. Mã tiền tố................................................................................................. 50

b. Cây biểu thức .......................................................................................... 52

c. Cây quyết định ........................................................................................ 53

d. Cây nhị phân tìm kiếm........................................................................... 53

II. CÂY PHỦ....................................................................................................... 56

1. Định nghĩa và các tính chất ....................................................................... 56

2. Các thuật toán tìm cây phủ ....................................................................... 56

a. Tìm theo chiều ngang ............................................................................. 56

b. Tìm theo chiều sâu ................................................................................. 56

3. Cây bao trùm bé nhất ................................................................................ 57

a. Bài toán thực tế ....................................................................................... 57

b. Quy về đồ thị ........................................................................................... 57

4. Ứng dụng ..................................................................................................... 58

a. Bài toán kết nối hệ thống mạng............................................................. 58

b. Bài toán cây phủ lớn nhất...................................................................... 58

c. Bài toán tìm mạng điện với độ tin cậy lớn nhất................................... 58

d. Bài toán Steiner trên đồ thị.................................................................... 59

Chương 4: BÀI TOÁN LUỒNG CỰC ĐẠI TRONG MẠNG........................... 60

I. MẠNG, LUỒNG TRONG MẠNG, BÀI TOÁN LUỒNG CỰC ĐẠI........ 60

1. Định nghĩa ................................................................................................... 60

2. Bài toán luồng cực đại trong mạng........................................................... 60

II. THUẬT TOÁN TÌM LUỒNG CỰC ĐẠI FORD-FULKERSON ............ 61

III. LUỒNG CỰC ĐẠI VÀ LÁT CẮT CỰC TIỂU........................................ 62

IV. MỘT SỐ BÀI TOÁN ỨNG DỤNG............................................................ 62

1. Mạng với nhiều điểm phát và điểm thu ....................................................... 62

2. Bài toán với khả năng thông qua các cung và các đỉnh.............................. 62

3. Bài toán ghép cặp ........................................................................................... 63

Chương 5: SỐ ỔN ĐỊNH VÀ TÔ MÀU ĐỒ THỊ............................................... 64

I. SỐ ỔN ĐỊNH TRONG, SỐ ỔN ĐỊNH NGOÀI, NHÂN ĐỒ THỊ............. 64

1. Số ổn định trong ......................................................................................... 64

2. Số ổn định ngoài ......................................................................................... 64

3. Nhân đồ thị.................................................................................................. 64

4. Các thuật toán tìm các tập ổn định........................................................... 65

5. Ứng dụng trong lập cờ Ca rô..................................................................... 65

II. TÔ MÀU ĐỒ THỊ......................................................................................... 68

1. Tô màu bản đồ ........................................................................................... 68

2. Tô màu đồ thị.............................................................................................. 68

3. Các mệnh đề................................................................................................ 68

4. Thuật toán tham lam (greedy algorithm) ................................................ 70

5. Những ứng dụng của bài toán tô màu đồ thị ........................................... 70

a. Bài toán điều khiển đèn hiệu nút giao thông........................................ 70

b. Bài toán lập lịch ..................................................................................... 70

c. Phân chia tần số ..................................................................................... 72

d. Các thanh ghi chỉ số ............................................................................... 72

KẾT LUẬN ................................................................................................................ 73

TÀI LIỆU THAM KHẢO......................................................................................... 74

- 1 -

MỞ ĐẦU

Lý thuyết đồ thị là lĩnh vực nghiên cứu đã tồn tại từ những năm đầu của thế kỷ 18

nhưng lại có những ứng dụng hiện đại. Những ý tưởng cơ bản của Lý thuyết đồ thị

được nhà toán học người Thụy Sĩ Leonhard Euler đề xuất và chính ông là người đã

dùng đồ thị để giải quyết bài toán cầu Konigsberg nổi tiếng.

Đồ thị được sử dụng để giải quyết nhiều bài toán thuộc các lĩnh vực khác nhau.

Chẳng hạn, ta có thể dùng đồ thị để biểu diễn những mạch vòng của một mạch điện,

dùng đồ thị biểu diễn quá trình tương tác giữa các loài trong thế giới động thực vật,

dùng đồ thị biểu diễn những đồng phân của các hợp chất polyme hoặc biểu diễn mối

liên hệ giữa các loại thông tin khác nhau. Có thể nói, Lý thuyết đồ thị được ứng dụng

rộng rãi trong tất cả các lĩnh vực khác nhau của thực tế cũng như những lĩnh vực trừu

tượng của lý thuyết tính toán.

Đề tài “Một số bài toán đồ thị và ứng dụng”, là đề tài nghiên cứu lý thuyết giải

quyết nhiệm vụ làm sáng tỏ hơn cơ sở toán cho Tin học đồng thời nêu ra những khả

năng ứng dụng của đồ thị theo từng nội dung Lý thuyết của đồ thị.

I. LÝ DO CHỌN ĐỀ TÀI

Lý thuyết đồ thị đóng vai trò làm cơ sở toán cho Tin học vì đồ thị là một bộ phận

của Toán rời rạc, bản chất và cấu trúc của đồ thị mang tính rời rạc mà công cụ chính

trong Tin học là máy tính, các quá trình xử lý, lưu trữ thông tin trong máy tính cũng

mang tính rời rạc, nên điều này tương hợp gắn chặt lý thuyết đồ thị với công nghệ máy

tính trong việc nghiên cứu các đối tượng có tính chất rời rạc.

“Một số bài toán đồ thị và ứng dụng” là đề tài có tầm quan trọng và mang nghĩa

thiết thực cao. Lý thuyết đồ thị có nhiều ứng dụng trong các nghành kĩ thuật và đã

được nghiên cứu nhiều với khối lượng kiến thức khá đồ sộ. Đề tài được thực hiện

trước tiên sẽ đề cập tới những vấn đề chủ yếu của lý thuyết đồ thị, sau đó tùy từng nội

dung sẽ xoay quanh những ứng dụng của đồ thị, giải quyết các bài toán trong Tin học

như xác định xem hai máy tính trong mạng có thể truyền tin được hay không nhờ mô

hình đồ thị của mạng máy tính, hay là bài toán nối mạng máy tính sao cho tổng chi phí

là nhỏ nhất hoặc việc khắc phục những gói tin bị truyền sai nhờ các giải thuật đã

nghiên cứu về đồ thị. Có những ứng dụng của đồ thị không đi trực tiếp vào các lĩnh

vực trong Tin học, ví dụ như bài toán lập lịch trong công tác hành chính, xác định

đường đi ngắn nhất giữa hai điểm nút giao thông, ta cũng xem đó là ứng dụng một

cách gián tiếp trong Tin học vì nếu được mô hình tốt những bài toán đó bằng đồ thị thì

sẽ giải quyết chúng dễ dàng bằng máy tính, hoặc là về chơi chơi cờ Ca rô tuy chỉ là

môn chơi về trí tuệ nhưng đồ thị cũng hỗ trợ tốt cho những ai muốn lập trình chơi cờ

Ca rô trên máy tính khi đã mô hình được các thế cờ bằng đồ thị.

II. MỤC TIÊU, NHIỆM VỤ

Đề tài được thực hiện nhằm làm sáng tỏ hơn cơ sở toán cho Tin học đồng thời nêu

ra những khả năng ứng dụng của đồ thị theo từng nội dung của Lý thuyết đồ thị.

III. PHƯƠNG PHÁP NGHIÊN CỨU

+ Tìm hiểu thông tin trên mạng internet, sách, báo.

+ Thông qua sự hướng dẫn của thầy cô và các kiến thức đã học.

- 2 -

Chương 1: MỘT SỐ VẤN ĐỀ CƠ BẢN CỦA ĐỒ THỊ

I. CÁC ĐỊNH NGHĨA ĐỒ THỊ

1. Định nghĩa đồ thị

Đồ thị là một cấu trúc rời rạc bao gồm các đỉnh và các cạnh nối các đỉnh đó. Người

ta phân loại đồ thị tùy theo đặc tính và số các cạnh nối các cặp đỉnh của đồ thị.

Đồ thị được mô tả hình thức: G = (V, E). Trong đó V là tập các đỉnh, E là tập các

cạnh. Có thể xem E là tập các cặp {v, w}, với v, w là hai đỉnh thuộc V.

Ví dụ. Giả sử ta có một mạng gồm các máy tính và các kênh điện thoại nối các máy

tính này. Chúng ta có thể biểu diễn các vị trí đặt máy tính bởi các điểm và các kênh

điện thoại nối chúng bởi các đoạn nối như hình 1.1 dưới đây.

Hình 1.1: Mạng máy tính

2. Đồ thị vô hướng

Đồ 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. 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:

Hình 1.1 là một ví dụ về đồ thị vô hướng.

3. Đồ thị có hướng

Đồ thị có hướng G = (V, E) gồm một tập các đỉnh V và tập E các cạnh có hướng

gọi là cung. Mỗi cung e  E được liên kết với một cặp đỉnh {v, w} (có thứ tự) như

hình sau:

Hình 1.2 là một ví dụ về đồ thị có hướng.

Hình 1.2: Mạng truyền thông có các đường điện thoại một chiều

v

e w

v

e w

Hà Tây

Nam Định

Hà Nội

Thanh Hóa

Huế

Đồng Nai

An Giang

Hồ Chí Minh

Long An

Khánh Hòa

Hà Tây

Nam Định

Hà Nội

Thanh Hóa

Huế

Đồng Nai An Giang

Hồ Chí Minh

Khánh Hòa

Long An