Một Số Bài Toán Tối ưu Rời Rạc Trong Lý Thuyết đồ Thị - Tài Liệu Text

Tải bản đầy đủ (.docx) (57 trang)

1. Trang chủ
>>
2. Tài Chính - Ngân Hàng
>>
3. Kế toán - Kiểm toán

Một số bài toán tối ưu rời rạc trong lý thuyết đồ thị

Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (1.11 MB, 57 trang )

1MỤC LỤCTrang2LỜI CẢM ƠNEm xin chân thành cảm ơn Ban Giám hiệu, Phòng Đào tạo Sau Đạihọc, Khoa Công nghệ Thông tin Trường Đại học công nghệ thông tin vàtruyền thông Thái Nguyên đã tận tình giúp đỡ, tạo mọi điều kiện thuận lợi choem trong quá trình học tập, nghiên cứu và thực hiện luận văn.Đặc biệt, em xin gửi lời tri ân sâu sắc đến GS. TS Đặng Quang Á –người đã dành nhiều thời gian, công sức và tận tình hướng dẫn khoa học choem trong suốt quá trình hình thành và hoàn chỉnh luận văn.Xin chân thành cảm ơn Quý Thầy, Cô đã giảng dạy, truyền đạt cho emnhững tri thức quý báu, thiết thực trong suốt khóa học.Cuối cùng xin bày tỏ lòng biết ơn đối với gia đình, người thân, bạn bè,đồng nghiệp đã giúp đỡ, động viên, đóng góp ý kiến quý báu cho em trongviệc hoàn thành luận văn này.Thái Nguyên, ngàythángnăm 2014Tác giảNguyễn Anh Văn3LỜI CAM ĐOANTôi xin cam đoan đây là công trình nghiên cứu của riêng tôi dưới sựhướng dẫn trực tiếp của GS.TS. Đặng Quang Á.Mọi trích dẫn sử dụng trong báo cáo này đều được ghi rõ nguồn tài liệutham khảo theo đúng qui định.Mọi sao chép không hợp lệ, vi phạm quy chế đào tạo, hay gian trá, tôixin chịu hoàn toàn trách nhiệm.Thái Nguyên, ngàythángTác giảNguyễn Anh Vănnăm 20144DANH MỤC CÁC KÝ HIỆU VÀ CHỮ VIẾT TẮTKý hiêuTừ viết tắtVTập đỉnh của đồ thịETập cạnh của đồ thịG=(V,E)Đồ thị G với tập đỉnh V, tập cạnh EG=(V,E,A)Đồ thị G với tập đỉnh V, tập cạnh E, tập cung Ae = (u,v)e là cạnh đồ thị, u,v là đỉnhdeg(v)Bậc của đỉnh vdeg-(v), deg+(v)Bán bậc vào, bán bậc ra đỉnh vPPolynomialNPNondeterministic PolynomialNP-CNondeterministic Polynomial-CompleteNP-HardNondeterministic Polynomial-HardNTMNondeterministic Turing MachineDTMDeterministic Turing MachinesDiễn giải5DANH MỤC BẢNGTrangBảng 1.1 Liệt kê tất cả các đỉnh kề với mỗi đỉnh của đồ thịBảng 1.2. Biểu diễn đồ thị có hướng trên hình 1.10.Bảng 2.1: Sắp xếp các cạnh theo thứ tự trọng số tăng dần1212236DANH MỤC HÌNHTrangHình 1.: Đồ thị vô hướngHình 1.2: Đồ thị có hướngHình 1.3: Đa đồ thịHình 1.4: Đồ thị hỗn hợpHình 1.5. Đồ thị có hướngHình 1.6. Đường đi trên đồ thị vô hướngHình 1.7. Đường đi trên đồ thị có hướngHình 1.8. Đồ thị liên thông G và đồ thị H gồm 3 thành phần liên thôngH1, H2, H3Hình 1.9. Đơn đồ thịHình 1.10. Đồ thị có hướngHình 1.11. Đơn đồ thịHình 1.12. Giả đồ thịHình 1.13. Đồ thị vô hướngHình 1.14. Mô hình phân lớp các bài toánHình 2.1. Đồ thị có trọng số biểu thị tiền thuê bao hàng tháng đườngtruyền thông trong mạng máy tínhHình 2.2. Đồ thị có trọng số GHình 2.3. Đơn đồ thị có trọng sốHình 2.4. Dùng thuật toán Dijsktra tìm đường đi ngắn nhất từ đỉnh a tớiđỉnh zHình 2.5. Đồ thị vô hướngHình 2.6. Đơn đồ thịHình 2.7. Hai bản đồHình 2.8. Các đồ thị đối ngẫu của các bản đồ trên hình 2.7Hình 2.9. Đồ thị đơn G và HHình 2.10. Đồ thị G và H đã được tô màuHình 2.11. Tô màu đồ thị vô hướngHình 3.1. Bảng danh sách các môn thiHình 3.2. Đồ thị biểu diễn các môn thiHình 3.3. Đồ thị các môn thi đã được lên lịchHình 3.4. Mẫu quản lý bậc họcHình 3.5. Mẫu quản lý phòng thực hànhHình 3.6. Mẫu quản lý giờ thiHình 3.7. Mẫu chọn nhóm cho các môn thiHình 3.8. Mẫu chọn phòng thực hànhHình 3.9. Mẫu xếp lịch thi45567891011111213141519202225303235363738394041444553535454555656577Hình 3.10. Mẫu đăng kí tài khoảnHình 3.11. Mẫu đăng nhập hệ thốngHình 3.12. Mẫu đổi mật khẩu578MỞ ĐẦU1. Lý do chọn đề tàiTrong vài trăm năm qua con người đã đạt được nhiều thành tựu khoa học,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ểntoá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úccó 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ị, logic 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óiriê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ànhphần quan trọng trong học vấn đối với sinh viên các ngành kỹ thuật. 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 ítbất ngờ.Lý thuyết đồ thị là một lĩnh vực nghiên cứu có ý nghĩa thực tiễn cao đã bắtđầu từ lâu. Những tư tưởng cơ bản của lý thuyết đồ thị được đề xuất vàonhững năm đầu của thế kỷ 18 bởi 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ổitiếng về 7 cái cầu ở thành phố Konigberg. Một cách không chính thức, đồ thịlà một tập các đối tượng được gọi là các đỉnh (hoặc nút) nối với nhau bởicác cạnh (hoặc cung). Cạnh có thể có hướng hoặc vô hướng. Đồ thị thườngđược vẽ dưới dạng một tập các điểm (các đỉnh nối với nhau bằng các đoạnthẳng (các cạnh). Có rất nhiều loại đồ thị đã được nghiên cứu như là cây, đồthị ngẫu nhiên, đồ thị có hướng và vô hướng, đồ thị trọng số và không cótrọng số.Tuy nhiên, do việc tính toán trên đồ thị thường là cần khối lượng tính toáncũng như không gian nhớ lớn,vì vậy gần đây cùng với sự phát triển mạnh mẽcủa kỹ thuật máy tính điện tử, các bài toán tối ưu trên đồ thị ngày càng đượcquan tâm và đã đạt được nhiều kết quả khả quan.Ngày nay, cùng với sự phát triển mạnh mẽ của khoa học và công nghệ, đặcbiệt là máy tính, người ta có khả năng giải quyết được nhiều bài toán rất phứctạp. Tuy nhiên, còn những vấn đề là “không giải được” cho dù kỹ thuật máytính có phát triển và cũng có những vấn đề được xem là “quá phức tạp”, vượtmọi khả năng tính toán thực tế vì mất quá nhiều thời gian. Việc nghiên cứu vềđộ phức tạp của thuật toán đã cho phép chúng ta phân loại được các lớp bàitoán theo từng mức độ phức tạp khác nhau, và chỉ ra ranh giới giữa các lớpbài toán giải được và những lớp bài toán không thể giải được trong thời gianđa thức.9Trong khuôn khổ của luận văn thạc sỹ, tôi chọn đề tài “Một số bài toán tốiưu rời rạc trong lý thuyết đồ thị” nhằm nghiên cứu về lý thuyết đồ thị, độphức tạp của thuật toán.2. Đối tượng nghiên cứuTìm hiểu tổng quan về tối ưu rời rạc, một số bài toán tối ưu thuộc lớp P ,NP-C trong lý thuyết đồ thị3. Phạm vi nghiên cứuLuận văn nghiên cứu các kiến thức chung về tối ưu rời rạc và lý thuyết đồthị, và tập trung vào một số bài toán tối ưu thuộc các lớp P, NP-C trong lýthuyết đồ thị và các thuật giải chúng.4. Nhiệm vụ nghiên cứuTìm hiểu chung về tối ưu rời rạc và lý thuyết đồ thịTìm hiểu một số bài toán tối ưu thuộc lớp P (Polynomial) trong lý thuyếtđồ thị và thuật giải- Tìm hiểu một số bài toán tối ưu thuộc lớp NP-hard trong lý thuyết đồ thịvà thuật giải- Cài đặt một thuật toán và thử nghiệm.5. Những nội dung nghiên cứu chính-Bố cục của luận văn gồm phần mở đầu trình bày lý do chọn đề tài, đốitượng và nhiệm vụ nghiên cứu của đề tài. Chương một, tập trung trình bàymột số kiến thức cơ bản về lý thuyết đồ thị các bài toán NP-C. Chương hai,trình bày một số bài toán tối ưu lớp P trong đồ thị. Chương 3, một số bài toántối ưu thuộc lớp NP-C trong đồ thị, trong chương này tôi trình bày phần càiđặt chương trình ứng dụng.Với những kết quả đạt được, phần cuối của luận văn nêu ra tính hiệuquả của nghiên cứu, đánh giá thuật toán và nêu vài đề xuất nhằm tối ưu thuậttoán, đánh giá các kết quả đạt được, những hạn chế và đề xuất hướng nghiêncứu tiếp theo của đề tài.6. Phương pháp nghiên cứu-Phương pháp đọc tài liệu-Phương pháp quan sát-Phương pháp phân tích – tổng hợp lý thuyết.-Phương pháp thực nghiệm.10Chương 1: MỘT SỐ KIẾN THỨC CƠ BẢN VỀ LÝ THUYẾTĐỒ THỊ CÁC BÀI TOÁN NP-C1.1. Các khái niệm cơ bản về đồ thịĐịnh nghĩa đồ thịTrong toán học và tin học, đồ thị là đối tượng nghiên cứu cơ bản của lýthuyết đồ thị. Một cách không chính thức, đồ thị là một tập các đối tượng gọilà đỉnh nối với nhau bởi các cạnh. Thông thường, đồ thị được vẽ dưới dạngmột tập các điểm (đỉnh, nút) nối với nhau bởi các đoạn thẳng (cạnh). Tùy theoứng dụng mà một số cạnh có thể có hướng. Chúng ta phân biệt các loại đồ thịkhác nhau bởi kiểu và số lượng cạnh nối hai đỉnh nào đó của đồ thị.Định nghĩa 1.1 [3]. Đơn đồ thị vô hướng G=(V, E) bao gồm V là tập cácđỉnh, và E là tập các cặp không có thứ tự gồm hai phần tử khác nhau của Vgọi là các cạnh.Hình 1.: Đồ thị vô hướngĐịnh nghĩa 1.2.[3] Đ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 ứngvới một cặp đỉnh.Định nghĩa 1.3.[3] Đơn đồ thị có hướng G=(V, E) bao gồm V là tập các đỉnh,và E là tậ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.Hình 1.2: Đồ thị có hướngĐịnh nghĩa 1.4. [3] Đa đồ thị có hướng G=(V, E) bao gồm V là tập các đỉ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áccung. Hai cung e1 và e2 được gọi là cung lặp nếu chúng cùng tương ứng vớimột cặp đỉnh.11Hình 1.3: Đa đồ thịHai loại đồ thị cơ bản:a) Đồ thị vô hướng (6 đỉnh, 9 cạnh). b) Đồ thị có hướng (5 đỉnh, 7 cung).Định nghĩa 1.5. [3] Đồ thị hỗn hợp G=(V, E, A ) bao gồm V là tập các đỉnh,E là tập các cạnh (E≠Ø) và A là tập các cung (A ≠Ø) của đồ thị.Hình 1.4: Đồ thị hỗn hợpĐồ thị hỗn hợp (6 đỉnh 5 cạnh, 4 cung)Số đỉnh của đồ thị G là số phần tử trong V.Chúng ta có thể coi các đồ thị vô hướng và có hướng là các trường hợp riêngcủa đồ thị hỗn hợp G=(V, E, A) khi mà A =Ø hoặc E=Ø.1.1.1. Các thuật ngữ cơ bảnĐịnh nghĩa 1.6.[3] 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ì chúngta 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 đầucủa cạnh (u,v).Để có thể biết được bao nhiêu cạnh liên thuộc với một đỉnh, ta đưa vàođịnh nghĩa sauĐịnh nghĩa 1.7.[3] Chúng 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).12Định lý 1.1. [3] Giả sử G=(V,E) là đồ thị vô hướng với m cạnh. Khi đó2m = ∑ deg(v)v∈VChứng minh. Rõ ràng mỗi cạnh e=(u,v) được tính một lần trong deg(u) vàmột lần trong deg(v). Từ đó suy ra tổng tất cả các bậc của các đỉnh bằng hailần số cạnh.Ví dụ 1.1: Đồ thị với n đỉnh và mỗi đỉnh có bậc là 6 có bao nhiêu cạnh?Giải: Theo định lý 1.1, ta có 2m=6n. Từ đó suy ra số cạnh của đồ thị là 3n.Hệ quả 1.1.[3] Trong đồ thị vô hướng, số đỉnh bậc lẻ (nghĩa là có bậc là sốlẻ) là một số chẵn.Chứng minh. Thực vậy, gọi O và U tương ứng là tập đỉnh bậc lẻ và tập đỉnhbậc chẵn của đồ thị. Ta cóDo deg(v) là chẵn với v là đỉnh trong U nên tổng thứ hai trong vế phải ở trênlà số chẵn. Từ đó suy ra tổng thứ nhất (chính là tổng bậc của các đỉnh bậc lẻ)cũng là số chẵn, do tất cả các số hạng của nó là số lẻ, nên tổng này phải gồmmột số chẵn các số hạng. Vì vậy, số đỉnh bậc lẻ phải là số chẵn.Định nghĩa 1.8.[3] Nếu e=(u,v) là cung của đồ thị có hướng G thì chúng tanói hai đỉnh u và v là kề nhau, và nói cung (u,v) nối đỉnh u và đỉnh v hoặccũng nói cung này là đi ra khỏi đỉnh u và đi vào đỉnh v. Đỉnh u (v) sẽ đượcgọi là đỉnh đầu (cuối) của cung (u,v)Định nghĩa 1.9.[3] Chúng 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))Hình 1.5. Đồ thị có hướngVí dụ 1.2. Xét đồ thị cho trong hình 1.5. Ta códeg-(A) = 2, deg-(B) = 3, deg-(C) = 1, deg-(D) = 2, deg-(E) = 2deg+(A) =3, deg+(B) =2, deg+(C) =2, deg+(D) = 2, deg+(E) =11.1.2. Đường đi, chu trình và đồ thị liên thôngĐịnh nghĩa 1.12.[3] Đườ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ãyx0 , 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 ).13Đỉnh u gọi là đỉnh đầu, còn đỉnh v gọi là đỉnh cuối của đường đi. Đường đicó đỉnh đầu trùng với đỉnh cuối (tức là u = v) được gọi là chu trình. Đường đihay chu trình được gọi là đơn nếu như không có cạnh nào bị lặp lại.Ví dụ 1.3. Xét đồ thị vô hướng cho trong hình 1.6.Hình 1.6. Đường đi trên đồ thị vô hướngTa có: a, d, c, f, e là đường đi đơn độ dài 4. Còn d, e, c, a không là đường đi,do (c, e) không phải là cạnh của đồ thị. Dãy b, c, f, e, b là chu trình độ dài 4.Đường đi a, b, e, d, a, b có độ dài là 5 không phải là đường đi đơn, do cạnh (a,b) có mặt trong nó hai lần.Định nghĩa 1.13.[3] Đường đi độ dài n từ đỉnh u đến đỉnh v, trong đó n là sốnguyên dương, trên đồ thị có hướng G = (V, A) là dãyx0 , x1 , ..., xn-1 , xn ,với u = x0 , v = xn , (xi , xi+1 ) ∈ A, 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 cung:(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 đicó đỉnh đầu trùng với đỉnh cuối (tức là u = v) được gọi là chu trình. Đường đihay chu trình được gọi là đơn nếu như không có cạnh nào bị lặp lại.Ví dụ 1.4. Xét đồ thị có hướng cho trong hình 1.7Hình 1.7. Đường đi trên đồ thị có hướngTa có a, d, c, f, e là đường đi đơn độ dài 4. Còn d, e, c, a không là đường đi,do (c, e) không phải là cạnh của đồ thị. Dãy b, c, f, e, b là chu trình độ dài 4.Đường đi a,b, e, d, a, b có độ dài là 5 không phải là đường đi đơn, do cạnh (a,b) có mặt trong nó hai lần.Nếu sử dụng đồ thị để biểu diễn mạng máy tính (trong đó các đỉnh của đồthị tương ứng với các máy tính, còn các cạnh tương ứng với các kênh nối) câuhỏi đặt ra là hai máy tính bất kì có thể trao đổi thông tin với nhau hoặc trựctiếp qua kênh nối chúng hoặc thông qua một vài máy tính trong mạng trunggian không? Câu hỏi đó được phát biểu trong ngôn ngữ đồ thị như sau: Tồn14tại hay không đường đi giữa mọi cặp đỉnh của đồ thị? Để trả lời câu hỏi đó taxét định nghĩa.Định nghĩa 1.14.[3] Đồ thị vô hướng G = (V, E) được gọi là liên thôngnếu luôn tìm được đường đi giữa hai đỉnh bất kỳ của nó.Hai máy tính bất kì trong mạng có thể trao đổi thông tin được với nhaukhi và chỉ khi đồ thị tương ứng với mạng này là đồ thị liên thông.Ví dụ 1.5. Trong hình 1.8: Đồ thị G là liên thông, còn đồ thị H là không liên thôngHình 1.8. Đồ thị liên thông G và đồ thị H gồm 3 thành phần liên thông H1, H2,H31.1.3. Đồ thị có trọng sốĐồ thị được sử dụng để giải các bài toán trong nhiều lĩnh vực khác nhau.Chẳng hạn, đồ thị được sử dụng để xác định các mạch vòng trong vấn đề giảitích mạch điện. Chúng ta có thể xác định xem hai máy tính trong mạng có thểtrao đổi thông tin với nhau được hay không. Khi đó, đồ thị được sử dụng đểbiễu diễn mạng truyền thông với các đỉnh là các nút mạng, các cạnh, các cunglà các đường truyền dữ liệu giữa các nút mạng. Đồ thị có thể dùng để biễudiễn các đường đi trong một vùng: các đỉnh tương ứng với các ngã 3, ngã 4,còn các cạnh, các cung tương ứng là các đường đi 2 chiều và đường đi 1chiều. Để cấu trúc đồ thị có thể biễu diễn được các bài toán thực tế người tađưa vào khái niệm đồ thị có trọng số, trên mỗi cạnh hay mỗi cung được gánmột trọng số thể hiện chi phí cho việc thực hiện một mục đích nào đó trêncạnh hay trên cung.Định nghĩa 1.17.[3] Chúng ta kí hiệu đồ thị có trọng số là bộ 4 G=(V, E, A,w), trong đó, w là hàm trọng sốw: E ∪ A → R ,R: tập số thực,ngoài ra còn có thể kí hiệu w bằng c hoặc weight, cost. Cho S là một tập concủa E ∪ A, khi đó chúng ta kí hiệu w(S)=∑w(s)| s ∈ S là giá trị trọng số củatập S.1.1.4. Các cấu trúc dữ liệu biểu diễn đồ thịCó nhiều cách khác nhau để lưu trữ các đồ thị trong máy tính. Sử dụng cấutrúc dữ liệu nào thì tùy theo cấu trúc của đồ thị và thuật toán dùng để thao táctrên đồ thị đó. Trên lý thuyết, người ta có thể phân biệt giữa các cấu trúc danhsách và các cấu trúc ma trận. Tuy nhiên, trong các ứng dụng cụ thể, cấu trúctốt nhất thường là kết hợp của cả hai. Người ta hay dùng các cấu trúc danh15sách cho các đồ thị thưa (sparse graph), do chúng đòi hỏi ít bộ nhớ. Trong khiđó, các cấu trúc ma trận cho phép truy nhập dữ liệu nhanh hơn, nhưng lại cầnlượng bộ nhớ lớn nếu đồ thị có kích thước lớn.Biểu diễn đồ thị: [2]Một cách biểu diễn đồ thị không có cạnh bội là liệt kê tất cả các cạnh củađồ thị. Nói cách khác, để biểu diễn đồ thị không có cạnh bội ta dùng danhsách kề. Danh sách này chỉ rõ các đỉnh nối với mỗi đỉnh của đồ thị.Ví dụ 1.6. Dùng danh sách kề để mô tả đơn đồ thị trên hình 1.9.aebdcHình 1.9. Đơn đồ thịBảng 1.1 Liệt kê tất cả các đỉnh kề với mỗi đỉnh của đồ thị.ĐỉnhCác đỉnh kềab,c,ebaca,d,edc,eea,c,dVí dụ 1.7. Biểu diễn đồ thị có hướng trên hình 1.10 bằng cách liệt kê tất cảcác đỉnh cuối của các cung xuất phát từ mỗi đỉnh của đồ thị.aebdcHình 1.10. Đồ thị có hướngBảng 1.2. Biểu diễn đồ thị có hướng trên hình 1.10.ĐỉnhCác đỉnh kềab,c,d,ebb,dca,c,e16deb,c,dMa trận kề [2]Khi biểu diễn đồ thị bởi danh sách các cạnh hay danh sách kề, thì việc thựchiện một thuật toán có thể sẽ rất cồng kềnh, nếu đồ thị có nhiều cạnh. Để đơngiản việc tính toán ta có thể biểu diễn đồ thị bằng ma trận. Có hai kiểu matrận thường được dùng để biểu diễn đồ thị sẽ được giới thiệu dưới đây.Giả sử G= (V, E) là một đơn đồ thị, trong đó |V| = n và các đỉnh được liệtkê một cách tùy ý v1,…vn. Ma trận kề A ( hay AG) của G ứng với danh sáchcác đỉnh này là ma trận không - một cấp n x n có phần tử tại vị trí hàng i cột jbằng 1 nếu vi và vj kề nhau và bằng 0 nếu chúng không được nối với nhau.Nói cách khác, ma trận kề của đồ thị là ma trận A = [aij] trong đó1 nếu{ vi,vj} là một cạnh của G0 nếu không có cạnh nối đỉnh vi với vjaij =Ví dụ 1.8. Dùng ma trận kề hãy biểu diễn đồ thị trên hình 1.11adbcHình 1.11. Đơn đồ thịTa sắp xếp các đỉnh theo thứ tự a, b, c, d. Ma trận biểu diễn đồ thị này là:Ma trận kề cũng có thể dùng để biểu diễn đồ thị vô hướng có khuyên và cócạnh bội. Khuyên tại đỉnh ai được biểu diễn bằng 1 tại vị trí (i,j) của ma trậnkề. khi có cạnh bội, ma trận kề không còn là ma trận không - một nữa, vì phầntử ở vị trí thứ (i,j) của ma trận này bằng số cạnh nối các đỉnh ai và aj . Tất cảcác đồ thị vô hướng, kể cả đa đồ thị và giả đồ thị đều có ma trận kề đối xứng.Ví dụ 1.9. Dùng ma trận kề biểu diễn giả đồ thị trên hình 1.12ad17bcHình 1.12. Giả đồ thịMa trận kề với thứ tự các đỉnh a, b, c, d là:Ma trận kề của đồ thị có hướng G = (V, E) có giá trị bằng 1 tại vị trí (i,j)nếu có một cạnh (cung) từ vi tới vj trong đó v1,v2,…,vn là một danh sách bất kỳcủa các đỉnh đồ thị. Nói cách khác, nếu A = [aij] là ma trận kề của đồ thị cóhướng theo danh sách này của đỉnh thì1 nếu có cạnh đi từ vi tới vj0 trong các trường hợp khácaij =Ma trận liên thuộc [2]Một cách thường dùng nữa để biểu diễn đồ thị là dùng 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 Vvà E là ma trận M = [mij], trong đó1 nếu có cạnh ej nối với đỉnh vi0 nếu có cạnh ej không nối với đỉnh vimij =Ví dụ 1.10. Hãy biểu diễn đồ thị trên hình 1.13 bằng ma trận liên thuộc.v1v2v3v4v5e1e3e218e4e6e5Hình 1.13. Đồ thị vô hướngMa trận liên thuộc có dạng1.2. Khái niệm về lớp các bài toán P và NP1.2.1. Khái niệm các loại thời gian tínhThời gian tính tốt nhất: là thời gian tính tối thiểu cần thiết để thực hiệnthuật toán với mọi bộ dữ liệu đầu vào kích thước n.Thời gian tính tồi nhất: là thời gian tính tối đa cần thiết để thực hiện thuậttoán với mọi bộ dữ liệu đầu vào có kích thước nThời gian tính trung bình: là thời gian tính cần thiết để thực hiện thuật toántrên một tập hữu hạn các bộ dữ liệu đầu vào có kích thước n. Thời gian tínhtrung bình được tính theo công thức sau:Thời gian tính trung bình = (Tổng thời gian tính tất cả các bộ dữ liệu cóthể)/ Số bộ dữ liệu.Định nghĩa 1.18. Bài toán quyết định là bài toán mà đầu ra chỉ có thể là‘yes’ hoặc ‘no’(đúng/sai, 0/1).Đối với một bài toán quyết định, có những bộ dữ liệu vào cho ra câu trả lời(đầu ra) là ‘yes’, chúng ta gọi đây là bộ dữ liệu ‘yes’, nhưng cũng có nhữngbộ dữ liệu vào cho ra câu trả lời là ‘no’, chúng ta gọi những bộ dữ liệu này làbộ dữ liệu ‘no’.1.2.2. Lớp bài toán P.Định nghĩa 1.19.[1] Một máy Turing M được gọi là có độ phức tạp thời gianT(n) (hoặc thời gian chạy T(n)) nếu mỗi khi M được cho một nguyên liệu đầuvào w có độ dài n thì M sẽ dừng sau khi thực hiện tối đa T(n) bước chuyển,bất kể M có kiểm nhận w hay không.Chúng ta chủ yếu quan tâm khi T(n) là một hàm đa thức.Một ngôn ngữ L thuộc lớp P nếu có một hàm đa thức T(n) sao cho L =L(M) với một máy Turing đơn định M nào đó có độ phức tạp thời gian T(n)19Ví dụ 1.11: [2] Thuật toán Kruskal tìm cây khung bé nhất của một đồ thị có Vlà số đỉnh và E là số cạnh với thời gian O(E log V). Thời gian thực hiện bởimáy Turing cũng cùng bậc như vậy.1.2.3. Lớp bài toán NP.Định nghĩa 1.20.[1] Ngôn ngữ L thuộc lớp NP (NondeterministicPolynomial) nếu ∃ máy Turing không đơn định M và một độ phức tạp thờigian T(n) sao cho L=L(M) và khi M được cho một nguyên liệu có độ dài n thìnó sẽ kiểm nhận sau không quá T(n) bước chuyển.Nhận xét: Vì mỗi máy Turing đơn định đều là máy Turing không đơn địnhkhông bao giờ có lựa chọn bước chuyển nên P ⊆ NP. Tuy nhiên, dường nhưNP cũng chứa nhiều bài toán không thuộc lớp P. Một câu hỏi toán học sâu sắccòn bỏ ngỏ là liệu P = NP hay không, nghĩa là mọi thứ có thể thực hiện đượcbởi một NTM thật sự trong thời gian đa thức có thể được thực hiện bởi mộtDTM trong một thời gian đa thức hay không, dù có thể là một hàm đa thứcbậc cao hơn.1.2.4. Lớp bài toán NP-đầy đủ (NP-Complete).Định nghĩa 1.21.[1] Ta nói L là bài toán thuộc loại NP-C nếu các khẳngđịnh sau là đúng:1) L thuộc NP2) Với mọi ngôn ngữ L’ ∈ NP có một phép thu thời gian đa thức L’ về LĐịnh lý 1.2.[1] Nếu bài toán P1 là NP-C, P2 là NP và có một phép thu thờigian đa thức từ P1 về P2 thì P2 cũng là NP-C.Chứng minh: Ta cần chứng tỏ rằng mỗi ngôn ngữ L thuộc NP đều thu đượcP2 trong thời gian đa thức. Khi đó theo định nghĩa P2 sẽ thuộc NP-C.Thật vậy, vì P1 là NP-C nên có một phép thu đa thức L về P1. Giả sử thờigian của phép thu này là P(n). Vì thế một chuỗi W ∈ L có chiều dài n đượcbiến đổi thành một chuối x ∈ P1 có chiều dài tối đa là P(n). Ta cũng biết rằngcó một phép thu đa thức từ P1 về P2. Giả sử thời gian của phép thu này làq(m). Thế thì phép thu này biến đổi chuỗi x ∈ P1 về chuỗi y nào đó thuộc P2với thời gian tối đa là q(p(n)). Vì thế phép biến đổi W ∈ L về y ∈ P2 mất thờigian tối đa là p(n) + q(p(n)), đây cũng là một đa thức. Như vậy, ta kết luậnrằng L có thể thu về P2 trong thời gian đa thức.Định lý 1.3.[1] Nếu có một bài toán nào đó là NP-C mà lại thuộc lớp P thì tacó P = NP.Chứng minh: Giả sử có bài toán Q ∈ NP-C và Q ∈ P. Thế thì mọi ngôn ngữL trong NP đều thu được về Q trong thời gian đa thức. Nếu Q ∈ P thì L ∈ P.Như vậy NP ∈ P. Kết hợp với điều hiển nhên là P ∈ NP ta được P = NP.Nhận xét: Chúng ta vẫn tin tưởng rằng nhiều bài toán thuộc lớp NP nhưngkhông thuộc P nên chúng ta sẽ xem việc chứng minh một bài toán là NP-C cógiá trị ngang với việc chứng minh rằng nó không thể giải được trong thời gian20đa thức, và vì thế không có lời giải đúng nào bằng máy tính (và ta sẽ chỉ đitìm lời giải gần đúng).1.2.5. Lớp bài toán NP-khó (NP-Hard).Một cách ngắn gọn có thể hiểu bài toán NP-khó là bài toán mà không cóthuật toán thời gian tính đa thức để giải nó trừ khi P = NP, mà chỉ có các thuậttoán giải trong thời gian hàm mũ. Sau đây là định nghĩa chính thức của bàitoán NP-khó.Định nghĩa 1.22.[1]. Một bài toán A được gọi là NP- khó (NP-hard) nếu nhưsự tồn tại thuật toán đa thức để giải nó kéo theo sự tồn tại thuật toán đa thứcđể giải mọi bài toán trong NP.Như vậy mọi bài toán NP-C đều là NP-Hard.Một số bài toán NP-khó tiêu biểu như:Bài toán bè cực đại (MaxClique): Cho một đồ thị vô hướng G = (V, E). V làtập các đỉnh, E là tập các cạnh tương ứng các đỉnh trong V. Cần tìm bè lớnnhất của G. Bè là tập các đỉnh trong đồ thị mà đôi một có cạnh nối với nhau(là một đồ thị con đầy đủ trong đồ thị G).Bài toán phủ đỉnh (Vertex cover): Ta gọi một phủ đỉnh của đồ thị vô hướngG = (V, E) là một tập con các đỉnh của đồ thị S ⊆ V sao cho mỗi cạnh của đồthị có ít nhất một đầu mút trong S. Bài toán đặt ra là: Cho đồ thị vô hướng G= (V, E) và số nguyên k. Hỏi G có phủ đỉnh với kích thước k hay không?Một cách không hình thức, có thể nói rằng nếu ta có thể giải được một cáchhiệu quả một bài toán NP-khó cụ thể, thì ta cũng có thể giải hiệu quả bất kỳbài toán trong NP bằng cách sử dụng thuật toán giải bài toán NP-khó như mộtchương trình con.Từ định nghĩa bài toán NP-khó có thể suy ra rằng mỗi bài toán NP-đầy đủđều là NP-khó. Tuy nhiên một bài toán NP-khó không nhất thiết phải là NPđầy đủ.Cũng từ bổ đề nêu trên, ta có thể suy ra rằng để chứng minh một bài toán Anào đó là NP-khó, ta chỉ cần chỉ ra phép qui dẫn một bài toán đã biết là NPkhó về nó.Từ phần trình bày trên, ta thấy có rất nhiều bài toán ứng dụng quan trọngthuộc vào lớp NP-khó, và vì thế khó hy vọng xây dựng được thuật toán đúnghiệu quả để giải chúng. Do đó, một trong những hướng phát triển thuật toángiải các bài toán như vậy là xây dựng các thuật toán gần đúng.21Hình 1.14. Mô hình phân lớp các bài toán22Chương 2. MỘT SỐ BÀI TOÁN TỐI ƯU LỚP P, NP-C TRONG ĐỒ THỊ2.1. Bài toán tìm cây khung bé nhất -Thuật toán KruskalMột công ty lập kế hoạch xây dựng mạng truyền thông nối năm trung tâmmáy tính với nhau. Bất kì hai trung tâm nào cũng có thể được nối kết với nhaubằng đường điện thoại. Cần phải kết nối như thế nào để đảm bảo giữa haitrung tâm máy tính bất kì luôn có đường truyền thông sao cho tổng số tiềnthuê bao của toàn mạng là tối thiểu? Chúng ta cần mô hình bài toán này bằngđồ thị có trọng số như hình 2.1, trong đó mỗi đỉnh là một trung tâm máy tính,mỗi cạnh là một đường truyền thông được thuê bao, còn trọng số của mỗicạnh là tiền thuê bao hàng tháng của đường truyền thông được biểu thị bằngcạnh đó. Có thể giải bài toán này bằng cách tìm cây khung sao cho tổng cáctrọng số của các cạnh của cây đạt cực tiểu. Cây khung như thế được gọi là câykhung nhỏ nhất.San FranciscoChicagoNew YorkAtlantaDenver$2000$1200$1300$1400$900$700$1600$2200$1000$800Hình 2.1. Đồ thị có trọng số biểu thị tiền thuê bao hàng tháng đường truyềnthông trong mạng máy tínhĐịnh nghĩa 2.1.[2] Cây khung nhỏ nhất trong một đồ thị liên thông có trọngsố là cây khung có tổng trọng số trên các cạnh của nó là nhỏ nhất.Để minh hoạ cho ứng dụng của bài toán cây khung nhỏ nhất, dưới đây tanghiên cứu thuật toán Kruskal.Tư tưởng [6]Thuật toán do Joseph Kruskal phát minh vào năm 1956. Để thực hiện thuậttoán Kruskal, chọn cạnh có trọng số nhỏ nhất của đồ thị.23Lần lượt ghép thêm vào cạnh có trọng số tối thiểu và không tạo thành chutrình với các cạnh đã được chọn. Thuật toán dừng sau khi (n-1) cạnh đã đượcchọn.Giả sử ta cần tìm cây bao trùm nhỏ nhất của đồ thị G. Thuật toán bao gồmcác bước sau:• Khởi tạo rừng F (tập hợp các cây), trong đó mỗi đỉnh của G tạo thành mộtcây riêng biệt• Khởi tạo tập S chứa tất cả các cạnh của G• Chừng nào S còn khác rỗng và F gồm hơn một cây Xóa cạnh nhỏ nhất trong S Nếu cạnh đó nối hai cây khác nhau trong F, thì thêm nó vào F và hợp haicây kề với nó làm một Nếu không thì loại bỏ cạnh đó.Khi thuật toán kết thúc, rừng chỉ gồm đúng một cây và đó là một cây baotrùm nhỏ nhất của đồ thị G.Thuật toán Kruskal [2]Procedure Kruskal (G: đồ thị V đỉnh, liên thông, có trọng số)T:= đồ thị rỗngfor i := 1 to n-1begine := một cạnh bất kì của G với trọng số nhỏ nhất và không tạo ra chu trìnhtrong T, khi ghép nó vào T.T:= T với cạnh e đã được ghép thêm vào.end { T là cây khung nhỏ nhất}Độ phức tạp [6]Nếu E là số cạnh và V là số đỉnh của đồ thị thì thuật toán Kruskal chạytrong thời gian O(E log V).Ví dụ 2.1. Cho đồ thị G như hình 2.2, yêu cầu tìm ra cây khung nhỏ nhất củađồ thị G ?24Hình 2.2. Đồ thị có trọng số GG gồm có 8 đỉnhĐồ thị G có n phần tử. Thuật toán Kruskal sẽ dừng khi có n-1 trong tập hợp Tn=8Vậy số cạnh trong tập hợp T: n - 1 = 8 - 1 = 7Bước 1: Bảng 2.1: Sắp xếp các cạnh theo thứ tự trọng số tăng dần có:CạnhTrọng sốCạnh (1,5)1Cạnh (4, 8)1Cạnh (7,8)1Cạnh (1, 6)2Cạnh (2, 3)2Cạnh (3, 8)3Cạnh (1, 3)4Cạnh (3, 7)4Cạnh (4, 5)5Cạnh (4, 6)5Cạnh (1, 4)6Cạnh (5, 6)6Cạnh (2, 4)7Cạnh (6, 8)7Cạnh (1, 2)8Cạnh (6, 7)8Cạnh (4, 3)9và khởi tạo T := Ø.Bước 2: Duyệt theo cạnh e thuộc danh sách đã sắp xếp+ Vì T + {(1, 5)} không chứachu trình thì ghép cạnh (1,5)vào cây T:= T + {(1,5)}.25+ Vì T + {(4, 8)} không chứachu trình thì ghép cạnh (4,8)vào cây T:= T + {(4, 8)}+ Vì T + {(7, 8)} không chứachu trình thì ghép cạnh (7,8)vào câyT:= T + {(7, 8)}+ Vì T + {(1, 6)} không chứachu trình thì ghép cạnh (1,6)vào câyT:= T + {(1, 6)}+ Vì T + {(2, 3)} không chứachu trình thì ghép cạnh (2,3)vào câyT:= T + {(2, 3)}

