Luận văn Mô hình đồ thị và ứng dụng đối với bài toán cộng đồng trên mạng xã hội

em làm luận văn tốt nghiệp này. Tiếp theo em xin gửi lời cảm ơn đến đến các thầy cô giáo trường Đại học Công nghệ Thông tin và Truyền thông - Đại học Thái Nguyên, đã tận tâm truyền đạt những kiến thức quý báu làm nền tảng để em hoàn thành luận văn này. Học Viên Hoàng Văn Dũng 1 LỜI CAM ĐOAN Tôi xin cam đoan mô hình đồ thị và ứng dụng đối với bài toán cộng đồng trên mạng xã hội được trình bày trong luận văn là do tôi thực hiện dưới sự hướng dẫn của thầy Vũ Vinh Quang Tất cả những tham khảo từ các nghiên cứu liên quan đều được nêu nguồn gốc một cách rõ ràng từ danh mục tài liệu tham khảo trong luận văn. Trong luận văn không có việc sao chép tài liệu, công trình nghiên cứu của người khác mà không chỉ rõ về tài liệu tham khảo. Thái Nguyên, ngày tháng năm 2020 Học viên Hoàng Văn Dũng 2 MỤC LỤC LỜI MỞ ĐẦU....1 Chƣơng 1: MỘT SỐ KIẾN THỨC CƠ BẢN VỀ MÔ HÌNH ĐỒ THỊ3 Một số khái niệm cơ bản ......3 Định nghĩa về đồ thị....3 Các thuật ngữ cơ bản..4 Đường đi, chu trình. Đồ thị liên thông........5 Một số phƣơng pháp mô tả đồ thị........5 Cấu trúc ma trận kề .......5 Cấu trúc danh sách kề.7 Một số thuật toán trên đồ thị...8 Các thuật toán duyệt đồ thị..8 Bài toán cây khung nhỏ nhất.........9 Bài toán xác định đường đi ngắn nhất.....12 Kết luận chương 1......15 Chƣơng 2: MÔ HÌNH MẠNG XÃ HỘI VÀ BÀI TOÁN CỘNG ĐỒNG..17 Khái niệm về bài toán cộng đồng..17 Một số độ đo trên đồ thị..18 Độ đo trung tâm của đỉnh........18 Độ đo trung gian của đỉnh19 Độ đo gần nhau theo khoảng cách trắc địa...21 Độ đo trung tâm của đồ thị....22 Độ đo trung gian của cạnh...22 Độ trung tâm véc tơ đặc trưng....25 Thuật toán phát hiện cộng đồng........26 Giới thiệu về họ thuật toán Girvan và Newman......27 Giới thiệu về thuật toán CONGA....28 Kết luận chương 2........33 Chƣơng 3: MỘT SỐ KẾT QUẢ THIẾT KẾ VÀ THỰC NGHIỆM CÁC THUẬT TOÁN Xác định độ đo trung tâm của đỉnh..34 Xác định độ đo trung gian của đỉnh.....35 3 Xác định độ đo trung gian của cạnh......36 Kết luận chương 3........41 TÀI LIỆU THAM KHẢO..42 4 DANH SÁCH CÁC HÌNH VẼ Hình 1.1: (a) Một đồ thị vô hướng; ....6 (b) Biểu diễn ma trận kề;.6 (c) Biểu diễn danh sách kề..6 Hình 1.2: (a) Một đồ thị có hướng; ....7 (b) Ma trận kề: ....7 (c) Biểu diễn danh sách kề. ....7 Hình 1.3: (a) Đồ thị trọng số; .....7 (b) Ma trận kề: ....7 (c) Danh sách kề......7 Hình 1.4: Duyệt cây theo chiều rộng BFS..9 Hình 2.1: Hai đỉnh v2, v5 cùng hạng 1 và các đỉnh còn lại cùng hạng 2..19 Hình 2.2: Ví dụ trường hợp không phân tách đỉnh v trong đồ thị....30 Hình 2.3: Ví dụ về phép phân chia một đỉnh trong đồ thị.........31 Hình 2.4: Tìm phép phân chia tối ưu....32 Hình 3.1: Độ đo trung tâm của các đỉnh trong đồ thị ...............35 Hình 3.2: Đồ thị G vô hướng ...36 Hình 3.3.40 5 MỞ ĐẦU Mô hình đồ thị là một mô hình cấu trúc dữ liệu kinh điển trong tin học, đối với mô hình này, chúng ta thường quan tâm đến việc mô tả cấu trúc trong máy tính điện tử và các thuật toán tìm kiếm, tối ưu trên mô hình này. Có thể nói việc nghiên cứu ứng dụng của mô hình đồ thị trong thực tế là một lĩnh vực vô cùng rộng lớn và có ý nghĩa thực tế rất cao. Đa số các nguồn dữ liệu hiện nay đều có thể biểu diễn được dưới dạng cấu trúc dữ liệu đồ thị, thí dụ như dữ liệu mạng internet, mạng xã hội, cấu trúc protein, các hợp chất hóa học, quy trình của một chương trìnhCấu trúc đồ thị được đánh giá là cấu trúc có tính bao quát mô tả các đối tượng so với các cấu trúc tuần tự, cây, mạng ngữ nghĩavà dựa trên cấu trúc này có thể thiết kế được nhiều thuật toán giải quyết được nhiều bài toán có độ tính toán phức tạp cao. Mỗi dữ liệu lớn trên các hệ thống mạng đều có thể biểu diễn dưới dạng các đồ thị và mối quan hệ của chúng theo các liên kết và kết nối vật lý; kết nối giữa các mạng trong lớp mạng; mối quan hệ trong mạng xã hội; siêu liên kết giữa các trang web và các tương tác phức tạp giữa các thực thể. Các đồ thị chứa đựng những thông tin giá trị cho việc ứng dụng vào hệ thống mạng như những phát hiện từ cộng đồng, những điểm chung; phân lớp; tìm kiếm trên mạng; những hệ thống được đưa ra theo thứ tự nào đó; độ tin cậy và uy tín; tìm kiếm và lấy dữ liệu từ điểm đến điểm. Để đưa các dữ liệu đang xét vào dưới dạng đồ thị, chúng ta cần phải định nghĩa các ma trận mô tả cấu trúc tổng thể của đồ thị; định nghĩa các ma trận mô tả các mẫu đặc trưng của các giao tiếp bên trong đồ thị phải tìm ra các cấu trúc có tính đặc trưng cộng đồng của mạng; hiểu rõ mô hình của việc lấy ra từ các đồ thị; phát triển và ứng dụng những thuật toán hiểu quả nhất để khai thác dữ liệu trong hệ thống mạng. Nhiều dữ liệu có cấu trúc đều có thể được biểu diễn bằng mạng, bằng tập hợp các đỉnh được nối với nhau theo cặp bằng các liên kết, như mạng sinh học, sự hợp tác của các nhà nghiên cứu, Đặc điểm quan trọng gắn kết các mạng lại với nhau đó là cấu trúc cộng đồng, trong đó có các nhóm có mật độ kết nối mạnh của các đỉnh trong nhóm và các kết nối yếu giữa các nhóm. Do đó, việc xác định cộng đồng có thể được xem như là việc tìm kiếm các cụm đỉnh phân nhóm. Một cộng đồng là một nhóm của các thực thể dùng chia sẻ những tài sản tương tự nhau hoặc kết nối với nhau thông qua mối quan hệ được lựa chọn. Việc xác định các kết nối và định vị các thực thể trong cộng đồng khác nhau được coi là mục tiêu chính của nghiên cứu phát hiện cộng đồng. Bằng trực quan có thể dễ dàng tìm ra những nhóm cộng đồng có 6 độ tập trung cao, nhưng không phải cộng đồng nào cũng được hình thành bằng các mối liên hệ chặt chẽ và dễ thấy vì một số cộng đồng được hình thành dưới dạng ẩn. Điều quan trọng là phải tìm được sự phân phối của các cạnh giữa các đỉnh, từ đó phát hiện và đưa ra các cộng đồng tồn tại bên trong mạng xã hội. Như vậy, khai phá dữ liệu đồ thị và phát hiện cấu trúc cộng đồng trên mạng xã hội là một lĩnh vực nghiên cứu khá hấp dẫn và được các nhà khoa học quan tâm nghiên cứu. Xuất phát từ một đồ thị mạng xã hội, người ta tìm ra các cụm, các nhóm cộng đồng có mối liên hệ chặt chẽ với nhau, từ đó phát hiện và tìm ra đặc tính của cấu trúc mạng. Mục tiêu chính của luận văn đặt ra là nghiên cứu các đặc trưng cơ bản về mô hình đồ thị, một số các thuật toán tìm kiếm tối ưu trên mô hình đồ thị. Khái niệm về bài toán cộng đồng và một số thuật toán xác định cộng đồng trên mạng xã hội. Dự kiến nội dung báo cáo của luận văn gồm: Phần mở đầu, 3 chương chính, phần kết luận, tài liệu tham khảo, phụ lục. Bố cục được trình bày như sau: Phần mở đầu: Nêu lý do chọn đề tài và hướng nghiên cứu chính của luận văn Chƣơng 1: Trình bày tổng quan về mô hình đồ thị bao gồm: Các khái niệm cơ bản, các phương pháp mô tả đồ thị, các thuật toán duyệt đồ thị và trọng tâm là các thuật toán xác định đường đi ngắn nhất trên đồ thị [1, 2, 3, 4, 6, 7]. Chƣơng 2. Trình bày các khái niệm cơ bản về mô hình mạng xã hội và bài toán cộng đồng bao gồm: Tổng quan về mạng xã hội, khái niệm về độ đo đỉnh và độ đo cạnh, các thuật toán tương ứng. Khái niệm về cộng đồng và một số thuật toán xác định cộng đồng, Họ thuật toán Girvan_Newman, thuật toán CONGA[5, 8, 9]. Chƣơng 3 Đưa ra một số kết quả cài đặt các thuật toán: thuật toán xác định độ đo đỉnh, thuật toán xác định độ đo cạnh, thuật toán xác định cộng đồng. Các kết quả cài đặt các thuật toán được thực hiện trên môi trường Matlab version 7.0 7 Chƣơng 1 MỘT SỐ KIẾN THỨC CƠ BẢN VỀ MÔ HÌNH ĐỒ THỊ Nội dung chương 1 đưa ra các khái niệm cơ bản về lý thuyết đồ thị, các thuật toán cơ bản trên mô hình đồ thị. Các kiến thức được tham khảo trong các tài liệu [1] [2] 1.1 Một số khái niệm cơ bản [1] 1.1.1 Định nghĩa về đồ 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 này, các loại đồ thị khác nhau được phân biệt bởi kiểu và số lượng cạnh nối hai đỉnh nào đó của đồ thị. Giả sử V là tập hữu hạn, không rỗng các phần tử nào đó. Bộ G = (V,E) được gọi là đồ thị hữu hạn. Mỗi phần tử của V gọi là một đỉnh và mỗi phần tử u = (x,y) của E được gọi là một cạnh của đồ thị G = (V,E). Xét một cạnh u của E khi đó tồn tại hai đỉnh x, y của V sao cho u = (x,y), ta nói rằng x nối với y hoặc x và y phụ thuộc u.  Nếu cạnh u = (x,y) mà x và y là hai đỉnh phân biệt thì ta nói x, y là hai đỉnh kề nhau.  Nếu u = (x,x) thì u là cạnh có hai đỉnh trùng nhau ta gọi đó là một khuyên.  Nếu u = (x,y) mà x, y là cặp đỉnh có phân biệt thứ tự hay có hướng từ x đến y thì u là một cung, khi đó x là gốc còn y là ngọn hoặc x là đỉnh vào, y là đỉnh ra.  Khi giữa cặp đỉnh (x,y) có nhiều hơn một cạnh thì ta nói rằng những cạnh cùng cặp đỉnh là những cạnh song song hay là cạnh bội. Trong thực tế ta có thể gặp nhiều vấn đề mà có thể dùng mô hình đồ thị để biểu diễn, như sơ đồ mạng máy tính, sơ đồ mạng lưới giao thông, sơ đồ thi công một công trình. Định nghĩa 1. Đơn đồ thị vô hướng G = (V,E) bao gồm V là các tập đỉnh và E là các tập các cặp không có thứ tự gồm hai phần tử khác nhau của V gọi là các cạnh. Định nghĩa 2. Đa đồ thị vô hướng G = (V,E) bao gồm V là tập các đỉnh, và E là họ các cặp không có thứ tự gồm hai phần tử khác nhau của V gọi là các cạnh. Hai cạnh e1 và e2 được gọi là cạnh lặp nếu chúng cùng tương ứng với một cặp đỉnh. Rõ ràng mỗi đơn đồ thị là đa đồ thị, nhưng không phải đa đồ thị nào cũng là đơn đồ thị, vì trong đa đồ thị có thể có hai (hoặc có nhiều hơn) cạnh nối một cặp đỉnh nào đó. 8 Định nghĩa 3. Giả đồ thị vô hướng G = (V,E) bao gồm V là các tập đỉnh, và E là họ các cặp không có thứ tự (không nhất thiết phải khác nhau) của V gọi là các cạnh. Cạnh e được gọi là khuyên nếu nó có dạng e = (u,u). Định nghĩa 4. Đơn đồ thị có hướng G = (V,E) bao gồm V là các tập đỉnh và E là các cặp có thứ tự gồm hai phần tử khác nhau của V gọi là các cung. Nếu trong mạng có thể có đa kênh thoại một chiều, ta sẽ phải sử dụng đến khái niệm đa đồ thị có hướng: Định nghĩa 5. Đa đồ thị có hướng G = (V,E) bao gồm V là các tập đỉnh và E là họ các cặp có thứ tự gồm hai phần tử khác nhau của V gọi là các cung. Hai cung e1, e2 tương ứng cùng với một cặp đỉnh được gọi là cung lặp. Trong các phần tử tiếp theo chủ yếu chúng ta sẽ làm việc với đơn đồ thị vô hướng và đơn đồ thị có hướng. Vì vậy, để ngắn gọn, ta bỏ qua tính từ đơn khi nhắc đến chúng. 1.1.2 Các thuật ngữ cơ bản Định nghĩa 6. Hai đỉnh u và v của đồ thị vô hướng G được gọi là kề nhau nếu (u,v) là cạnh của đồ thị G. Nếu e = (u,v) là cạnh của đồ thị thì ta nói cạnh này là liên thuộc với hai đỉnh u và v, hoặc cũng nói là cạnh e là nối đỉnh u và đỉnh v, đồng thời các đỉnh u và v sẽ được gọi là các đỉnh đầu của cạnh (u,v). Định nghĩa 7. Ta gọi bậc của đỉnh v trong đồ thị vô hướng là số cạnh liên thuộc với nó và sẽ ký hiệu là deg(v). Định nghĩa 8. Nếu e = (u,v) là cung của đồ thị có hướng G thì ta nói hai đỉnh u và v là kề nhau, và nói cung (u,v) nối đỉnh u với đỉnh v hoặc cũng nói cung này là đi ra khỏi đỉnh u và đi vào đỉnh v. Đỉnh u(v) sẽ được gọi là đỉnh đầu(cuối) của cung (u,v). Định nghĩa 9. Ta gọi bán bậc ra (bán bậc vào) của đỉnh v trong đồ thị có hướng là số cung của đồ thị đi ra khỏi nó (đi vào nó) và ký hiệu là deg+(v)(deg-(v)). 1.1.3 Đường đi, chu trình. Đồ thị liên thông. Định nghĩa 10. Đường đi độ dài n từ đỉnh u đến đỉnh v, trong đó n là số nguyên dương, trên đồ thị vô hướng G = (V,E) là dãy x0, x1,, xn-1, xn trong đó u = x0, v = xn, (xi, xi+1)  E, i = 0,1,2,, n-1. Đường đi nói trên còn có thể biểu diễn dưới dạng dãy các cạnh: (x0,x1), (x1,x2),, (xn-1,xn). Đỉnh u gọi là đỉnh đầu, còn đỉnh v gọi là đỉnh cuối của đường đi. Đường đi có đỉnh đầu trùng với đỉnh cuối (tức là u = v) được gọi là chu trình. Đường đi hay chu trình 9 được gọi là đơn nếu như không có cạnh nào bị lặp lại. Khái niệm đường đi và chu trình trên đồ thị có hướng được định nghĩa hoàn toàn tương tự như trường hợp đồ thị vô hướng, chỉ khác là ta có chú ý đến hướng trên các cung. Định nghĩa 11. Đồ thị vô hướng G = (V,E) được gọi là liên thông nếu luôn tìm được đường đi giữa hai đỉnh bất kỳ của nó. Như vậy hai máy tính bất kỳ trong mạng có thể trao đổi thông tin được với nhau khi và chỉ khi đồ thị tương ứng với mạng này là đồ thị liên thông. 1.2 Một số phƣơng pháp mô tả đồ thị [1][2] Với một biểu đồ nhất định có một số biểu diễn khác nhau. Việc dễ dàng cài đặt các thuật toán trên đồ thị cũng như hiệu quả của thuật toán phụ thuộc vào sự lựa chọn cách biểu diễn đồ thị đúng đắn. Hai cấu trúc được sử dụng phổ biến nhất để biểu diễn một đồ thị (có hướng hay vô hướng) là ma trận kề và danh sách kề. 1.2.1 Cấu trúc ma trận kề Giả sử G = (V, E) là đơn đồ thị có số đỉnh (ký hiệu |V| là n), không mất tính tổng quát có thể coi các đỉnh được đánh số 1, 2, ..., n. Khi đó, ta có thể biểu diễn đồ thị bằng một ma trận vuông A cấp n trong đó A(i,j)=1 nếu cạnh (i,j) là tồn tại và A(i,j)=0 nếu cạnh (i,j) không tồn tại. Trong trường hợp khi đồ thị có trọng số thì chúng ta có cấu trúc ma trận trọng số là một ma trận vuông A cấp n trong đó A(i,j)=trọng số của cạnh nếu cạnh (i,j) là tồn tại và A(i,j)=  nếu cạnh (i,j) không tồn tại (A(i,i)=0 nếu không tồn tại khuyên.  Các tính chất của ma trận liền kề: + Với đồ thị vô hướng G, ma trận liền kề tương ứng là ma trận đối xứng. + Nếu G là đồ thị vô hướng và A là ma trận liền kề tương ứng thì ta có Tổng các số trên hàng i = tổng các số trên cột i = Bậc của đỉnh i = deg(i)  Ưu điểm của ma trận liền kề: Đơn giản, trực quan, dễ cài đặt. 10  Nhược điểm của ma trận liền kề: Số cạnh của đồ thị là nhiều hay ít, ma trận liền kề luôn đòi hỏi n2 ô để lưu các phần tử ma trận gây lãng phí bộ nhớ dẫn tới không thể biểu diễn được đồ thị với số đỉnh lớn. Hình 1.1: (a) Một đồ thị vô hướng; (b) Biểu diễn ma trận kề; (c) Biểu diễn danh sách kề. Hình 1.2: (a) Một đồ thị có hướng; (b) Ma trận kề: (c) Biểu diễn danh sách kề. 11 Hình 1.3: (a) Đồ thị trọng số ; (b) Ma trận kề: (c) Danh sách kề. 1.2.2 Cấu trúc danh sách kề Để mô tả đồ thị G, chúng ta có thể sử dụng cấu trúc danh sách theo tư tưởng: một đỉnh x bất kì sẽ lưu trữ các đỉnh kề với x bằng một danh sách tuyến tính.  Các tính chất của danh sách kề: + Với cấu trúc danh sách kề thì số phần tử trong danh sách kề với mỗi đỉnh chính bằng bậc của đỉnh đó + Thường sử dụng cấu trúc con trỏ để mô tả 1.3 Một số thuật toán trên đồ thị [1][2] 1.3.1 Các thuật toán duyệt đồ thị  Thuật toán duyệt theo chiều sâu DFS Tư tưởng của thuật toán: theo tư tưởng đệ quy tức là mọi đỉnh x kề với S sẽ đến được từ S, với mỗi đỉnh x thì những đỉnh y kề với x cũng đến được từ S. Điều đó gợi ý cho ta viết một thủ tục đệ quy DFS(u) mô tả việc duyệt từ đỉnh u bằng cách thông báo thăm đỉnh u và tiếp tục quá trình duyệt DFS(v) với v là một đỉnh chưa thăm kề với u. Để cài đặt đệ quy ta cần chú ý: Để không một đỉnh nào bị liệt kê tới hai lần, ta sử dụng kỹ thuật đánh dấu, mỗi lần thăm một đỉnh, ta đánh dấu đỉnh đó lại để các bước duyệt đệ quy kế tiếp không duyệt lại đỉnh đó nữa. Để lưu lại đường đi từ đỉnh xuất phát S, trong thủ tục DFS(u), trước khi gọi đệ quy DFS(v) với v là một đỉnh kề với u mà chưa đánh dấu, ta lưu lại vết đường đi từ u tới v bằng cách đạt TRACE[v] := u, tức là TRACE[v] lưu lại đỉnh liền trước v trong đường đi từ S tới v. Thủ tục DFE được mô tả như sau 12 Procedure DFS(u) Input: G, u Output: Danh sách các đỉnh BEGIN 1: Đánh dấu u là được thăm (có thể tới được từ S); 2: Xét mọi đỉnh v kề với u mà chưa thăm, với mỗi đỉnh v đó; + Trace[v] := u; //Lưu vết đường đi + DFS(v); // Gọi đệ quy END;  Thuật toán duyệt theo chiều rộng BFS Tư tưởng: Việc thăm một đỉnh sẽ lên lịch duyệt các đỉnh kề với nó nhất. Như vậy, thứ tự duyệt là ưu tiên chiều rộng. Ví dụ: Trong Hình 1.3, bắt đầu thăm đỉnh S. Việc thăm đỉnh S sẽ phát sinh thứ tự duyệt những đỉnh kề với S. Chọn 1 đỉnh x để thăm. Khi thăm đỉnh x sẽ phát sinh yêu cầu duyệt những đỉnh kề với x Hình 1.4: Duyệt cây theo chiều rộng BFS. Thuật toán duyệt theo chiều rộng được mô tả bằng thủ tục sau đây: Procedure BFS(u) Input: G, u Output: Danh sách các đỉnh 1: Khởi tạo: + Các đỉnh ở trạng thái chưa đánh dấu, trừ đỉnh xuất phát S. + Hàng đợi Q=S //Chứa các đỉnh sẽ được duyệt theo thứ tự. 2: Đẩy S vào ngăn xếp; 13 3: repeat 4: Lấy u khỏi hàng đợi; 5: Thông báo thăm u; //Bắt đầu việc duyệt đỉnh u 6: if then 7: Ghi nhận vết đường đi từ u tới v; 8: Đẩy v vào hàng đợi; //v sẽ chờ được duyệt tại những bước sau 9: end if 10: until (Hàng đợi rỗng:); 11: Truy vết tìm đường đi; End. 1.3.2 Bài toán cây khung nhỏ nhất Giới thiệu bài toán Bài toán tìm cây khung nhỏ nhất của đồ thị là một trong số những bài toán tối ưu trên đồ thị tìm được ứng dụng trong nhiều lĩnh vực khác nhau của đời sống. Trong phần này ta sẽ có hai thuật toán cơ bản để giải bài toán này. Trước hết, nội dung của bài toán được phát biểu như sau. Cho G = (V, E) là một đồ thị vô hướng liên thông. Với V= {1,2,.., n } và tập cạnh E gồm m cạnh. Với mỗi cạnh e của đồ thị được gán với một số không âm. c(e) gọi là độ dài của nó. Giả sử H=(V, T) là cây khung của đồ thị G (T tập cạnh nhỏ nhất của cây khung). Ta gọi độ dài C(H) của cây khung H là tổng độ dài của các cạnh của nó: C(H) = c(e) eT Bài toán đặt ra là trong số tất cả các cây khung của đồ thị G hãy tìm cây khung với độ dài C(H) nhỏ nhất. Cây khung như vậy gọi là cây khung nhỏ nhất của đồ thị và bài toán đặt ra được gọi là bài toán cây khung nhỏ nhất. Do tính chất của cây, nên nếu đồ thị G có n đỉnh thì cây khung có đúng n-1 cạnh. Để minh hoạ cho những ứng dụng của bài toán cây khung nhỏ nhất, dưới đây là hai mô hình thực tế tiêu biểu cho nó. * Bài toán xây dựng hệ thống đường sắt: Giả sử ta muốn xây dựng một hệ thống đường sắt nối n thành phố sao cho hành khách có thể đi từ bất cứ một thành phố nào đến bất kỳ một trong số các thành phố còn lại. Mặt khác, trên quan điểm kinh tế đòi 14 hỏi là chi phí về xây dựng hệ thống đường phải là nhỏ nhất. Rõ ràng là đồ thị mà đỉnh là các thành phố còn các cạnh là các tuyến đường sắt nối các thành phố tương ứng, với phương án xây dựng tối ưu phải là cây. Vì vậy, bài toán đặt ra dẫn về bài toán tìm cây khung nhỏ nhất trên đồ thị đầy đủ n đỉnh, mỗi đỉnh tương ứng với một thành phố với độ dài trên các cạnh chính là chi phí xây dựng hệ thống đường sắt nối hai thành phố. * Bài toán nối mạng máy tính: Cần nối mạng một hệ thống gồm n máy tính đánh số từ 1 đến n. Biết chi phí nối máy i với máy j là m(i,j) (thông thường chi phí này phụ thuộc vào độ dài cáp nối cần sử dụng). Hãy tìm cách nối mạng sao cho tổng chi phí là nhỏ nhất. Bài toán này cũng dẫn về bài toán tìm cây khung nhỏ nhất. Bài toán tìm cây khung nhỏ nhất đã có những thuật toán rất hiệu quả để giải chúng. Sau đây chúng ta sẽ nghiên cứu 2 thuật toán cây khung nhỏ nhất kinh điển  Thuật toán Kruskal Tư tưởng của thuật toán là duyệt trong danh sách cạnh đã sắp xếp từ nhỏ đến lớn theo trọng số, kết nạp lần lượt các cạnh vào tập T sao cho không tạo thành chu trình trong tập này. Thuật toán sẽ dừng khi T chứa đúng n-1 cạnh. Thuật toán được mô tả như sau: Procedure Kruskal Begin Sắp xếp Ci,j; T=; While |T| <(n-1) and (E  ) Do Begin Chọn e là cạnh có độ dài nhỏ nhất trong E; E:=E\  e  ; If (T  e không chứa chu trình ) then T:=T e; End; If |T| <(n-1) then Đồ thị không liên thông End. Nhận xét: 15 - Bài toán tìm cây khung lớn nhất có thể đưa về bài toán tìm cây khung nhỏ nhất bằng cách đổi dấu tất cả các trọng số của Ci,j, hoặc có thể cài đặt một cách độc lập bằng cách kết nạp dần vào cây từ cạnh lớn đến cạnh nhỏ nhất. - Trong thuật toán việc khó nhất là kiểm tra xem có tạo thành chu trình hay không? - Khối lượng tính toán nhiều nhất của thuật toán là ở bước sắp xếp các cạnh, vì vậy độ phức tạp tính toán của thuật toán phụ thuộc vào cách chọn thuật toán sắp xếp.  Thuật toán Prim Thuật toán Kruskal làm việc kém hiệu quả đối với những đồ thị dày (đồ thị có số cạnh là n(n-1)/2). Trong trường hợp đó người ta xây dựng một thuật toán hiệu quả hơn đó là thuật toán prim. Thuật toán prim còn được gọi là phương pháp lân cận gần nhất. Trong phương pháp này, bắt đầu từ một đỉnh tuỳ ý của đồ thị s, bắt đầu ta nối s với đỉnh lân cận gần nó nhất, chẳng hạn là t, nghĩa là trong số các cạnh kề của s thì cạnh (s,t) có độ dài ngắn nhất. Tiếp theo trong số những cạnh kề với hai đỉnh s, t ta lại tìm cạnh có độ dài nhỏ nhất. Cạnh này dẫn đến một đỉnh thứ 3 là z, và ta thu được bộ phận gồm 3 đỉnh và 2 cạnh. Quá trình này sẽ tiếp tục cho đến khi ta thu được bộ cây gồm n đỉnh và n-1 cạnh sẽ chính là cây khung nhỏ nhất cần tìm. Giả sử đồ thị cho bởi ma trận Ci,j (i,j=1..n). Trong quá trình thực hiện thuật toán, ở mỗi bước để có thể nhanh chóng chọn đỉnh và cạnh cần bổ sung vào cây khung thì các đỉnh của đồ thị sẽ được gán cho các nhãn. Nhãn của đỉnh v sẽ gồm hai phần: [d[v],near[v]], trong đó d[v] dùng để ghi nhận độ dài của các cạnh có độ dài nhỏ nhất trong số các cạnh nối đỉnh v với các đỉnh của cây khung đang xây dựng. Còn near[v] ghi nhận của cây khung gần v nhất. Thuật toán Prim được mô tả bằng thủ tục sau: Procedure Prim G: Đơn đồ thị liên thông n đỉnh c trọng số ; Input: Đồ thị liên thông n đỉnh có trọng số dương. Output: Cây khung nhỏ nhất T của đồ thị. BEGIN VT:= {u};ET:=  ; D u := 0; near u := u; gán nh n cho đỉnh đầu tiên u 0,u D u : Trọng số nhỏ nhất của các cạnh tới u ;near u : Đỉnh gần u nhất For v V – VT do Begin D[v]:= C[u,v];Near[v]:= u: End; 16 2. (Bước lặp) Stop:=False; While not Stop Do Begin - Tìm s  V – VT thỏa m n D[s]:=min{D[v]: v V–VT} - VT:= VT  {s}; ET:=ET {(s, near[s])}; - If | ET |:= (n -1) Then Begin T:=(VT, ET) là khung cây nhỏ nhất Stop:= True; End Else For v V – VT do If D[v] > C[s,v] Then Begin D[v]:= C[s,v]; near[v]:=s; End; End; END; Trong thực hành tính toán, ta thường xây dựng bảng để thay đổi nhãn của tất cả các đỉnh. Ví dụ: Tìm cây khung nhỏ nhất bằng thuật toán Prim của đồ thị gồm các đỉnh A, B, C, D, E, F, H, I được cho bởi ma trận trọng số sau. 17 Lập bảng tính toán, ta có V.lặp A B C D E F H I VT ET K.tạo  [A,15] [A,16] [A,19] [A,23] [A,20] [A,32] [A,18] A  1   [A,16] [B,13] [A,23] [B,19] [B,20] [B,12] A, B (A,B) 2   [A,16] [I,11] [I,21] [I,18] [I,14]  A, B, I (A,B), (B,I) 3   [D,13]  [I,21] [I,18] [I,14]  A, B, I, D (A,B), (B,I), (I,D) 4     [I,21] [I,18] [I,14]  A, B, I, D, C (A,B), (B,I), (I,D), (D,C) 5     [I,21] [H,17]   A, B, I, D, C, (A,B), (B,I), H (I,D), (D,C), (I,H) 6     [I,21]    A, B, I, D, C, (A,B), (B,I), H, F (I,D), (D,C), (I,H), (H,F) 7         A, B, I, D, C, (A,B), (B,I), H, F, E (I,D), (D,C), (I,H), (H,F), (I,E) Vậy độ dài cây khung nhỏ nhất là: 15 + 12 + 11 + 13 + 14 + 17 + 21 = 103. 18 1.3.3 Bài toán xác định đường đi ngắn nhất Cho đơn đồ thị G = (V, E) liên thông, có trọng số dương, V v1, v 2 ,..., vnm , E e 1 , e 2 ,..., e . Mỗi cạnh eij  (,) vij v được gán với một trọng số dương Cij xác định như sau: - Cij nếu (,)vij v E - Cij  0 nếu vvij - Cij = trọng số thực nếu (,)vij v E Yêu cầu: Tìm đường đi ngắn nhất từ một đỉnh nguồn tới các đỉnh còn lại của đồ thị Sau đây chúng ta sẽ nghiên cứu 2 thuật toán quan trọng về đường đi ngắn nhất. Bài toán 1: Tìm đường đi ngắn nhất từ một đỉnh nguồn tới một đỉnh đich  Thuật toánDijkstra: Tƣ tƣởng - Xây dựng một tập S các đỉnh mà độ dài đường đi từ gốc tới nó là ngắn nhất. Lúc đầu S chỉ chứa đỉnh gốc giả sử là a, ở mỗi bước ta thêm vào S một trong số các đỉnh còn lại của v mà độ dài từ a đến v là ngắn nhất. - Dùng mảng D[2..n], trong đó D[u] để ghi độ dài đường đi ngắn nhất hiện thời từ a tới đỉnh u. - Ban đầu vì S chỉ chứa a, nên D[u] = C[a,u]. Tại mỗi bước ta sẽ chọn đỉnh v V\ S mà D[v] là nhỏ nhất và thêm v vào S. Sau khi thêm v vào S ta xác định lại các D[u] với uS . Nếu độ dài đường đi đặc biệt qua đỉnh v (vừa được chọn) mà nhỏ hơn D[u] thì ta lấy D[u] là độ dài đường đi đó. Khi S = V thì D[u] lưu độ dài ngắn nhất từ 1 đến u. - Sử dụng mảng P[2..n] trong đó P[u] = v nếu v là đỉnh kề trước của u. Thuật toán Input: Ma trận trọng số C (dương) của đồ thị với đỉnh gốc là a. Output: Khoảng cách từ gốc a tới các đỉnh của đồ thị Procedure Dijkstra; Begin S:= {a} ; D[a]:=0; 19 For uV( {a}) do Begin D[u]:= C[a,u] ; D u : ảng lưu độ dài ngắn nhất từ gốc tới u C a,u : Giá trị trọng số thực từ a đến u P[u]:= a ; P u : à ma trận lưu vết đường đi End ; While VS\   do Begin Chọn đỉnh v trong V\S mà D v nhỏ nhất; S:= S {v} ; {thêm v vào S} For mỗi đỉnh u trong V\S do If D[v] + C[v,u] < D[u] then Begin D[u]:= D[v] + C[v,u]; P[u]:= v ; End; End ; End ; Dễ thấy rằng độ phức tạp của thuật toán là On()2 Bài toán 2: Tìm đường đi ngắn nhất giữa mọi cặp đỉnh Để tìm đường đi ngắn nhất giữa mọi cặp đỉnh ta có thể sử dụng thuật toán Dijkstra với các đỉnh được chọn làm nguồn lần lượt là 1, 2, , n. Ngoài ra còn có cách trực tiếp giải quyết vấn đề trên, đó là thuật toán Floyd.  Thuật toán Floyd Tƣ tƣởng - Nếu đỉnh k nằm trên đường đi ngắn nhất từ đỉnh i tới j thì đoạn đường từ i tới k và từ k tới j phải là đường đi ngắn nhất từ i tới k và từ k tới j tương ứng. - Sử dụng ma trận A để lưu độ dài đường đi ngắn nhất giữa mọi cặp đỉnh, Ban đầu ta đặt A[i,j] = C[i,j], tức là ban đầu A chứa độ dài đường đi trực tiếp (không đi qua các đỉnh nào cả). Sau đó thực hiện n lần lặp, sau lần lặp thứ k ma trận A sẽ chứa độ dài 20 đường đi ngắn nhất giữa mọi cặp đỉnh chỉ qua các đỉnh thuộc tập {1, 2, ,k}. Như vậy, sau n lần lặp ta nhận được ma trận A chứa độ dài các đường đi ngắn nhất giữa mọi cặp đỉnh của G. - Ký hiệu Ak là ma trận A sau lần lặp thứ k, tức là Ak[i,j] là độ dài đường đi ngắn nhất từ i đến j chỉ qua các đỉnh thuộc {1, 2, , k}. Ak[i,j] được tính theo công thức: Ak[i,j] = Min{Ak-1[i,j], Ak-1[i,k] + Ak-1[k,j]}. - Trong quá trình lặp ta phải lưu lại vết đường đi tức là các đường đi ngắn nhất đi qua các đỉnh nào. Khi đó ta sẽ sử dụng mảng phụ P[] n n , trong đó P[i,j] lưu đỉnh k nếu đường đi ngắn nhất từ i tới j qua đỉnh k. Ban đầu p[i,j] = 0 với mọi j, j, vì lúc đó đường đi ngắn nhất là đường đi trực tiếp, không qua các đỉnh nào cả. Với các phần tử như trên ta thấy ở bước lặp thứ k thì giá trị của ma trận A ở dòng thứ k và cột thứ k là không thay đổi. Procedure Floyd; Var i, j, k: integer; Begin For i:=1 to n do For j:=1 to n do Begin A[i,j]:= C[i,j];P[i,j]:= 0; End; For k:= 1 to n do For i:=1 to n do For j:=1 to n do If A[i,k] + A[k,j] < A[i,j] then Begin A[i,j]:= A[i,k] + A[k,j];P[i,j]:= k; End; End; Dễ thấy rằng độ phức tạp của thuật toán là On()3 . 1.3.4. Bài toán tô màu đồ thị Bài toán được đặt ra xuất phát từ bài toán tô màu bản đồ như sau: 21 Ta coi mỗi bản đồ là một đồ thị phẳng. Trong một bản đồ ta coi hai miền có chung nhau một đường biên là hai miền kề nhau. ( Hai miền chỉ có chung nhau một điểm biên là hai miền không kề nhau ). Một bản đồ thường được tô màu sao cho hai miền kề nhau được tô hai màu khác nhau. Và bài toán đặt ra là : “ xác định số màu tối thiểu cần có để tô màu một bản đồ sao cho 2 miền kề nhau có màu khác nhau”. Ví dụ: Ta có bản đồ sau Với bản đồ này ta cần 3 màu là đủ ( 2 màu không đủ để có thể tô được theo yêu cầu nói trên ). Mỗi bản đồ trên mặt phẳng có thể biểu diễn bằng một đồ thị, trong đó mỗi miền của bản đồ được biểu diễn bằng một đỉnh, các cạnh nối hai đỉnh nếu các miền được biểu diễn bằng hai đỉnh này là kề nhau. Đồ thị nhận được bằng cách này gọi là đồ thị đối ngẫu của bản đồ đang xét. Thuật toán Welch-Powell về tô màu đồ thị. Để tô màu một đồ thị G, ta có thể sử dụng thuật toán Welch-Powell như sau  Sắp xếp các đỉnh G theo bậc giảm dần.  Dùng một màu để tô đỉnh đầu tiên và cũng dùng màu này để tô màu đỉnh liên tiếp trong danh sách mà không kề với các đỉnh đã tô.  Bắt đầu trở lại danh sách, tô màu thứ hai cho đỉnh chưa đươc tô màu và lập lại quá trình trên cho đến khi tất cả các đỉnh đều được tô màu. Chú ý: Thuật toán Welch-Powell chưa cho ta sắc số của một đồ thị G, nó chỉ giúp ta một cách tiếp cận tìm sắc số của một đồ thị. Để tìm sắc số của một đồ thị thì sau khi tô màu xong ta phải sử dụng các định lý, các tính chất đã học của lý thuyết đồ thị để khẳng định màu được dùng là ít nhất và từ đó suy ra sắc số của đồ thị. Bài toán tìm sắc 22 số của một đồ thị là một bài toán khó và không phải đồ thị nào cũng tìm được sắc số một cách dễ dàng. Bài toán tô màu có nhiều ứng dụng trong thực tế. Chẳng hạn: việc xếp lịch thi cho sinh viên, phân chia tần số phát sóng của các đài phát thanh, truyền hình, bố trí các con vật trong sở thú.... Ví dụ: Hãy lập lịch cho các sinh viên trong một trường đại học sao cho không có sinh viên nào phải thi 02 môn trong cùng một buổi thi. Chẳng hạn, có 7 môn cần xếp lịch thi được đánh số lần lượt từ 1 đến 7 và các cặp môn sau có chung sinh viên dự thị: + 1 và 3, 1 và 4, 1 và 7. + 2 và 3, 2 và 4, 2 và 5, 2 và 7. + 3 và 4, 3 và 7. + 4 và 5, 4và 6. + 5 và 7. + 6 và 7. Giải: Xây dựng đồ thị G = (V,E) mô tả bài toán sau: Mỗi đỉnh vi  V (i = 1...7 ) đại diện cho môn thi thứ i. Mỗi cạnh e  E nối hai đỉnh vi và vj nếu có sinh viên phải thi lại cả hai môn được biểu diễn bằng 2 đỉnh này. Ta có đồ thị G = (V,E) như sau: 23  Để lập lịch thi ta sẽ tiến hành tô m