Đồ án tốt nghiệp Công nghệ thông tin: Xây dựng bài toán ghép đôi không trọng số

Chia sẻ: Vũ Văn Cường | Ngày: | Loại File: DOCX | Số trang:43

Thêm vào BST

Báo xấu

118
lượt xem 17
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Đồ án tốt nghiệp được biên soạn với mục tiêu tìm hiểu về cơ sở lý thuyết về đồ thị và độ phức tạp thuật toán; bài toán tìm bộ ghép cực đại trên đồ thị và các thuật toán; ứng dụng bài toán ghép đôi trong thực tế.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Đồ án tốt nghiệp Công nghệ thông tin: Xây dựng bài toán ghép đôi không trọng số

ĐẠI HỌC KHOA CÔNG NGHỆ THÔNG TIN  ĐỒ ÁN TỐT NGHIỆP ĐẠI HỌC TÊN ĐỀ TÀI XÂY DỰNG BÀI TOÁN GHÉP ĐÔI KHÔNG TRỌNG SỐ Họ và tên: Chuyên nghành: Công nghệ thông tin Lớp: cntt Khoá: 20162020 Hướng dẫn: Tiến sỹ Hà Nội, 12/2020 1
LỜI CAM ĐOAN Em xin cam đoan: Đồ án tốt nghiệp “ Xây dựng bài toán ghép đôi không trọng số “ này là công trình nghiên cứu của cá nhân em, được thực hiện trên cơ sở nghiên cứu lý thuyết và ứng dụng , dưới sự hướng dẫn khoa học của Tiến sĩ Phạm Minh Hoàn , Trường Đại học Kinh tế quốc dân . Em xin chịu trách nhiệm về lời cam đoan này. Hà Nội, ngày 12 tháng 12 năm 2020 Tác giả 2
LỜI CÁM ƠN Để hoàn thành bài nghiên cứu này, em xin chân thành cám ơn Trường Đại học Kinh tế quốc dân, Phòng đào tạo, các thầy, cô giáo giảng dạy lóp Công nghệ thông tin 58B đã quan tâm, tạo điều kiện thuận lợi, tận tình giảng dạy và giúp đỡ em trong thời gian theo học tại trường. Đặc biêt, em xin bày tỏ lòng biết ơn sâu sắc đến TS. Phạm Minh Hoàn, người đã dành nhiều thời gian, tam huyết hướng dẫn em trong suốt quá trình nghiên cứu và hoàn thành đồ án . Mặc dù đã cố gắng hết sức hoàn thiện luận văn, tuy nhiên chắc chắn vẫn còn nhiều thiếu sót, rất mong nhận được sự góp ý quý báu của quý thầy cô và các bạn. Xin trân trọng cám ơn ! Hà Nội, ngày 12 tháng 12 năm 2020 Tác giả 3
MỤC LỤC 4
LỜI NÓI ĐẦU Ngày nay việc giải quyết các bài toán lớn cho hệ thống đòi hỏi sự hợp tác chặt chẽ giữa các chuyên gia trong các lĩnh vực chuyên môn, như các chuyên gia Toán, Toán ứng dụng và các chuyên gia Tin học, kỹ sư lập trình. Việc thiết lập được một mô hình hợp lý, phản ánh đƣợc bản chất của bài toán thực tế đồng thời khả thi về phương diện tính toán luôn là điều đáng được quan tâm. Đặc biệt trong các chuyên ngành liên quan thì toán học là chuyên ngành rất được quan tâm, một trong số đó là Lý thuyết đồ thị. Đồ thị biểu diễn được rất nhiều cấu trúc, nhiều bài toán thực tế có thể được biểu diễn bằng đồ thị. Ví dụ, cấu trúc liên kết của một website có thể được biểu diễn bằng một đồ thị có hướng như sau: các đỉnh là các trang web hiện tại có tại website, tồn taị một cạnh có hướng nối từ trang A tới trang B khi và chỉ khi A có chứa 1 liên kết tới B. Do vậy, sự phát triển của các thuật toán xử l đồ thị là một trong các mối quan tâm chính của khoa học máy tính . Mặc dù Lý thuyết đồ thị đã được khoa học phát triển từ rất lâu nhưng có nhiều ứng dụng hiện đại , đặc biệt là các thuật toán trên đồ thị đã có nhiều ứng dụng trong nhiều lĩnh vực khác nhau như : Mạng máy tính, Lý thuyết mã, Tối ưu hoá, Kinh tế học ...Những ý tưởng cơ bản của lý thuyết đồ thị được nhà toán học Thụy sỹ Leonhard Euler đưa ra từ thế kỷ 18. Ông đã dùng lý thuyết đồ thị để giải quyết bài toán cầu Konigsberg nổi tiếng. Đồ thị cũng được dùng để giải nhiều bài toán thuộc những lĩnh vực rất khác nhau như : người ta có thể dùng đồ thị để biểu diễn sự 5
cạnh tranh của các loài trong môi trường sinh thái, dùng đồ thị biểu diễn ai có ảnh hưởng đến ai trong một tổ chức nào đó và cũng có thể dùng đồ thị để giải các bài toán như bài toán tính số các tổ hợp khác nhau của các chuyến xe giữa hai thành phố trong một mạng giao thông, bài toán đi tham quan tất cả các phố của một thành phố sao cho mỗi phố đi qua đúng một lần, hay bài toán tìm số màu cần thiết để tô các vùng khác nhau của một bản đồ,...Đồ thị với các trọng số được gán cho các cạnh của nó có thể dùng để giải các bài toán như bài toán tìm đường đi ngắn nhất giữa hai thành phố trong một mạng giao thông, bài toán phân công lao động sao cho tổng lợi nhuận thu được là lớn nhất. Đặc biệt, nhiều bài toán trong thực tế sử dụng mô hình đồ thị và các thuật toán trên đồ thị được giải quyết rất hiệu quả như: bài toán điều hành taxi, bài toán xếp lớp học theo tín chỉ có thể đưa về mô hình bài toán tìm bộ ghép cực đại trên đồ thị và sử dụng các thuật toán tương ứng. Chính vì đồ thị có thể được sử dụng để giải quyết nhiều bài toán thuộc nhiều lĩnh vực khác nhau một cách dễ dàng và phổ biến như vậy nên đồ thị giữ một vai trò hết sức quan trọng trong cuộc sống, đặc biệt là trong lĩnh vực công nghệ thông tin, dựa vào đồ thị và các thuật toán trên đồ thị người ta có thể xây dựng nên các phần mềm hữu ích giải các bài toán thực tế một cách nhanh chóng và tối ưu . Nhận thấy tính thiết thực của vấn đề này và được sự gợi ý của giảng viên hướng dẫn, tôi đã chọn nội dung nghiên cứu về ―Bài toán ghép đôi không trọng số trên đồ thị, ứng dụng giải 6
một số bài toán trong thực tế.” làm đề tài cho luận văn tốt nghiệp của mình . Báo cáo được bố cục thành 3 chương: Chương 1: Cơ sở lý thuyết đồ thị và độ phức tạp thuật toán. Chương 2 : Bài toán tìm bộ ghép cực đại trên đồ thị và các thuật toán. Chương 3: Ứng dụng bài toán ghép đôi trong thực tế . 7
CHƯƠNG 1 : CƠ SỞ LÝ THUYẾT VỀ ĐỒ THỊ VÀ ĐỘ PHỨC TẠP THUẬT TOÁN 1.1. Các khái niệm cơ bản 1.1.1. Khái niệm đồ thị Là một cấu trúc rời rạc gồm các đỉnh và các cạnh nối các đỉnh đó. Được mô tả hình thức: G = (V, E) V gọi là tập các đỉnh, E là tập các cạnh, Có thể coi E là tập các cặp (u, v) với u và v là hai đỉnh của V. Một số hình ảnh của đồ thị: 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 và cạnh e này liên thuộc với đỉnh u và đỉnh v. Với một đỉnh v trong đồ thị, ta định nghĩa bậc của v , ký hiệu deg(v) là số cạnh liên thuộc với v. Dễ thấy rằng trên đơn đồ thị thì số cạnh liên thuộc với v cũng là số đỉnh kề với v. Định lý: giả sử G = (V, E) là đồ thị vô hướng với m cạnh, khi đó tổng tất cả các bậc đỉnh trong V sẽ bằng 2m: 8
Đối với đồ thị có hướng G = (V, E). Xét một cung e ϵ E, nếu e = (u, v) thì ta nói 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, ta định nghĩa : Bán bậc ra của v ký hiệu deg+(v) là số cung đi ra khỏi nó; bán bậc vào ký hiệu deg(v) là số cung đi vào đỉnh đó. Định lý: giả sử G = (V, E) là đồ thị có hướng với m cung, khi đó tổng tất cả các bán bậc ra của các đỉnh bằng tổng tất cả các bán bậc vào và bằng m: = m 1.1.2. Các loại đồ thị Có thể phân loại đồ thị theo đặc tính và số lượng của tập các cạnh E: Cho đồ thị G = (V, E). Định nghĩa 1: Một đơn đồ thị vô hƣớng là một bộ G = , trong đó: V ≠ Ø là tập hợp hữu hạn gồm các đỉnh của đồ thị. E là tập hợ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ư vậy, theo định nghĩa trên, trong một đơn đồ thị không thể có các cặp cạnh nối cùng một cặp đỉnh (do E là tập hợp nên không thể có 2 cặp trùng nhau), các cạnh đều không phân biệt thứ tự nên cạnh [u,v] và cạnh [v,u] đều được coi là một cạnh duy nhất, điều này phù hợp với việc biểu diễn các con đường 2 chiều, và hiển nhiên là không có cặp [u,u] nào đó trong E. 9
Ví dụ a) Đơn đồ thị vô hướng b) Không phải đơn đồ c) Không phải đơn đồ thị vô thị vô hướng do có các hướng do có cạnh nối một cặp cạnh nối cùng một đỉnh với chính nó. cặp đỉnh Tuy nhiên, trên thực tế, cũng có thể trong một hệ thống giao thông vẫn tồn tại nhiều con đường đi nối cùng hai địa điểm, hoặc cũng có thể có một con đường để đi từ một địa điểm nào đó rồi lại quay về chính nó (đây có thể là một con đường nội bộ của một trung tâm mua sắm, …). Khi đó, tính chất của đơn đồ thị vô hướng nhất định nghĩa trên không cho phép n biểu diễn được hệ thống giao thông trong trường hợp này. Muốn vậy, ta phải dùng một loại đồ thị tổng quát hơn, đó là: đa đồ thị vô hướng. Định nghĩa 2: Đa đồ thị vô hướng là một bộ G = , trong đó V ≠ Ø là tập hợp hữu hạn gồm các đỉnh của đồ thị. E là một họ các cặp không có thứ tự của V gọi là các cạnh. Lưu ý: Khi ta nói E là một họ nghĩa là nó có thể có những cặp trùng nhau (khác với khái niệm tập hợp). Các cạnh nối cùng một cặp đỉnh được gọi là các cạnh song song. 10
Các cạnh nối từ một đỉnh với chính nó được gọi là khuyên. Ví dụ e1 a) Đa đồ thị vô hướng: e1 và e2 là b) Đa đồ thị vô hướng: e là khuyên các cạnh song song Điểm chung của hai loại đồ thị đã được định nghĩa ở trên là tính chất vô hướng (hai chiều) của các cạnh. Trong thực tế, cũng có khi ta phải chú trọng đến tính có hướng của các cạnh nối này (chẳng hạn như biểu diễn các con đường một chiều). Từ đó, ta có thêm loại đồ thị: Đơn đồ thị có hướng và đa đồ thị có hướng. Về cơ bản, hai loại này cũng tương tự như hai loại mà ta định nghĩa ở trên, chỉ thêm sự khác biệt là tính chất có thứ tự của các cạnh. Định nghĩa 3: Đơn đồ thị có hướng là một bộ G = , trong đó: V ≠ Ø là tập hợp hữu hạn gồm các đỉnh của đồ thị. E là tập hợp 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. a) Đơn đồ thị có b) Không phải đơn đồ thị c) Không phải đơn đồ thị có 11
hướng có hướng do các các cặp hướng do có cung nối một cung nối cùng một cặp đỉnh với chính nó. đỉnh. Định nghĩa 4: Đa đồ thị có hướng là một bộ G = , trong đó V ≠ là tập hợp hữu hạn gồm các đỉnh của đồ thị. E là một họ các cặp cạnh thứ tự của V gọi là các cung. Các cung nối cùng một cặp đỉnh được gọi là các cung song song. Ví dụ e1 e a) Đa đồ thị có hướng: e1 và e2 là các b) Đa đồ thị có hướng: e là cung song song. khuyên . Định nghĩa 5: Một giả đồ thị G = (V, E) gồm một tập các đỉnh V, một tập các cạnh E và một hàm f từ E tới {{u,v} | u,v V}. Một c nh là một khuyên nếu f(e) = {u} với một đỉnh u nào đó. Một số thuật ngữ cơ bản + Cho đồ thị vô hướng G = . 12
Hai đỉnh u và v của đồ thị được gọi là kề nhau nếu (u,v) là một cạnh của đồ thị. 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. Cạnh được nói là nối đỉnh u và v. Đỉnh u và v được gọi là đỉnh đầu của cạnh e. + Cho đồ thị vô hướng G = . Bậc của đỉnh v trong đồ thị, kí hiệu là deg(v), là số cạnh liên thuộc với n. Đỉnh có bậc 0 được gọi là đỉnh cô lập, đỉnh có bậc 1 gọi là đỉnh treo. Ví dụ Cho đồ thị vô hướng G = sau: V = {1, 2, 3, 4, 5, 6} E = {(1,2), (2,3), (1,4), (1,5), (2,5), (4,5), (2,4)} Bậc của các đỉnh: deg(1) = 3 deg(2) = 4 deg(3) = 1 deg(4) = 3 deg(5) = 3 deg(6) = 0 Đỉnh 3 là đỉnh treo Đỉnh 6 là đỉnh cô lập + Cho G = là đồ thị vô hướng. Khi đó ta có tổng số bậc của các đỉnh của đồ thị sẽ bằng hai lần số cạnh của n. Nói cách khác, ta có: ∑deg (v) =2|E| vV 13
Trong đồ thị vô hƣớng, số đỉnh bậc lẻ là một số chẵn. + Cho đồ thị có hướng G = . Hai đỉnh u và v của đồ thị được gọi là kề nhau nếu (u,v) là một cung của đồ thị. Nếu e=(u,v) là cung của đồ thị thì ta nói cung này đi ra khỏi đỉnh u và đi vào đỉnh v. Đỉnh u được gọi là đỉnh đầu của cung e và đỉnh v được gọi là đỉnh cuối của cung e. + Cho đồ thị có hướng G=. Bán bậc ra của đỉnh v trong đồ thị, ký hiệu là deg+(v), là số cạnh đi ra khỏi v. Bán bậc vào của đỉnh v trong đồ thị, ký hiệu là deg (v), là số cạnh vào v. Ví dụ Xét đồ thị có hướng G = sau: Hình 7: Đồ thị có hướng V = {1, 2, 3, 4, 5, 6} E = {(1,2), (2,3), (1,4), (5,1), (5,2), (2,6), (6,3), (4,5), (6,5), (3,4)} Bậc của các đỉnh: Bán bậc ra: deg+(1)=2 deg+(2)=2 deg+(3)=1 deg+(4)=1 deg+(5)=2 deg+(6)=2 14
Bán bậc vào: deg(1)=1 deg(2)=2 deg(3)=2 deg(4)=2 deg(1)=2 deg(1)=1 Tương tự như đồ thị vô hướng, đối với đồ thị có hướng ta cũng có kết quả gần tương tự về bậc của các đỉnh của đồ thị. + Cho G = là đồ thị có hướng. Tổng bán bậc ra của các đỉnh bằng tổng bán bậc vào của các đỉnh và bằng số cạnh của đồ thị. ∑deg+(v)=deg(v)=|E| vV vV + Đồ thị vô hướng G = đượ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 . 1.1.3. Biểu diễn đồ thị trên máy tính Lý thuyết đồ thị được ứng dụng trong rất nhiều lĩnh vực khác nhau. Để sử dụng được đồ thị hiệu quả và nhanh chóng hơn, chúng ta phải biểu diễn và xử lý được đồ thị với máy tính. Cách biểu diễn thông thường bằng hình vẽ và mô tả tập hợp sẽ không phải hợp với cách thức lưu trữ dữ liệu và xử lý trên máy tính. Chúng ta phải tìm một cấu trúc dữ liệu thích hợp để biểu diễn đồ thị trên máy tính. Có nhiều phương pháp khác nhau để biểu diễn đồ thị trên máy tính. Sau đây chúng ta sẽ lần lượt tìm hiểu một số phương pháp thông dụng. 1.1.3.1. Danh sách cạnh 15
Trong trường hợp đồ thị có n đỉnh, m cạnh, ta có thể biểu diễn đồ thị dưới dạng danh sách cạnh, trong cách biểu diễn này, ngƣời ta liệt kê tất cả các cạnh của đồ thị trong một danh sách, mỗi phần tử của danh sách là một cặp (u, v) tương ứng với một cạnh của đồ thị. (Trong trường hợp đồ thị có hướng thì mỗi cặp (u, v) tương ứng với một cung, u là đỉnh đầu và v là đỉnh cuối của cung). Danh sách được lưu trong bộ nhớ dưới dạng mảng hoặc danh sách móc nối. Ví dụ với đồ thị dưới đây: Cài đặt trên mảng: 1 2 3 4 5 (1,3) (2,4) (3,5) (4,1) (5,2) 5 2 nil Ví dụ biểu diễn đồ thị danh sách cạnh Ưu điểm của danh sách cạnh: • Trong trường hợp đồ thị thưa (có số cạnh tương đối nhỏ: chẳng hạn m
• Trong một số trường hợp, ta phải 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. (Thuật toán Kruskal chẳng hạn) Nhược điểm của danh sách cạnh: • Nhược điểm cơ bản của danh sách cạnh là khi ta cần duyệt tất cả các đỉnh kề với đỉnh v nào đó của đồ thị, thì chẳng có cách nào khác là phải duyệt tất cả các cạnh, lọc ra những cạnh có chứa đỉnh v và xét đỉnh còn lại. Điều đó khá tốn thời gian trong trường hợp đồ thị dày (nhiều cạnh). 1.1.3.2. Danh sách kề Sử dụng danh sách liền kề để biểu diễn đồ thị không có cạnh bội. Danh sách này chỉ rõ các đỉnh nối với mỗi đỉnh của đồ thị. Đỉnh Đỉnh liền kề 1 2, 3,4, 5 2 1,3, 4, 5 3 1,2,4 4 1,2,3 5 1,2 Ví dụ biểu diễn đồ thị danh sách liền kề Ưu điểm của danh sách kề: 17
• Đối với danh sách kề, 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, cái tên "danh sách kề" đã cho thấy rõ điều này. 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ề n . Nhược điểm của danh sách kề • Về lý thuyết, so với hai phương pháp biểu diễn trên, danh sách kề tốt hơn hẳn. Chỉ có điều, trong trường hợp cụ thể mà ma trận kề hay danh sách cạnh không thể hiện nhược điểm thì ta nên dùng ma trận kề (hay danh sách cạnh) bởi cài đặt danh sách kề có phần dài dòng hơn. 1.1.3.3. Ma trận liền kề Giả sử G = (V, E) là một đồ thị đơn trong đó |V| = n và các đỉnh được liệt kê tuỳ v1,…,vn. Ma trận liền kề A của G ứng với danh sách các đỉnh này là ma trận không một cấp n*n có phần tử hàng i, cột j bằng 1 nếu vi và vj liền kề nhau, và bằng 0 nếu chúng không được nối với nhau. 1 0 1 1 1 1 2 1 0 1 1 1 1 1 0 1 0 3 4 1 1 1 0 0 5 1 1 0 0 0 1 2 4 5 18
Hình 10: Ví dụ biểu diễn đồ thị ma trận kề Các tính chất của ma trận liền kề: 1. Đối với đồ thị vô hướng G, thì ma trận liền kề tương ứng là ma trận đối xứng (aij = aji), điều này không đúng với đồ thị có hướng. 2. Nếu G là đồ thị vô hướng và A là ma trận liền kề tương ứng thì trên ma trận A: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) 3. Nếu G là đồ thị có hướng và A là ma trận liền kề tương ứng thì trên ma trận A: • Tổng các số trên hàng i = Bán bậc ra của đỉnh i = deg+(i) • Tổng các số trên cột i = Bán bậc vào của đỉnh i = deg(i) Trong trường hợp G là đơn đồ thị, ta có thể biểu diễn ma trận liền kề A tương ứng là các phần tử logic.Aij = TRUE nếu (i, j) E và aij = FALSE nếu (i, j) ∉ E Ưu điểm của ma trận liền kề: • Đơn giản, trực quan, dễ cài đặt trên máy tính • Để kiểm tra xem hai đỉnh (u, v) của đồ thị có kề nhau hay không, ta chỉ việc kiểm tra bằng một phép so sánh: auv ≠ 0. Nhược điểm của ma trận liền kề: • Bất kể số cạnh của đồ thị là nhiều hay ít, ma trận liền kề luôn luôn đòi hỏi n2 ô nhớ để lưu các phần tử ma trận, điều đó gây lãng phí bộ nhớ dẫn tới việc không thể biểu diễn được đồ thị với số đỉnh lớn. 19
Với một đỉnh u bất kỳ của đồ thị, nhiều khi ta phải xét tất cả các đỉnh v khác kề với nó, hoặc xét tất cả các cạnh liên thuộc với n . Trên ma trận liền kề việc đó được thực hiện bằng cách xét tất cả các đỉnh v và kiểm tra điều kiện auv ≠ 0. Như vậy, ngay cả khi đỉnh u là đỉnh cô lập (không kề với đỉnh nào) hoặc đỉnh treo (chỉ kề với 1 đỉnh) ta cũng buộc phải xét tất cả các đỉnh và kiểm tra điều kiện trên dẫn tới lãng phí thời gian. 1.1.3.4. Ma trận liên thuộc Giả sử G = (V, E) là một đồ thị vô hướng, v1, v2, vn là tập các đỉnh còn e1, e2, ..., em là tập các cạnh của nó. Khi đó ma trận liên thuộc theo thứ tự trên của V và E là ma trận M = [mij] trong đ : mij = 1 nếu cạnh ej nối với đỉnh vi mij = 0 nếu cạnh ej không nối với e1 e2 e3 e4 e5 e6 e7 e8 v1 1 0 0 0 1 1 1 0 v2 1 1 1 1 0 0 0 0 v3 0 0 0 1 0 1 0 1 v4 0 0 1 0 0 0 1 1 v5 0 1 0 0 1 0 0 0 Ví dụ biểu diễn đồ thị ma trận liên thuộc 20