Tài liệu Một số vấn đề ứng dụng của lý thuyết đồ thị

Header Page 1 of 128. TRƯỜNG ĐẠI HỌC SƯ PHẠM HÀ NỘI 2 KHOA CÔNG NGHỆ THÔNG TIN ---------***--------- DƯƠNG THỊ LIỄU MỘT SỐ VẤN ĐỀ ỨNG DỤNG CỦA LÝ THUYẾT ĐỒ THỊ KHÓA LUẬN TỐT NGHIỆP ĐẠI HỌC Chuyên ngành: Tin học HÀ NỘI - 2013 luan van thac si - luan van kinh te - khoa luan - tai lieu -Footer Page 1 of 128. Header Page 2 of 128. LỜI CẢM ƠN Trong suốt quá trình học tập và làm khóa luận, em nhận được sự giúp đỡ, tạo điều kiện của các thầy, cô giáo khoa Công nghệ Thông tin. Bên cạnh đó là sự giúp đỡ rất nhiều của người thân, bạn bè để em có được kết quả ngày hôm nay. Trước hết em xin tỏ lòng kính trọng cảm ơn thầy giáo TS.Trịnh Đình Vinh, thầy đã tận tình chỉ bảo, hướng dẫn cho em hoàn thành được bản khóa luận này. Xin cảm ơn các thầy, cô giáo trong khoa Công nghệ Thông tin – trường Đại học sư phạm Hà Nội 2, các bạn trong lớp K35 – Tin học đã tận tình giúp đỡ, giới thiệu tài liệu, sách tham khảo để khóa luận được hoàn thành đúng thời hạn. Cuối cùng là lòng biết ơn đến sự quan tâm, chăm sóc và tạo điều kiện của gia đình để con tập trung vào việc học tập và hoàn thành bản khóa luận này. Do thời gian thực hiện không nhiều nên khóa luận không tránh khỏi những thiếu sót. Rất mong nhận được sự đóng góp của thầy cô giáo và các bạn để khóa luận được hoàn thiện hơn. Em xin chân thành cảm ơn! Hà Nội, tháng 05 năm 2013 Sinh viên DƯƠNG THỊ LIỄU luan van thac si - luan van kinh te - khoa luan - tai lieu -Footer Page 2 of 128. Header Page 3 of 128. LỜI CAM ĐOAN Tên em là: DƯƠNG THỊ LIỄU Sinh viên lớp: K35 – Tin học, khoa Công nghệ thông tin, trường Đại học sư phạm Hà Nội 2. Em xin cam đoan: 1. Đề tài: “Một số vấn đề ứng dụng của lý thuyết đồ thị” là sự nghiên cứu của riêng em, dưới sự hướng dẫn của thầy giáo TS. Trịnh Đình Vinh. 2. Khóa luận hoàn toàn không sao chép của tác giả nào khác. Nếu sai em xin hoàn toàn chịu trách nhiệm. Hà Nội, tháng 05 năm 2013 Người cam đoan DƯƠNG THỊ LIỄU luan van thac si - luan van kinh te - khoa luan - tai lieu -Footer Page 3 of 128. Header Page 4 of 128. MỤC LỤC LỜI CẢM ƠN LỜI CAM ĐOAN DANH MỤC HÌNH VẼ DANH MỤC BẢNG MỞ ĐẦU ..................................................................................................... 1 Chương 1: LÝ THUYẾT ĐỒ THỊ ................................................................ 5 1.1. Đồ thị .................................................................................................. 5 1.1.1. Định nghĩa đồ thị ......................................................................... 5 1.1.2. Đồ thị đơn ................................................................................... 6 1.1.3. Đa đồ thị ...................................................................................... 6 1.1.4. Giả đồ thị..................................................................................... 6 1.2. Các loại đồ thị ...................................................................................... 7 1.2.1. Đồ thị vô hướng........................................................................... 7 1.2.2. Đồ thị có hướng ........................................................................... 7 1.2.3. Đồ thị hỗn hợp............................................................................. 7 1.3. Một số khái niệm.................................................................................. 7 1.3.1. Cạnh liên thuộc, đỉnh kề, bậc....................................................... 7 1.3.2. Đường đi và chu trình .................................................................. 8 1.3.3. Đồ thị liên thông .......................................................................... 8 1.4. Biểu diễn đồ thị trên máy tính ............................................................ 10 1.4.1. Biểu diễn bằng ma trận kề ......................................................... 10 1.4.2. Danh sách cạnh (cung) .............................................................. 12 1.4.3. Danh sách kề ............................................................................. 13 1.5. Các ứng dụng của lý thuyết đồ thị ...................................................... 14 Chương 2: CHU TRÌNH, ĐƯỜNG ĐI ....................................................... 15 2.1. Chu trình Euler và chu trình Hamilton................................................ 15 2.1.1. Chu trình Euler .......................................................................... 15 luan van thac si - luan van kinh te - khoa luan - tai lieu -Footer Page 4 of 128. Header Page 5 of 128. 2.1.2. Chu trình Hamilton .................................................................... 18 2.2. Tìm kiếm đường đi trên đồ thị ............................................................ 19 2.2.1. Thuật toán tìm kiếm theo chiều sâu (Depth First Seach) ............ 19 2.2.2. Thuật toán tìm kiếm theo chiều rộng (Breadth First Search) ...... 21 2.2.3. Độ phức tạp tính toán của DFS và BFS ..................................... 23 2.3. Đường đi ngắn nhất trong đồ thị có trọng số....................................... 24 2.3.1. Bài toán đường đi ngắn nhất ...................................................... 24 2.3.2. Các thuật toán ............................................................................ 24 2.3.3. Các ứng dụng ............................................................................ 29 Chương 3: MỘT SỐ VẤN ĐỀ VỀ CÂY .................................................... 36 3.1. Các khái niệm và tính chất cơ bản ...................................................... 36 3.1.1. Các khái niệm cơ bản ................................................................ 36 3.1.2. Cây m – phân ............................................................................ 37 3.2. Các ứng dụng ..................................................................................... 37 3.2.1. Mã tiền tố .................................................................................. 37 3.2.3. Cây biểu diễn biểu thức ............................................................. 40 3.2.4. Cây quyết định .......................................................................... 41 3.2.5. Cây sắp xếp và tìm kiếm............................................................ 41 Chương 4: XÂY DỰNG CHƯƠNG TRÌNH ỨNG DỤNG ........................ 47 4.1. Phát biểu bài toán ............................................................................... 47 4.2. Giải quyết bài toán ............................................................................. 47 4.2.1. Giải thuật tổng quát ................................................................... 47 4.2.2. Kết hợp “Stack” và “Queue” ..................................................... 48 4.2.3. Cài đặt lớp Cell.......................................................................... 49 4.2.4. Hiệu ứng Backtracking trong DFS ............................................. 50 KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN .................................................. 52 TÀI LIỆU THAM KHẢO .......................................................................... 54 luan van thac si - luan van kinh te - khoa luan - tai lieu -Footer Page 5 of 128. Header Page 6 of 128. DANH MỤC HÌNH VẼ Hình 1.1: Đồ thị ............................................................................................. 5 Hình 1.2: Ví dụ về một đồ thị ........................................................................ 6 Hình 1.3: a. Đa đồ thị b. Giả đồ thị ............................................................ 6 Hình 1.4: Đồ thị liên thông ............................................................................ 9 Hình 1.5: Các loại đồ thị liên thông ............................................................... 9 Hình 1.6: Đồ thịbiểu diễn ma trận kề ........................................................... 10 Hình 1.7: Đồ thị danh sách cạnh (cung) ....................................................... 12 Hình 1.7a: Danh sách kề của đồ thị G1 ......................................................... 13 Hình 1.7b: Danh sách kề của đồ thị G2 ......................................................... 13 Hình 2.1: Mô hình đồ thị của bài toán 7 cái cầu ........................................... 15 Hình 2.2: Chu trình Euler vô hướng ............................................................ 16 Hình 2.3: Chu trình Euler vô hướng sau khi đi từ 1 đến 4............................. 17 Hình 2.4: Chu trình Hamilton ...................................................................... 18 Hình 2.5: Cây DFS ...................................................................................... 20 Hình 2.6: Cây BFS ...................................................................................... 22 Hình 2.7: Sự chuyển đổi trạng thái ............................................................... 30 Hình 2.8: Sơ đồ lưới của giải thuật Viterbi ................................................... 31 Hình 2.9: Sơ đồ PERT ................................................................................. 34 Hình 3.1: Cây .............................................................................................. 36 Hình 3.2: Mã tiền tố .................................................................................... 38 Hình 3.3: Cây biểu diễn nhị phân ................................................................ 39 Hình 3.4: Cây biểu diễn biểu thức ............................................................... 40 Hình 3.5: Cây quyết định ............................................................................. 41 Hình 3.6: Cây nhị phân tìm kiếm ................................................................. 42 Hình 3.7: Cây nhị phân đầy đủ .................................................................... 43 Hình 3.8: Câp sắp xếp hòa nhập .................................................................. 44 Hình 3.9: Cây sắp xếp nhanh ...................................................................... 46 Hình 4.1: Giao diện chương trình ................................................................ 50 luan van thac si - luan van kinh te - khoa luan - tai lieu -Footer Page 6 of 128. Header Page 7 of 128. DANH MỤC BẢNG Bảng 1: Thuật toán DFS .............................................................................. 20 Bảng 2: Thuật toán BFS .............................................................................. 23 Bảng 3: Các công viêc ................................................................................. 34 Bảng 4: Mã Huffman ................................................................................... 39 luan van thac si - luan van kinh te - khoa luan - tai lieu -Footer Page 7 of 128. Header Page 8 of 128. MỞ ĐẦU 1. Lý do chọn đề tài Lý thuyết đồ thị là một lĩnh vực nghiên cứu đã có từ lâu đời và có nhiều ứng dụng hiện đại. Những tư tưởng cơ bản của lý thuyết đồ thị được đề xuất từ những năm đầu của thế kỷ 18 bởi một nhà toán học lỗi lạc người Thụy Sĩ Leonhard Euler. Chính ông là người đã sử dụng đồ thị để giải bài toán nổi tiếng về các cái cầu ở thành phố Konigsberg. Đồ thị được sử dụng để giải quyết các bài toán trong nhiều lĩnh vực khác nhau. Chẳng hạn, đồ thị có thể sử dụng để xác định các mạch vòng trong vấn đề giải tích mạch điện. Đồ thị có thể phân biệt các hợp chất hóa học hữu cơ khác nhau với cùng công thức phân tử nhưng khác nhau về cấu trúc phân tử hay xác định xem hai máy tính trong mạng có thể trao đổi thông tin được với nhau hay không. Đồ thị có trọng số trên các cạnh có thể sử dụng để giải các bài toán như: tìm đường đi ngắn nhất giữa hai thành phố trong cùng một mạng giao thông. Đồ thị còn được sử dụng để giải các bài toán về lập lịch, thời khóa biểu và phân bố tần số cho các trạm phát thanh truyền hình... Do đó việc nghiên cứu lý thuyết đồ thị này mang lại nhiều ý nghĩa thực tiễn nhất định. Xuất phát từ tính thực tiễn đó em xin chọn đề tài: “Một số vấn đề ứng dụng của lý thuyết đồ thị”. 2. Mục đích chọn đề tài Mục đích nghiên cứu của đề tài này là tìm hiểu, khảo sát thực nghiệm và ứng dụng của lý thuyết đồ thị trong các ngành kỹ thuật. Dựa trên lý thuyết đồ thị, một số bài toán như kiểm tra tính liên thông, tìm đường đi ngắn nhất, khắc phục những gói tin bị truyền sai nhờ các giải thuật của đồ thị và xây dựng chương trình minh họa. 1 luan van thac si - luan van kinh te - khoa luan - tai lieu -Footer Page 8 of 128. Header Page 9 of 128. 3. Nhiệm vụ, yêu cầu Đề tài của khóa luận: “Một số vấn đề ứng dụng của lý thuyết đồ thị” được đặt ra với nhiệm vụ, yêu cầu:  Nghiên cứu các khái niệm cơ bản nhất của đồ thị, phương pháp biểu diễn đồ thị trên máy tính.  Tìm hiểu các thuật toán tìm đường đi trên đồ thị.  Nghiên cứu các ứng dụng của lý thuyết đồ thị.  Tìm hiểu các khái niệm, tính chất cơ bản của cây và các ứng dụng của nó.  Cài đặt chương trình minh họa ứng dụng của lý thuyết đồ thị. 4. Phương pháp nghiên cứu  Nghiên cứu qua việc đọc sách, báo và các tài liệu liên quan nhằm xây dựng cơ sở lý thuyết của đề tài và các biện pháp cần thiết để giải quyết các vấn đề của đề tài.  Tham khảo các ý kiến của các chuyên gia để có thể thiết kế chương trình phù hợp với thực tiễn.  Thông qua quan sát thực tế, yêu cầu cơ sở của lý luận được nghiên cứu và các kết quả đạt được qua những phương pháp trên. 5. Ý nghĩa khoa học và thực tiễn của đề tài Đề tài giới thiệu hướng nghiên cứu và ứng dụng của lý thuyết đồ thị vào thực tế cuộc sống, một lĩnh vực vẫn còn khá mới ở Việt Nam. Đề tài cũng hướng đến việc đơn giản hóa việc tìm đường đi trên đồ thị. Thuật toán tìm đường đi là một thuật toán quan trọng và có ý nghĩa to lớn trong thực tế như tìm lộ trình di chuyển cho bất kỳ đối tượng di động nào như người, xe máy, ô tô... Nó mang lại nhiều tiện ích và hiệu quả cho người sử dụng, đặc biệt là hiệu quả về kinh tế, tiết kiệm thời gian, công sức... trong việc lựa chọn đường đi cho hợp lý. 2 luan van thac si - luan van kinh te - khoa luan - tai lieu -Footer Page 9 of 128. Header Page 10 of 128. 6. Cấu trúc của khóa luận Ngoài các phần mở đầu và kết luận khóa luận còn bao gồm các chương: Chương 1: Lý thuyết đồ 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òn trình bày đến một vấn đề quan trọng, đó là cách biểu diễn đồ thị trên máy tính. Chương 2: Chu trình, đường đi Chương này trình bày những khái niệm về chu trình, đường Euler và chu trình, đường đi Hamilton. Tìm hiểu các thuật toán tìm kiếm đường đi trên đồ thị và các ứng dụng trong truyền tin, trong việc lập lịch công. Chương 3: Một số vấn đề về cây Trong chương này đề 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ó.Một số ứng dụng của cây nhị phân như mã tiền tố, mã Huffman, 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. Chương 4: Xây dựng chương trình ứng dụng Đây là chương cuối cùng, chương này sẽ giới thiệu về bài toán tìm đường đi thoát khỏi mê cung. Sử dụng thuật toán Breadth First Seach (BFS – Tìm kiếm theo chiều rộng) và Depth First Seach (DFS – Tìm kiếm theo chiều sâu) để tìm đường đi giữa hai điểm trong một mê cung. 7. Kết quả đạt được Khóa luận đã nghiên cứu được các khái niệm cơ bản nhất của đồ thị, các thuật toán tìm đường đi trên đồ thị, ứng dụng của lý thuyết đồ thị và cáckhái niệm, tính chất cơ bản của cây. Khóa luận đã xây dựng được chương trình tìm đường đi thoát khỏi mê cung bằng thuật toán tìm kiếm theo chiều sâu và tìm kiếm theo chiều rộng. Tuy nhiên chương trình mới chỉ mang tính chất mô phỏng chưa có được ứng 3 luan van thac si - luan van kinh te - khoa luan - tai lieu -Footer Page 10 of 128. Header Page 11 of 128. dụng thực tế. Hướng phát triển chương trình trong tương lai thành bài toán tìm đường đi cho người đưa thư, lập trình đường đi cho xe bus... 4 luan van thac si - luan van kinh te - khoa luan - tai lieu -Footer Page 11 of 128. Header Page 12 of 128. Chương 1: LÝ THUYẾT ĐỒ THỊ 1.1. Đồ thị 1.1.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 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ử X là tập hữu hạn, không rỗng và U  X  X. Bộ G  được gọi là đồ thị đơn nếu giữa hai đỉnh bất kỳ được nối với nhau bởi không quá một cạnh (cung), tức là đồ thị không có cạnh bội, không có khuyên. 1.1.3. Đa đồ thị Đồ thị G  X, U> được gọi là đa đồ thị nếu nó có ít nhất một cặp đỉnh được nối với nhau bởi hai cạnh (hai cung) trở lên. 1.1.4. Giả đồ thị Là đồ thị có ít nhất một khuyên, có thể chứa cạnh bội, cạnh đơn. Tóm lại đây là loại đồ thị tổng quát nhất. A B A B C D D a) Hình 1.3: a. Đa đồ thị C b) b.Giả đồ thị 6 luan van thac si - luan van kinh te - khoa luan - tai lieu -Footer Page 13 of 128. Header Page 14 of 128. 1.2. Các loại đồ thị 1.2.1. Đồ thị vô hướng Đồ thị G  gọi là đồ thị có hướng nếu tất cả các cạnh e  U mà cặp đỉnh thuộc nó e  (x, y) X có phân biệt thứ tự. Đồ thị có hướng là đồ thị mà mọi e  (x, y) X đều là cung. 1.2.3. Đồ thị hỗn hợp Đồ thị G= vừa có cạnh vô hướng, vừa có cạnh có hướng thì nó được gọi là đồ thị hỗn hợp, loại đồ thị này rất ít khi được dùng tới. Chú ý rằng vấn đề phân chia đồ thị và các thuật ngữ về đồ thị chỉ mang tính tương đối, hiện nay vẫn còn chưa mang tính thống nhất chuẩn trên nhiều tài liệu. 1.3. Một số khái niệm Như trên định nghĩa đồ thị G = (V, E) là một cấu trúc rời rạc, tức là các tập V và E hoặc là tập hữu hạn, hoặc là tập đếm được, có nghĩa là có thể đánh số thứ tự 1, 2, 3… cho các phần tử của tập V và E. Hơn nữa, đứng trên phương diện người lập trình cho máy tính thì chỉ quan tâm đến các đồ thị hữu hạn (V và E là tập hữu hạn) mà thôi. 1.3.1. Cạnh liên thuộc, đỉnh kề, bậc Đối với đồ thị vô hướng G = (V, E). Xét một cạnh e  E, nếu e = (u, v) thì ta nói hai đỉnh u và v là kề nhau (adjacent), cạnh e này liên thuộc (incident) với đỉnh u và v. Với một đỉnh v trong đồ thị, định nghĩa bậc (degree) của v, ký hiệu deg(v) là số cạnh liên thuộc với v. Có thể thấy rằng trên đơn đồ thị thì số cạnh 7 luan van thac si - luan van kinh te - khoa luan - tai lieu -Footer Page 14 of 128. Header Page 15 of 128. liên thuộc với v cũng là số đỉnh kề với v. Đối với đồ thị có hướng G = (V, E). Xét một cung e  E, nếu e = (u, v) thì sẽ có u nối tới v và v nối từ u, cung e là đi ra khỏi đỉnh u và đi vào đỉnh v. Đỉnh u khi đó được gọi là đỉnh đầu, đỉnh v được gọi là đỉnh cuối của cung e. Với mỗi đỉnh v trong đồ thị có hướng, định nghĩa: Bán bậc ra (out – degree) của v ký hiệu deg+(v) là số cung đi ra khỏi nó; bán bậc vào (in – degree), ký hiệu deg-(v) là số cung đi vào đỉnh đó. 1.3.2. Đường đi và chu trình Đường đi: Một đường đi với độ dài k từ đỉnh u đến đỉnh v là dãy (u = x0, x1,…, vk = v) thỏa mãn (xi, xi+1)  E (là một cạnh của đồ thị) vớii: (1≤ i ≤ k). Đỉnh u gọi là đỉnh xuất phát, v gọi là đỉnh kết thúc của đường đi. Đường đi không có cạnh nào đi qua hơn một lần gọi là đường đi đơn. Chu trình: Đường đi có đỉnh xuất phát trùng với đỉnh kết thúc gọi là chu trình. Tương tự có khái niệm chu trình đơn. 1.3.3. Đồ thị liên thông Cho đồ thị G = . Hai đỉnh phân biệt x, y  X được gọi là liên thông nếu tồn tại một đường đi nối các đỉnh x, y với nhau. Đồ thị G được gọi là liên thông nếu với hai đỉnh phân biệt bất kỳ trong đồ thị đều là liên thông. Xét 2 đồ thị liên thông G1 = và G2 = Trong đó: X1X2 =  và U1U2 =  Khi đó: X = X1X2 U = U1U2 Thì G = là đồ thị có 2 thành phần liên thông G1, G2. 8 luan van thac si - luan van kinh te - khoa luan - tai lieu -Footer Page 15 of 128. Header Page 16 of 128. A D B E F C Hình 1.4: Đồ thị liên thông Ví dụ như đồ thị trong hình 1.4 có ba thành phần liên thông sau: G1 = với X1= {A,B,C} và U1 = {AB, AC, CB} G2 = với X2= {D, E} và U2 = {DE} G3 = với X3= {F} và U3 =  Cho đồ thị có hướng G =  G được gọi là đồ thị liên thông yếu nếu đồ thị vô hướng tương ứng với nó là liên thông.  G là liên thông một chiều nếu với hai đỉnh x, y khác nhau bất kỳ của G luôn có đường đi x – y hoặc đường đi y – x.  G là liên thông mạnh (liên thông hai chiều) nếu hai đỉnh x, y khác nhau bất kỳ của G đều có đường đi x – y và đường đi y – x. A B A B A B D D D C C C H1 H2 H3 Hình 1.5: Các loại đồ thị liên thông Ở hình 1.5 đồ thị H1 là liên thông mạnh, giả sử cặp đỉnh (A, C) có chiều đi từC tới A, đồng thời cũng có chiều đi từ A tới C và bất kỳ các cặp đỉnh khác cũng tương tự như vậy. Đồ thị H2 là liên thông một chiều đi từ D tới A. Đồ thị H3 là liênthông yếu vì tồn tại cặp đỉnh (B, C) không có chiều đi B –C và cũng khôngcó chiều đi C – B, nhưng đồ thị vô hướng tương ứng là liên thông. 9 luan van thac si - luan van kinh te - khoa luan - tai lieu -Footer Page 16 of 128. Header Page 17 of 128. 1.4. Biểu diễn đồ thị trên máy tính Lĩnh vực đồ thị có nhiều ứng dụng trong thực tế, có thể mô hình nhiều ứng dụng bằng đồ thị và sử dụng máy tính để giải quyết các bài toán về ứng dụng đó. Nên việc biểu diễn và lưu trữ đồ thị trên máy tính là một vấn đề khá trọng tâm,phương thức biểu diễn từng loại đồ thị trên máy tính ảnh hưởng đến các giảithuật, phương pháp giải quyết các ứng dụng trên máy tính. 1.4.1. Biểu diễn bằng ma trận kề Phương pháp này dựa trên mối quan hệ giữa các cặp đỉnh, mỗi đồ thịđược đặt tương ứng với một ma trận vuông cấp n (n là số đỉnh của đồthị). Gọi ma trận kề là A = (aij) i, j = 1… n.  Trường hợp G = là đồ thị vô hướng với X = {x1, x2, …, xn} khi đó mỗi phần tử aij của ma trận A xác định như sau: aij = aji = d, nếu cặp đỉnh (xi, xj) có d cạnh nối với nhau. Khi cặp đỉnh không có cạnh nào nối với nhau thì aij = 0. Khi đó ma trận kề của đồ thị vô hướng là ma trận đối xứng.  Trường hợp G = là đồ thị có hướng với X ={x1, x2, …, xn} thì mỗi phần tử aij của A được xác định như sau: đối với mỗi cặp đỉnh (xi, xj) từ xi đến xj nếu có d cung thì aij = d. Chú ý aij = 0 nếu không có cung nào hướng từ xi đến xj đến. Ma trận kề trong trường hợp này là không đối xứng. Trong 2 trường hợp trên, chú ý nếu đỉnh x có một khuyên thì phần tử tương ứng của ma trận kề là aij = 1. A B C A B C D D G1 G2 Hình 1.6: Đồ thịbiểu diễn ma trận kề Ta có thể dùng ma trận kề biểu diễn đồ thị G1 và G2 trong hình 1.6 như sau: 10 luan van thac si - luan van kinh te - khoa luan - tai lieu -Footer Page 17 of 128. Header Page 18 of 128. Đối với đồ thị có trọng số mỗi cạnh e = (xi, xj) được gán một trọng số l(e), còn viết là l(xi, xj) thì ma trận kề của nó được thay bằng ma trận có trọng số, 1  1 MG1   1  0 1 0 2 1 1 2 0 0 0  1 0  0 0 1 1    MG2   0 1 0 1 1 0    Khi đó mỗi phần tử của ma trận bằng trọng số của cạnh tương ứng: aij = l(xi, xj). Ưu điểm của phương pháp này là dễ dàng xác định được các cặp đỉnh có kề nhau hay không hoặc rất thuận tiện khi tìm số bậc của mỗi đỉnh. Việc truy cập phần tử của ma trận kề qua chỉ số không phụ thuộc vào số đỉnh của đồ thị. Nhược điểm lớn nhất của phương pháp này là không phụ thuộc vào số cạnh của đồ thị, luôn phải sử dụng n2 đơn vị bộ nhớ để lưu trữ ma trận kề của nó. Định lý: Nếu G = là đa đồ thị với A = (aij) là ma trận kề tương ứng, thì số đường đi khác nhau từ đỉnh xi đến đỉnh xj có độ dài s bằng phần tử Pij của ma trận tích A  A  ...  A  As  ( Pij ) s lần Ví dụ: Trong một số hệ thống thông tin khi được mô hình bằng đồ thị có thể thực hiện tốt một số công tác kiểm kỹ thuật. Ví dụ khi biểu diễn một mạng máy tính bằng đồ thị, giả sử có hai máy nào đó mà thông tin truyền giữa chúng là quan trọng, cần tiến hành kiểm tra xem đã có đường truyền dự phòng giữa chúng không. Xét ở góc độ đồ thị thì cần kiểm tra xem số đường đi giữa cặp đỉnh tương ứng với hai máy đó, nếu có số đường đi lớn hơn một là đã có đường truyền dự phòng. 11 luan van thac si - luan van kinh te - khoa luan - tai lieu -Footer Page 18 of 128. Header Page 19 of 128. 1.4.2. Danh sách cạnh (cung) Cho đồ thị G = với số cạnh m, số đỉnh n. Nếu m < 6n thì G thường được biểu diễn dưới dạng danh sách cạnh (cung). Theo cách này danh sách tất cả các cạnh (cung) của đồ thị vô hướng (có hướng). Mỗi cạnh (cung) e = (x, y) của đồ thị tương ứng với hai biến Dau[e], Cuoi[e]. 2 1 4 2 1 3 3 G1 4 G2 Hình 1.7: Đồ thị danh sách cạnh (cung) Ví dụ: Hình 1.7 đồ thị G1 và G2 được biểu diễn bằng danh sách cạnh (cung) như sau: Dau Cuoi Dau Cuoi 1 2 1 2 1 3 2 3 2 3 3 1 2 4 4 1 3 4 4 2 Danh sách cạnh (cung) G1 Danh sách cạnh (cung) G2 Ưu điểm của danh sách cạnh là tiết kiệm được không gian lưu trữ bởi nó chỉ cần sử dụng 2m ô nhớ để lưu danh sách cạnh.Trong một số trường hợp, nếu xét tất cả các cạnh của đồ thị thì cài đặt trên danh sách cạnh làm cho việc duyệt các cạnh dễ dàng hơn. Nhược điểm của phương pháp này là khi xác định những đỉnh nào của đồ thị là kề với một đỉnh cho trước, sẽ phải làm cỡ m phép so sánh, điều đó khá tốn thời gian trong trường hợp đồ thị dày (nhiều cạnh). 12 luan van thac si - luan van kinh te - khoa luan - tai lieu -Footer Page 19 of 128. Header Page 20 of 128. 1.4.3. Danh sách kề Phương pháp biểu diễn bằng danh sách kề cũng được sử dụng khá phổ biến và thường hay dùng cho đồ thị có hướng. Danh sách kề cho đỉnh xi là danh sách gồm tất cả các đỉnh kề của xi theo thứ tự các đỉnh trong tập đỉnh X. Có thể biểu diễn đồ thị như một mảng FIRST, với phần tử FIRST[i] là con trỏ trỏ tới danh sách kề cho đỉnh xi. Ví dụ: Ở hình 1.7 đồ thị G1 và G2 được biểu diễn bằng danh sách kề như sau: FIRST 1 2 3 2 1 3 4 Nil 1 2 4 Nil 2 3 3 4 Nil Nil Hình 1.7a: Danh sách kề của đồ thị G1 FIRST 1 2 2 Nil 3 Nil 1 Nil 3 4 3 Nil 2 Hình 1.7b: Danh sách kề của đồ thị G2 Bộ nhớ sử dụng cho phương pháp biểu diễn danh sách kề là tỷ lệ thuận với tổng số đỉnh và các cạnh của đồ thị. Danh sách kề có ưu và nhược điểm:  Ưu điểm của danh sách kề là đối với việc duyệt tất cả các đỉnh kề với một đỉnh v cho trước là hết sức dễ dàng. Việc duyệt tất cả các cạnh cũng đơn giản vì một cạnh thực ra là nối một đỉnh với một đỉnh khác kề với nó. 13 luan van thac si - luan van kinh te - khoa luan - tai lieu -Footer Page 20 of 128.