Đề tài Một số vấn đề ứng dụng của đồ thị trong Tin học

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ý 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 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 chưa đầy đủ nhưng 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ị, nhưng 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 nhưng 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à lưu 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ớ để lưu 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ớ để lưu 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ớ để lưu 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à chưa 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 lưu 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, nhưng đây cũng thực sự là bài toán khó, việc đề cập đầy đủ lý thuyết cũng chưa đượ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, nhưng 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 trưng 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, lưu 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ở nhưng 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 chưa được như nhiều vấn đề của đồ thị chưa nêu ra được thuật toán cụ thể để giải quyết, nhiều thuật toán vẫn chưa đượ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 chưa 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à chưa 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