Một số vấn đề ứng dụng của đồ thị trong Tin học
Lời nói đầu
Bước sang năm bản lề của thế kỷ 21, nhìn lại thế kỷ 20 là thế kỷ mà con người đạt được nhiều thành tựu khoa học rực rỡ nhất, một trong những thành tựu đó là sự bùng nổ của ngành khoa học máy tính. Sự phát triển kỳ diệu của máy tính trong thế kỷ này gắn liền với sự phát triển toán học hiện đại, đó là toán rời rạc.
Toán học rời rạc nghiên cứu các cấu trúc có tính chất rời rạc không liên tục. Toán rời rạc bao gồm các lĩnh vực như quan hệ, lý thuyết đồ thị, lôgíc toán, ngôn ngữ hình thức . trong đó lý thuyết đồ thị là một bộ phận trọng tâm với nhiều khối lượng kiến thức khá lý thú và được nghiên cứu nhiều nhất.
Toán rời rạc nói chung và lý thuyết đồ thị nói riêng là công cụ thiết yếu cho nhiều ngành khoa học kỹ thuật, và là một thành phần quan trọng trong học vấn đối với sinh viên các ngành kỹ thuật đặc biệt sinh viên ngành Tin học. Lý thuyết đồ thị, với cách tiếp cận đối tượng nghiên cứu và phương pháp tư duy khá độc đáo thực sự ngày càng hữu ích có nhiều ứng dụng phong phú và gây không ít bất ngờ. Máy tính mà bản thân nó với các quá trình làm việc 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.
Lý thuyết đồ thị có nhiều ứng dụng thực tiễn đặc biệt là trong lĩnh vực Tin học, muốn hiểu biết sâu sắc các vấn đề Tin học cần nắm vững các kiến thức về Toán học rời rạc mà trong đó đặc biệt là lý thuyết đồ thị. Từ những nhận thức trên, với đề tài "Một số vấn đề ứng dụng của đồ thị trong Tin học" đây không chỉ là nhiệm vụ em phải thực hiện trong kỳ bảo vệ luận văn tốt nghiệp mà thực sự đây là đề tài mà em rất quan tâm và say mê nghiên cứu.
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. Ts Đỗ Đức Giáo là người trực tiếp, tận tình, chu đáo giảng dạy và hướng dẫn em hoàn thành cuốn luận văn này. Nhân dịp này em cũng xin cảm ơn sự giúp đỡ, dạy bảo tận tình của các thầy cô giáo, cán bộ Khoa Công Nghệ Thông Tin trường Đại học Dân lập Đông Đô và những bạn học đã đóng góp những ý kiến bổ ích cho bản luận văn này.
Do trình độ hiểu biết còn hạn chế, thời gian chuẩn bị không nhiều, bản luận văn này còn nhiều sai sót và chưa đầy đủ, em rất mong nhận được sự góp ý của các thầy cô và các bạn quan tâm.
Giới thiệu đề tài
"Một số vấn đề ứng dụng của đồ thị trong Tin học" là đề tài mang tính nghiên cứu lý thuyết, có tầm quan trọng và có ý nghĩa thiết thực cao. Khái niệm đồ thị ở đây khác với những đồ thị thông thường đã biết, đây là 1 lĩnh vực về lý thuyết đồ thị nghiên cứu những cấu trúc mang tính rời rạc là 1 bộ phận quan trọng của Toán học rời rạc.
Lý thuyết đồ thị có nhiều ứng dụng trong các ngà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 đó tuỳ từng nội dung cũng sẽ xoay quanh tới những ứng dụng của đồ thị trong Tin học, 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 2 điểm nút giao thông, ta cũng xem đó là ứng dụng 1 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 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ị.
Đề tài được thực hiện xong bao gồm những nội dung sau đây:
Chương 1 Một số vấn đề cơ bản của đồ thị
Nhằm trình bày những khái niệm cơ bản nhất về lý thuyết đồ thị, là cơ sở tìm hiểu sâu sắc hơn các vấn đề tiếp theo. Ngoài các định nghĩa, tính chất cơ bản của đồ thị, chương này có trình bày đến 1 vấn đề quan trọng, đó là cách lưu trữ, biểu diễn và xử lý đồ thị trên máy tính khi đã xét những mô hình biểu diễn hình học. Cấu trúc dữ liệu liên quan chặt chẽ đến giải thuật, việc biểu diễn đồ thị trên máy tính như thế nào sẽ ảnh hưởng đến cách giải các bài toán ứng dụng bằng máy tính. Trong chương có trình bày một số phương pháp biểu diễn đồ thị trên máy tính, mỗi phương pháp đều có những ưu và khuyết điểm riêng, vì vậy cần lựa chọn phương pháp sao cho phù hợp với đặc điểm từng bài toán và đạt được hiệu quả về thuật toán.
Khi đưa các ví dụ minh họa, nhất là về phần đồ thị đặc biệt ta sẽ thấy được ứng dụng của đồ thị trong mô hình về mạng máy tính.
Chương 2 Số ổn định và tô màu đồ thị
Số ổn định của đồ thị bao gồm số ổn định trong, số ổn định ngoài và nhân đồ thị, nghiên cứu vấn đề này ta sẽ thấy được mối quan hệ giữa các tập đỉnh của một đồ thị. Một ứng dụng khá lý thú khi đề cập tới vấn đề này đó là xây dựng mô hình đồ thị cho bài toán lập trình chơi cờ carô, có sử dụng đến tập ổn định ngoài của đồ thị.
ở chương này ta cũng sẽ gặp đến một ứng dụng khá thiết thực khi bàn đến vấn đề tô màu của đồ thị, hay còn gọi là sắc số của đồ thị, ứng dụng đó là bài toán lập lịch. Lập lịch là công tác hành chính phổ biến, hay gặp ở các cơ quan, xí nghiệp, trường học . cũng đã có nhiều sản phẩm phần mềm phục vụ cho việc lập lịch.
Chương 3 Chu trình, đường đi Euler và Hamilton trong đồ thị
Trình bày những khái niệm về chu trình Euler, đường Euler, chu trình Hamilton, đường Hamilton các tính chất của chúng đồng thời đưa ra 1 số thuật toán ứng dụng để tìm các đường, chu trình Euler, Hamilton.
Chương 4 Đường đi ngắn nhất trong đồ thị
Bài toán đường đi ngắn nhất hay được đề cập tới trong lý thuyết đồ thị, đây cũng là loại bài toán tối ưu có nhiều ứng dụng rộng rãi. Trong đồ thị thường đặt ra các loại tìm đường đi ngắn nhất như sau:
- Đường đi ngắn nhất nhất giữa 1 cặp đỉnh đã được xác định trước.
- Đường đi ngắn nhất giữa 1 đỉnh với tất cả các đỉnh còn lại.
- Đường đi ngắn nhất giữa tất cả các cặp đỉnh bất kỳ.
Để giải quyết các loại bài toán này, trong chương sẽ trình bày 1 số thuật toán chính hay được sử dụng như: Dijkstra, Ford-Bellman và Floyd.
Về mặt ứng dụng, trong chương sẽ nêu ra giải thuật Viterbi cho ứng dụng khá quan trọng trong lĩnh vực Tin học đó sửa gói tin sai khi truyền tin trong mạng máy tính.
Khi nói đến đường đi ngắn nhất, người ta cũng hay nói đến mở rộng của bài toán đường đi ngắn nhất thành đường đi dài nhất. Trong vấn đề này ta lại có 1 ứng dụng nữa trong công tác lập lịch, đó là sơ đồ mạng PERT cho việc lập dự án thi công một công trình. ứng dụng này rất thực tiễn và đã đem lại nhiều hiệu quả cao cho việc thi công một công trình.
Chương 5 Một số vấn đề về cây
Đây là chương cuối cùng và là chương sẽ đề cập tới nhiều ứng dụng nhất. Cây là một trường hợp riêng của đồ thị, để nghiên cứu hết các tính chất, khái niệm về cây cần cả 1 khối lượng kiến thức đồ sộ và đã có những đề tài cấp luận văn hoặc hơn thế nữa nghiên cứu về cây. Trong chương này chỉ đề cập tới những điểm chính nhất, cơ bản nhất về cây và tập trung khai thác những ứng dụng của nó.
Những ứng dụng của cây thì rất nhiều, trong chương chỉ đề cập tới những ứng dụng cơ sở nhất nhưng cũng thiết thực nhất, đó là 1 số ứng dụng của cây nhị phân như mã tiền tố, cây biểu diễn biểu thức, cây quyết định, cây sắp xếp và tìm kiếm.
Trong lý thuyết đồ thị, khi nói về cây thì cây bao trùm là vấn đề không thể thiếu, vì đây cũng là đặc điểm rất hay của đồ thị. Trong cây bao trùm lại có cây bao trùm bé nhất, lớn nhất và đây lại là 1 dạng của bài toán tối ưu. Trong chương cũng sẽ giới thiệu ứng dụng thực tiễn của cây bao trùm nhỏ nhất trong việc kết nối mạng sao cho chi phí nhỏ nhất, đồng thời đưa ra 1 số thuật toán tìm cây bao trùm, đặc biệt có những thuật toán rất cơ sở được nêu ra, được dùng nhiều trong việc giải quyết các bài toán đồ thị trên máy tính như là kỹ thuật quay lui, tìm kiếm ưu tiên theo chiều rộng và chiều sâu.
Mục lục
Nội dung Trang
Lời nói đầu 1
Giới thiệu đề tài 2
Mục lục . 5
Chương 1 Một số vấn đề cơ bản của đồ thị
9
I. Các định nghĩa đồ thị . 9
1. Định nghĩa đồ thị . 9
2. Đồ thị đơn 10
3. Đa đồ thị 10
4. Giả đồ thị 10
II. Các loại đồ thị 11
1. Đồ thị vô hướng . 11
2. Đồ thị có hướng . 11
3. Đồ thị hỗn hợp 11
III. Một số khái niệm và tính chất cơ bản của đồ thị 11
1. Bậc đồ thị . 11
1.1 Bậc đồ thị vô hướng 11
1.2 Bậc đồ thị có hướng 12
2. Đường đi và chu trình . 13
2.1 Đường đi . 13
2.2 Chu trình 13
3. Đồ thị liên thông 14
4. Đồ thị con và đồ thị bộ phận 15
IV. Các dạng biểu diễn của đồ thị 15
1. Biểu diễn hình học của đồ thị 15
2. Sự đẳng cấu . 16
3. Một số đồ thị đặc biệt . 17
3.1 Đồ thị đều . 17
3.2 Đồ thị đầy đủ 17
3.3 Đồ thị bánh xe 17
3.4 Một vài ứng dụng của đồ thị đặc biệt . 18
4. Biểu diễn đồ thị trên máy tính 19
4.1 Biểu diễn bằng ma trận kề 19
4.2 Danh sách cạnh (cung) 22
4.3 Danh sách kề 22
Chương 2 Số ổn định và tô màu đồ thị 24
I. Số ổn định trong, số ổn định ngoài, nhân đồ thị . 24
1. Số ổn định trong 24
2. Số ổn định ngoài 24
3. Nhân đồ thị 24
4. Các thuật toán tìm các tập ổn định trong cực đại, ổn định ngoài cực tiểu. 25
4.1 Thuật toán tìm số ổn định trong 25
4.2 Thuật toán tìm số ổn định ngoài 25
5. ứng dụng đồ thị trong lập trình chơi cờ Ca rô 26
II. tô màu đồ thị 29
1. Sắc số đồ thị . 29
2. Tô màu đồ thị phẳng . 31
2.1 Đồ thị phẳng . 31
2.2 Định lý 5 màu (Kempe - Heawood) . 31
2.3 Bài toán 4 màu (Appel - Haken) . 32
3. Ví dụ ứng dụng . 32
Chương 3 Chu trình, đường đi Euler và hamilton trong đồ thị 35
I. Chu trình và đường đi Euler . 35
1. Chu trình Euler 35
1.1 Định nghĩa 35
1.2 Thuật toán tìm chu trình Euler . 37
2. Đường đi Euler 38
2.1 Định nghĩa 38
2.2 Thuật toán tìm đường Euler . 38
II. Chu trình và đường đi Hamilton . 39
1. Chu trình Hamilton 39
2. Đường Hamilton 40
3. Thuật toán liệt kê tất cả các chu trình Hamilton . 41
Chương 4 Đường đi ngắn nhất trong đồ thị 42
I. Đường đi ngắn nhất trong đồ thị không có trọng số . 42
1. Định nghĩa . 42
2. Thuật toán . 42
Ii. Đường đi ngắn nhất trong đồ thị có trọng số 43
1. Các khái niệm . 43
2. Thuật toán tìm đường đi ngắn nhất cho đồ thị có trọng số 44
2.1 Cơ sở thuật toán tìm đường đi ngắn nhất . 44
2.2 Thuật toán Dijkstra . 45
2.3 Thuật toán Ford - Bellman . 45
2.4 Thuật toán Floyd . 47
III. các ứng dụng 47
1. ứng dụng trong truyền tin 47
2. ứng dụng trong việc lập lịch thi công của một công trình 50
IV. Chương trình mô tả thuật toán Dijkstra tìm đường đi ngắn nhất 53
Chương 5 Một số vấn đề về cây 56
I. Các khái niệm và tính chất cơ bản 56
1. Định nghĩa 56
2. Một số khái niệm cơ bản . 57
3. Cây m phân 58
4. Các ứng dụng . 58
4.1 Mã tiền tố . 58
4.2 Cây biểu diễn biểu thức 61
4.3 Cây quyết định 62
4.4 Cây sắp xếp và tìm kiếm 63
4.4.1 Sắp xếp chèn với tìm kiếm nhị phân . 63
4.4.2 Thuật toán sắp xếp hoà nhập . 65
4.4.3 Thuật toán sắp xếp nhanh 68
II. Cây bao trùm . 70
1. Định nghĩa và các tính chất . 70
2. Các thuật toán tìm cây bao trùm . 71
2.1 Thuật toán theo lý thuyết . 71
2.2 Thuật toán tìm kiếm ưu tiên chiều sâu và chiều rộng . 71
2.2.1 Kỹ thuật quay lui . 72
2.2.2 Thuật toán tìm kiếm theo chiều sâu . 72
2.2.3 Thuật toán tìm kiếm theo chiều rộng . 73
2.3 Chương trình thể hiện cho các thuật toán 73
2.3.1 Chương trình Pascal về thuật toán quay lui 73
2.3.2 Chương trình cho thuật toán tìm kiếm chiều sâu và chiều rộng 74
3. Cây bao trùm bé nhất . 76
3.1 Định nghĩa . 76
3.2 Thuật toán tìm cây bao trùm bé nhất 76
3.2.1 Thuật toán Kruskal 76
3.2.2 Thuật toán Prim . 77
3.2.3 Chương trình thể hiện thuật toán . 78
3.3 ứng dụng cho bài toán kết nối hệ thống mạng . 81
4. Cây bao trùm lớn nhất 81
4.1 Định nghĩa . 81
4.2 Thuật toán tìm cây bao trùm lớn nhất 81
Kết luận 83
Tài liệu tham khảo 84
7 trang |
Chia sẻ: lvcdongnoi | Lượt xem: 5116 | Lượt tải: 1
Bạn đang xem nội dung tài liệu Một số vấn đề ứng dụng của đồ thị trong Tin học, để tải tài liệu về máy bạn click vào nút DOWNLOAD ở trên
Giíi thiÖu :
Lý thuyÕt ®å thÞ ®îc nghiªn cøu vµ ph¸t triÓn do nÈy sinh tõ nhu cÇu gi¶i quyÕt c¸c vÊn ®Ò thùc tiÔn, cã nhiÒu øng dông trong c¸c ngµnh khoa häc kü thuËt kh¸c nhau. §Ò tµi thùc hiÖn lµ "Mét sè vÊn ®Ò øng dông cña ®å thÞ trong Tin häc", ®©y lµ ®Ò tµi nghiªn cøu lý thuyÕt gi¶i quyÕt nhiÖm vô lµ 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Þ trong Tin häc theo tõng néi dung cña Lý thuyÕt ®å thÞ.
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ý lu 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 gi÷a ®å thÞ vµ m¸y tÝnh.
Lý thuyÕt ®å thÞ cã c¶ mét khèi lîng kiÕn thøc lý thuyÕt ®å sé, øng dông cña ®å thÞ còng rÊt réng, ®Ò tµi ®îc thùc hiÖn chØ bao gåm nh÷ng néi dung c¬ së vµ träng t©m cña ®å thÞ, vµo mçi néi dung lý thuyÕt sÏ ®a ra nh÷ng vÝ dô øng dông minh ho¹ nh»m lµm râ sù øng dông cña phÇn lý thuyÕt ®ã. Trong c¸c øng dông rÊt réng lín cña ®å thÞ c¸c vÝ dô ®îc ®a ra còng cha ®Çy ®ñ nhng thùc sù ®ã còng lµ ®¹i diÖn vµ phÇn nµo lµm s¸ng tá c¸c vÊn ®Ò øng dông cña ®å thÞ.
LuËn v¨n ®îc thùc hiÖn ®i theo tõng phÇn néi dung cña lý thuyÕt ®å thÞ gåm 5 ch¬ng nh sau :
Ch¬ng I Mét sè vÊn ®Ò c¬ b¶n cña ®å thÞ
Nghiªn cøu c¸c vÊn ®Ò øng dông cña ®å thÞ, tríc hÕt ph¶i t×m hiÓu c¸c vÊn ®Ò c¬ b¶n cña lý thuyÕt ®å thÞ, ®©y lµ c¬ së ®Ó t×m hiÓu s©u s¾c h¬n c¸c vÊn ®Ò tiÕp theo. Trong ch¬ng sÏ tr×nh bµy c¸c ®Þnh nghÜa vµ tÝnh chÊt c¬ b¶n cña ®å thÞ, nhng tãm l¹i ta quan t©m ®Õn c¸c vÊn ®Ò chÝnh sau:
- TÝnh rêi r¹c : §å thÞ lµ cÊu tróc rêi r¹c gåm c¸c ®Ønh vµ c¹nh, thÓ hiÖn ®óng nh c¸c yÕu tè rêi r¹c trong m¸y tÝnh. C¸c yÕu tè rêi r¹c nhau nhng kh«ng hoµn toµn ®éc lËp nhau mµ gi÷a chóng cã sù liªn hÖ, cã mèi quan hÖ víi nhau. Nghiªn cøu mèi quan hÖ gi÷a c¸c yÕu tè rêi r¹c lµ quan träng, ®iÒu nµy quy ®Þnh b¶n chÊt vµ cÊu tróc cña ®å thÞ.
- C¸ch biÓu diÔn vµ lu tr÷ cña ®å thÞ trªn m¸y tÝnh : CÊu tróc d÷ liÖu liªn quan chÆt chÏ ®Õn gi¶i thuËt, c¸ch thøc biÓu diÔn ®å thÞ trªn m¸y tÝnh ¶nh hëng nhiÒu ®Õn viÖc gi¶i c¸c bµi to¸n øng dông trªn m¸y tÝnh. §Ò cËp tíi vÊn ®Ò nµy cã 3 ph¬ng ph¸p chÝnh:
a) BiÓu diÔn b»ng ma trËn kÒ
Ph¬ng ph¸p nµy dùa trªn mèi hÖ gi÷a tÊt c¶ c¸c cÆp ®Ønh, ®å thÞ n ®Ønh t¬ng øng víi ma trËn vu«ng cÊp n, lµ ph¬ng ph¸p ®îc dïng phæ biÕn, thÓ hiÖn cho hÇu hÕt c¸c lo¹i ®å thÞ. u ®iÓm lµ dÔ dµng x¸c ®Þnh ®îc c¸c cÆp ®Ønh cã kÒ nhau hay kh«ng hoÆc lµ rÊt thuËn tiÖn khi cÇn tÝnh sè bËc cña mçi ®Ønh, ngoµi ra ta cã thÓ biÕt ®îc sè ®êng ®i víi ®é dµi x¸c ®Þnh gi÷a 1 cÆp ®Ønh nµo ®ã b»ng c¸ch tÝnh tÝch cña ma trËn kÒ. Nhîc ®iÓm cña ph¬ng ph¸p nµy lµ kh«ng phô thuéc vµo sè c¹nh cña ®å thÞ, ta lu«n ph¶i sö dông n2 ®¬n vÞ bé nhí ®Ó lu tr÷ nã.
b) BiÓu diÔn b»ng danh s¸ch c¹nh (cung)
§©y lµ c¸ch biÓu diÔn theo c¹nh, phô thuéc vµo sè c¹nh cña ®å thÞ. Danh s¸ch c¹nh (cung) lµ bao gåm tÊt c¶ c¸c c¹nh (cung) cña ®å thÞ, mçi mét c¹nh (cung) gåm c¸c thµnh phÇn: ®Ønh ®Çu, ®Ønh cuèi, träng sè (nÕu cã). Nh vËy ®¬n vÞ bé nhí ®Ó lu tr÷ ®å thÞ m c¹nh lµ 2m (hoÆc 3m nÕu cã träng sè). Nhîc ®iÓm cña ph¬ng ph¸p nµy lµ khã x¸c ®Þnh c¸c ®Ønh kÒ víi mét ®Ønh cho tríc hoÆc lµ tÝnh sè bËc cña mét ®Ønh.
c) BiÓu diÔn b»ng danh s¸ch kÒ
Víi ph¬ng ph¸p nµy th× øng víi mçi ®Ønh lµ 1 danh s¸ch liªn kÕt c¸c ®Ønh kÒ víi nã, víi ®å thÞ cã híng n ®Ønh m c¹nh th× ®¬n vÞ bé nhí ®Ó lu tr÷ lµ n + m. C¸ch biÓu diÔn nµy thÝch hîp cho c¸c thuËt to¸n lµm viÖc víi cÊu tróc ®å thÞ hay thay ®æi nh thªm bít c¹nh.
VÒ mÆt øng dông, khi ®Ò cËp tíi c¸c lo¹i ®å thÞ ®å thÞ ®Æc biÖt, trong ch¬ng sÏ nªu nh÷ng m« h×nh cÊu tróc m¹ng (topolopy) d¹ng ®iÓm - ®iÓm cã ¸p dông ®Õn c¸c d¹ng cña ®å thÞ ®Æc biÖt, nh cÊu tróc m¹ng h×nh sao, h×nh vßng, b¸nh xe... HoÆc ta xÐt øng dông trong mét hÖ thèng th«ng tin nh m¹ng m¸y tÝnh, cã nh÷ng ®êng truyÒn gi÷a 2 ®iÓm lµ rÊt quan träng, ®Ó tr¸nh nh÷ng sù cè cÇn cã c¸c ®êng truyÒn tin dù phßng kh¸c, ®Ó xem xÐt c¸c ®êng truyÒn dù phßng ta cÇn xem xÐt ®Õn ®êng ®i, sè ®êng ®i gi÷a 2 ®iÓm truyÒn tin ®ã. Nh vËy ta thÊy øng dông nµy liªn quan tíi ®êng ®i, sè ®êng ®i gi÷a 2 ®Ønh trong m« h×nh ®å thÞ t¬ng øng.
Ch¬ng II. Sè æn ®Þnh vµ t« mµu ®å thÞ
Ch¬ng gåm 2 néi dung chÝnh: Sè æn ®Þnh vµ s¾c sè ®å thÞ. Sè æn ®Þnh lµ sè æn ®Þnh trong, sè æn ®Þnh ngoµi vµ nh©n ®å thÞ. Nh ®· nªu trªn, mèi quan hÖ gi÷a c¸c yÕu tè rêi r¹c lµ quan träng, ®Ò cËp tíi c¸c vÊn ®Ò nµy ta l¹i thÊy ®îc râ mèi quan hÖ gi÷a c¸c tËp ®Ønh. TËp æn ®Þnh trong l¹i tËp c¸c ®Ønh cña ®å thÞ sao cho nh÷ng ®Ønh trong tËp nµy cã mèi quan hÖ lµ kh«ng kÒ nhau. TËp æn ®Þnh ngoµi hay cßn gäi lµ tËp thèng trÞ, nh÷ng ®Ønh trong tËp nµy cã mèi quan hÖ "thèng trÞ" c¸c ®Ønh kh¸c ngoµi tËp, quan hÖ "thèng trÞ" nµy ®îc hiÓu lµ lu«n tån t¹i 1 ®Ønh thuéc tËp thèng trÞ sao cho nã kÒ víi 1 ®Ønh bÊt kú ngoµi tËp. Nh©n ®å thÞ chÝnh lµ tËp võa lµ tËp æn ®Þnh trong võa lµ tËp æn ®Þnh ngoµi, ®èi víi tËp æn ®Þnh trong ta quan t©m tíi tËp cã lùc lîng cùc ®¹i, víi tËp æn ®Þnh ngoµi ta quan t©m tíi tËp cã lùc lîng cùc tiÓu.
VÒ mÆt øng dông cña sè æn ®Þnh : sè æn ®Þnh ngoµi thêng ®îc ¸p dông cho bµi to¸n ®Æt väng g¸c, tõ ý tëng nµy ta xÐt 1 øng dông phôc vô cho viÖc lËp tr×nh ch¬i cê ca r«. Trong kü thuËt ch¬i cê Ca r« qu©n cã kh¶ n¨ng th¾ng nhiÒu h¬n lµ qu©n cã kh¶ n¨ng thèng trÞ ®îc qu©n ®èi ph¬ng, sö dông cÊu tróc d÷ liÖu lµ ®å thÞ cho thÕ cê ta cã thÓ ¸p dông ph¬ng ph¸p t×m tËp æn ®Þnh trong ®Ó tÝnh níc ®i cã lîi nhÊt cho cê ca r«, h¬n n÷a viÖc tÝnh to¸n ®êng ®i, níc ®i còng sÏ ®îc thuËn lîi h¬n.
VÊn ®Ò t« mµu ®å thÞ lµ viÖc t×m sè mµu tèi thiÓu ®Ó t« c¸c ®Ønh ®å thÞ sao cho nh÷ng ®Ønh kÒ nhau ph¶i kh¸c mµu nhau hay cßn gäi lµ t×m s¾c sè ®å thÞ. VÒ mÆt øng dông ta cã thÓ thÊy ®îc ¸p dông cho bµi to¸n lËp lÞch. LËp lÞch lµ viÖc bè trÝ hîp lý ®Ó sao cho kh«ng cã sù trïng lÆp nh lµ vÒ thêi gian vµ ®Þa ®iÓm... th× t¬ng øng trong ®å thÞ ph¶i t« mµu c¸c ®Ønh sao cho 2 ®Ønh kÒ nhau th× kh«ng trïng mµu. VËy nªn ch¨ng ph¸t triÓn nghiªn cøu vÊn ®Ò t« mµu ®å thÞ mét c¸ch ®Çy ®ñ h¬n ®Ó phôc vô cho bµi to¸n lËp lÞch.
Ch¬ng III. Chu tr×nh, ®êng Euler vµ Hamilton
- Chu tr×nh, ®êng ®i Euler : Chu tr×nh (®êng ®i) Euler lµ chu tr×nh (®êng ®i) ®i qua tÊt c¶ c¸c c¹nh ®å thÞ mçi c¹nh ®óng mét lÇn. Cã thÓ nãi ®· nhiÒu ngêi biÕt ®Õn chu tr×nh, ®êng ®i Euler khi mµ cha häc ®Õn lý thuyÕt vÒ Euler bëi v× ta hay gÆp c¸c bµi to¸n ®è vui lµ cho tríc mét h×nh vÏ víi yªu cÇu t« l¹i h×nh ®ã chØ b»ng mét nÐt liÒn. Cã nhiÒu vÊn ®Ò thùc tiÔn cã thÓ ¸p dông chu tr×nh (®êng ®i) Euler ®Ó gi¶i quyÕt nh lµ t×m hµnh tr×nh cho ngêi ph¸t th, xe röa ®êng... sao cho hµnh tr×nh lµ tèi u nhÊt.
- Chu tr×nh, ®êng ®i Hamilton : Chu tr×nh (®êng ®i) Hamilton lµ chu tr×nh (®êng ®i) ®i qua tÊt c¶ c¸c ®Ønh mçi ®Ønh ®óng mét lÇn. Kh¸c víi chu tr×nh, ®êng ®i Euler ®· cã c¸c ®iÒu kiÖn cÇn vµ ®ñ ®Ó nhËn biÕt nã trong ®å thÞ, cßn chu tr×nh, ®êng ®i Hamilton míi chØ cã ®iÒu kiÖn ®ñ. Chu tr×nh, ®êng ®i Hamilton còng cã nhiÒu øng dông thùc tiÔn vÝ dô nh cho 1 hÖ thèng m¹ng, mét m¸y nµo ®ã cÇn göi ®i 1 th«ng ®iÖp tíi tÊt c¶ c¸c m¸y kh¸c theo kiÓu truyÒn tin lu vµ chuyÓn tiÕp h·y t×m ®êng truyÒn tin thÝch hîp nhÊt.
Chu tr×nh, ®êng ®i Euler vµ Hamilton cã tÇm quan träng vµ ý nghÜa øng dông cao, nhng ®©y còng thùc sù lµ bµi to¸n khã, viÖc ®Ò cËp ®Çy ®ñ lý thuyÕt còng cha ®îc thùc hiÖn mét c¸ch trän vÑn ë trong ch¬ng.
Ch¬ng IV §êng ®i ng¾n nhÊt trong ®å thÞ
Cã nhiÒu bµi to¸n d¹ng tèi u cã thÓ vËn dông lý thuyÕt vÒ chu tr×nh, ®êng ®i Euler hoÆc Hamilton ®Ó gi¶i quyÕt, ngoµi ra ta cã thÓ ¸p dông lý thuyÕt vÒ ®êng ®i ng¾n nhÊt trong ®å thÞ ®Ó gi¶i quyÕt lo¹i bµi to¸n nµy. Bµi to¸n t×m ®êng ®i ng¾n nhÊt cã nhiÒu øng dông vÊn ®Ò lµ cÇn ®a ra thuËt to¸n h÷u hiÖu ®Ó gi¶i quyÕt lo¹i bµi to¸n nµy. Cã nhiÒu thuËt to¸n ®îc nªu ra, nhng ta sÏ quan t©m tíi thuËt to¸n ®îc dïng phæ biÕn vµ cã nhiÒu u ®iÓm ®ã lµ thuËt to¸n Dijkstra cho ®å thÞ cã träng sè. Nguyªn t¾c cña nhiÒu thuËt to¸n lµ ®¸nh träng sè d(v) c¸c ®Ønh sau ®ã tiÕn hµnh ®iÒu chØnh l¹i träng sè c¸c ®Ønh theo ®iÒu kiÖn sau:
NÕu d[u] + c[u, v] < d[v] th× d[v] := d[u] + c[u, v]
Trong ®ã träng sè d[v] lµ ®é dµi ®êng ®i ng¾n nhÊt tõ ®Ønh xuÊt ph¸t tíi ®Ønh v, c[u, v] lµ ma trËn träng sè.
T tëng cña thuËt to¸n Dijkstra lµ x©y dùng dÇn dÇn tËp S c¸c ®Ønh cã träng sè nhá nhÊt: mçi lÇn t×m ®îc ®Ønh cã träng sè nhá nhÊt th× dïng nã ®Ó ®iÒu chØnh träng sè c¸c ®Ønh kÒ víi nã sau ®ã ®a ®Ønh cã träng sè nhá nhÊt võa t×m ®îc vµo tËp S.
VÒ mÆt øng dông : Trong lÜnh vùc Tin häc, xÐt ë 1 m¹ng m¸y tÝnh nhiÒu khi ngêi ta cÇn x¸c ®Þnh mét ®êng truyÒn cã thêi gian truyÒn tin ng¾n nhÊt gi÷a 2 m¸y nµo ®ã. §Ó thùc hiÖn ®iÒu nµy cã thÓ m« h×nh m¹ng b»ng ®å thÞ sau ®ã vËn dông thuËt to¸n t×m ®êng ®i ng¾n nhÊt ®Ó gi¶i quyÕt.
C¸c øng dông th× cã nhiÒu, trong ch¬ng nµy ta sÏ ®Ò cËp mét c¸ch cô thÓ vÒ thuËt to¸n Viterbi vËn dông lý thuyÕt ®êng ®i ng¾n nhÊt ®Ó söa gãi tin bÞ truyÒn sai trong 1 hÖ thèng th«ng tin, ®©y lµ 1 øng dông kh¸ thiÕt thùc v× nã hay b¾t gÆp trong 1 hÖ thèng truyÒn tin. Khi nãi ®Õn bµi to¸n t×m ®êng ®i ng¾n nhÊt, ngêi ta còng hay më réng thµnh bµi to¸n t×m ®êng ®i dµi nhÊt. Víi vÊn ®Ò nµy trong ch¬ng còng nªu ra cô thÓ øng dông ®å thÞ cho viÖc lËp lÞch thi c«ng 1 c«ng tr×nh lín. §©y lµ 1 øng dông thuéc lo¹i bµi to¸n tèi u vËn dông ®êng ®i dµi nhÊt vµ ®ång thêi còng lµ øng dông cho c«ng t¸c lËp lÞch. §å thÞ cho øng dông nµy gäi lµ s¬ ®å m¹ng Pert, ®©y còng lµ lo¹i ®å thÞ cã u tiªn tríc sau vµ cuèi ch¬ng sÏ xÐt ®Õn øng dông cña lo¹i ®å thÞ nµy trong viÖc lËp tr×nh song song.
Ch¬ng V. Mét sè vÊn ®Ò vÒ c©y
Lµ néi dung cuèi cïng cña luËn v¨n, ch¬ng nµy sÏ ®Ò cËp ®Õn nhiÒu øng dông cña c©y cho viÖc ¸p dông, ph©n tÝch c¸c gi¶i thuËt c¬ së trong kü n¨ng lËp tr×nh. C©y lµ trêng hîp riªng cña ®å thÞ, cã nh÷ng ®Æc trng riªng dÔ nhËn thÊy ®ã lµ lu«n tån t¹i 1 ®êng ®i duy nhÊt gi÷a mäi cÆp ®Ønh, biÕt ®îc sè ®Ønh th× lu«n biÕt ®îc sè c¹nh... §Ó nghiªn cøu hÕt c¸c tÝnh chÊt vÒ c©y th× ®ã lµ c¶ 1 khèi lîng kiÕn thøc lín, ch¬ng nµy chØ ®Ò cËp tíi nh÷ng vÊn ®Ò c¬ b¶n nhÊt vÒ c©y vµ tËp trung khai th¸c nh÷ng øng dông cña nã.
Sù øng dông c©y trong viÖc ph©n tÝch c¸c gi¶i thuËt ®ã lµ nhiÒu thuËt to¸n cã thÓ m« h×nh b»ng c©y, hay nãi c¸ch kh¸c lµ dïng c©y ®Ó thÓ hiÖn, biÓu diÔn thuËt to¸n. Khi nh×n vµo c©y thÓ hiÖn thuËt to¸n ta sÏ hiÓu s©u s¾c thuËt to¸n h¬n lµ khi nghe ph¸t biÓu thuËt to¸n b»ng lêi bëi v× c©y cho ta c¸i nh×n trùc quan sinh ®éng, dêng nh thÊy ®îc hÕt c¸c bíc ®i ch¬ng tr×nh thuËt to¸n khi ch¹y trªn m¸y tÝnh. Ngoµi ra nh×n vµo m« h×nh c©y biÓu diÔn thuËt to¸n dÔ t¹o cho ta ®îc t duy lËp tr×nh cµi ®Æt thuËt to¸n h¬n lµ khi ta ®äc thuËt to¸n ®îc ph¸t biÓu b»ng lêi hay xem vµo s¬ ®å khèi cña thuËt to¸n.
C©y cã nhiÒu øng dông quan träng mµ trong ch¬ng sÏ ®Ò cËp tíi nh c©y t×m kiÕm, c©y quyÕt ®Þnh, c©y m· ho¸ tiÒn tè, c©y biÓu thøc... §©y lµ nh÷ng øng dông rÊt thiÕt thùc trong kü thuËt lËp tr×nh, ch¼ng h¹n nh trong mét ch¬ng tr×nh nµo ®ã, mét ngêi nhËp vµo mét biÓu thøc nhÞ nguyªn to¸n häc vËy lµm thÕ nµo mµ biÓu diÔn, lu tr÷ vµ xö lý biÓu thøc nµy trong m¸y tÝnh, ®iÒu nµy cã thÓ thùc hiÖn ®îc nhê sù vËn dông c©y biÓu diÔn biÓu thøc.
Trong lý thuyÕt ®å thÞ, khi nãi vÒ c©y th× c©y bao trïm lµ vÊn ®Ò kh«ng thÓ thiÕu. C©y bao trïm còng cã nhiÒu øng dông, ®Æc biÖt lµ c©y bao trïm ng¾n nhÊt, ta còng cã thÓ vËn dông nã ®Ó gi¶i lo¹i bµi to¸n tèi u vÝ dô nh bµi to¸n nèi m¹ng m¸y tÝnh sao cho chÝ phÝ nèi m¹ng lµ thÊp nhÊt. §Ó t×m c©y bao trïm nhá nhÊt trong ch¬ng sÏ giíi thiÖu ®Õn hai thuËt to¸n Kruskal vµ Prim, mçi thuËt to¸n ®Òu cã nh÷ng ®Æc ®iÓm riªng. Còng cã nh÷ng lóc ta chØ cÇn t×m c©y bao trïm nãi chung, ®Ó t×m c©y bao trïm trong ch¬ng còng sÏ ®Ò cËp tíi thuËt to¸n t×m kiÕm u tiªn theo chiÒu réng vµ chiÒu s©u, ®©y lµ thuËt to¸n rÊt c¬ së nhng lµ quan träng v× nã ®îc ¸p dông trong hÇu hÕt c¸c thuËt to¸n liªn quan ®Õn ®å thÞ.
KÕt luËn :
§Ò tµi ®îc thùc hiÖn xong còng ®· cã ®îc nh÷ng kÕt qu¶ nhÊt ®Þnh trong viÖc lµm s¸ng tá ®îc c¬ së lý thuyÕt ®å thÞ, thÓ hiÖn ®îc vai trß cña ®å thÞ lµ lµm c¬ së to¸n cho Tin häc, phôc vô ®¾c lùc trong kü thuËt lËp tr×nh vµ ®ång thêi nªu ®îc tÝnh øng dông cña ®å thÞ theo tõng néi dung lý thuyÕt. Bªn c¹nh nh÷ng kÕt qu¶ ®¹t ®îc còng cã nh÷ng ®iÒu cha ®îc nh nhiÒu vÊn ®Ò cña ®å thÞ cha nªu ra ®îc thuËt to¸n cô thÓ ®Ó gi¶i quyÕt, nhiÒu thuËt to¸n vÉn cha ®îc cµi ®Æt. VÒ mÆt øng dông th× cßn cã nhiÒu øng dông cßn nªu chung chung, míi dõng l¹i trªn m« h×nh lý thuyÕt cha cã nh÷ng sè liÖu chøng minh hay lµ ch¬ng tr×nh cµi ®Æt cô thÓ, khi ®i tõng néi dung lý thuyÕt ®å thÞ th× chØ nªu ®îc c¸c øng dông cña phÇn néi dung lý thuyÕt ®ã mµ cha nªu ®îc c¸c øng dông cña tæng hîp nhiÒu néi dung lý thuyÕt ®å thÞ.
Cuèn luËn v¨n ®îc hoµn thµnh sau thêi gian gÇn 3 th¸ng, t¸c gi¶ sÏ kh«ng thÓ nµo hoµn thµnh ®îc ®Ò tµi cña m×nh nÕu nh kh«ng nhËn ®îc sù gióp ®ì, híng dÉn tËn t×nh cña thÇy gi¸o Pgs. Ts §ç §øc Gi¸o, t¸c gi¶ xin ch©n thµnh bµy tá lßng biÕt ¬n ®èi víi thÇy Pgs. Ts §ç §øc Gi¸o vµ cïng toµn thÓ c¸c thÇy c« gi¸o, c¸n bé khoa C«ng nghÖ Th«ng tin trêng §¹i häc D©n lËp §«ng §« vµ b¹n bÌ ®· quan t©m, ®éng viªn gióp ®ì t¸c gi¶ hoµn thµnh cuèn luËn v¨n nµy.
Hµ néi 6/2000
Sinh viªn thùc hiÖn: Phan Thanh Long.
Môc lôc
Trang
Giíi thiÖu .................................................................................................. 1
Mét sè vÊn ®Ò c¬ b¶n cña ®å thÞ ............................................................. 1
Sè æn ®Þnh vµ t« mµu ®å thÞ .................................................................... 2
Chu tr×nh, ®êng ®i Euler vµ Hamilton ................................................ 3
§êng ®i ng¾n nhÊt trong ®å thÞ ............................................................ 4
Mét sè vÊn ®Ò vÒ c©y ............................................................................... 4
KÕt luËn .................................................................................................... 5
Ung dung do thi trong Tin hoc.rar