Tài liệu liên quan

• Bài toán tối ưu rời rạc và Lượng cực đại
  • 7
  • 1
  • 9
• Toán tử Owa trong một số bài toán tối ưu
  • 50
  • 654
  • 3
• GIÁO TRÌNH TOÁN RỜI RẠC - CHƯƠNG V MỘT SỐ BÀI TOÁN TỐI ƯU TRÊN ĐỒ THỊ
  • 21
  • 856
  • 3
• Chương 5: MỘT SỐ BÀI TOÁN TỐI ƯU TRÊN ĐỒ THỊ
  • 21
  • 737
  • 1
• Tài liệu Giáo trình toán rời rạc - Chương 5: MỘT SỐ BÀI TOÁN TỐI ƯU TRÊN ĐỒ THỊ doc
  • 20
  • 1
  • 7
• Tài liệu Một số bài toán tối ưu trên đồ thị pptx
  • 20
  • 990
  • 25
• Tài liệu Chương 5: Một số bài toán tối ưu trên đồ thị pptx
  • 21
  • 553
  • 0
• Tài liệu CHƯƠNG V MỘT SỐ BÀI TOÁN TỐI ƯU TRÊN ĐỒ THỊ pdf
  • 20
  • 601
  • 2
• Luận văn: TOÁN TỬ OWA TRONG MỘT SỐ BÀI TOÁN TỐI ƯU potx
  • 50
  • 547
  • 1
• [Giáo trình Toán rời rạc] - Chương5 - Một số bài toán Tối ưu trên Đồ thị potx
  • 20
  • 494
  • 1

Tài liệu bạn tìm kiếm đã sẵn sàng tải về

(1.17 MB - 57 trang) - Một số bài toán tối ưu rời rạc trong lý thuyết đồ thị Tải bản đầy đủ ngay ×