Tài liệu Nghiên cứu bài toán tô màu đồ thị và ứng dụng lập lịch thi trong đào tạo theo hệ thống tín chỉ

NGUYỄN VĂN LƯỢNG BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC SƯ PHẠM HÀ NỘI 2 ả NGUYỄN VĂN LƯỢNG LUẬN VĂN THẠC SĨ MÁY TÍNH NGHIÊN CỨU BÀI TOÁN TÔ MÀU ĐỒ THỊ VÀ ỨNG DỤNG LẬP LỊCH THI TRONG ĐÀO TẠO THEO HỆ THỐNG TÍN CHỈ LUẬN VĂN THẠC SĨ MÁY TÍNH KHÓA 2011 - 2013 HÀ NỘI, 2013 BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC SƯ PHẠM HÀ NỘI 2 NGUYỄN VĂN LƯỢNG NGHIÊN CỨU BÀI TOÁN TÔ MÀU ĐỒ THỊ VÀ ỨNG DỤNG LẬP LỊCH THI TRONG ĐÀO TẠO THEO HỆ THỐNG TÍN CHỈ Chuyên ngành: Khoa học máy tính Mã số: 60 48 01 01 LUẬN VĂN THẠC SĨ MÁY TÍNH Người hướng dẫn khoa học: PGS. TS Lê Huy Thập HÀ NỘI, 2013 LỜI CẢM ƠN Trước tiên, em xin gửi lời cảm ơn và lòng biết ơn sâu sắc nhất tới thầy giáo PGS. TS Lê Huy Thập, người đã luôn động viên, tận tình hướng dẫn và giúp đỡ em rất nhiều về kiến thức, kinh nghiệm trong quá trình thực hiện đề tài. Em xin chân thành cảm ơn các thầy cô phòng Sau Đại học, các thầy cô khoa Công nghệ thông tin, các thầy cô thuộc Viện Công nghệ Thông tin Viện Khoa học và Công nghệ Việt Nam, cũng như tất cả các thầy cô Trường Đại học Sư phạm Hà Nội 2 đã tạo điều kiện và truyền đạt những kiến thức quý báu cho em trong suốt quá trình học tập. Xin chân thành cảm ơn các anh, các chị và các bạn học viên lớp Cao học K15KHMT- trường Đại học sư phạm Hà Nội 2 đã luôn động viên, giúp đỡ, nhiệt tình chia sẻ những kinh nghiệm học tập và công tác trong suốt khoá học. Mặc dù rất cố gắng, song luận văn này không thể tránh khỏi những thiếu sót, kính mong được sự chỉ dẫn của các quý thầy cô và các bạn. Hà Nội, tháng 12 năm 2013 Tác giả Nguyễn Văn Lượng LỜI CAM ĐOAN Tôi xin cam đoan rằng số liệu và kết quả nghiên cứu trong luận văn này là trung thực và không trùng lặp với các đề tài khác. Tôi cũng xin cam đoan rằng mọi sự giúp đỡ cho việc thực hiện luận văn này đã được cảm ơn và các thông tin trích dẫn trong luận văn đã được chỉ rõ nguồn gốc. Hà Nội, tháng 12 năm 2013 Tác giả Nguyễn Văn Lượng MỤC LỤC MỞ ĐẦU........................................................................................................... 1 Chương 1: CƠ SỞ LÝ THUYẾT...................................................................... 4 1.1. Tổng quan đơn đồ thị vô hướng hữu hạn................................................... 4 1.1.1. Đơn đồ thị vô hướng liên thông ....................................................... 4 1.1.2. Đồ thị phẳng ..................................................................................... 5 1.1.3. Đồ thị vô hướng con đầy đủ và màu đồ thị...................................... 6 1.2. Giới thiệu các thuật toán tô màu .............................................................. 11 1.2.1. Thuật toán thu gọn (hòa nhập) đỉnh (Contraction Algorithm)....... 11 1.2.2. Thuật toán tô màu tuần tự (Sequential Coloring) .......................... 14 1.2.3. Thuật toán duyệt theo chiều sâu có chặn nhánh............................. 19 1.2.4. Thuật toán tham lam (Greedy Coloring)........................................ 20 1.3. Giới thiệu các phương pháp lập lịch thi................................................... 22 1.3.1. Các phương pháp thông thường ..................................................... 22 1.3.2. Phương pháp lập lịch thi dựa vào tô màu đồ thị ............................ 22 1.4. Kết luận chương ....................................................................................... 26 Chương 2: ỨNG DỤNG LÝ THUYẾT ĐỒ THỊ VÀO LẬP LỊCH THI....... 27 2.1. Ma trận liền kề ......................................................................................... 27 2.2. Xác định đồ thị con đầy đủ dựa vào ma trận liền kề................................ 29 2.3. Tô màu đồ thị dựa vào ma trận liền kề .................................................... 34 2.3.1. Thuật toán sắp xếp đỉnh của đơn đồ thị ......................................... 34 2.3.2. Thuật toán tô màu đơn đồ thị với ma trận liền kề .......................... 35 2.4. Lập lịch thi ............................................................................................... 37 2.4.1. Đặt vấn đề....................................................................................... 37 2.4.2. Bài toán lập lịch thi theo hệ thống tín chỉ ...................................... 37 2.5. Kết luận chương ....................................................................................... 48 Chương 3: XÂY DỰNG ỨNG DỤNG LẬP LỊCH THI TRONG ĐÀO TẠO THEO HỆ THỐNG TÍN CHỈ ......................................................................... 49 3.1. Ứng dụng lập lịch thi tại Trường Đại học Sư phạm Hà Nội 2................. 49 3.1.1. Phân tích, thiết kế bằng UML ........................................................ 49 3.1.2. Các chức năng của chương trình.................................................... 50 KẾT LUẬN ..................................................................................................... 56 TÀI LIỆU THAM KHẢO............................................................................... 57 DANH MỤC TỪ VIẾT TẮT RLF Recursive - Largest - First LF Largest First DSATUR Degree of Saturation BSC Backtracking Sequential Coloring 1 MỞ ĐẦU 1. Lý do chọn đề tài Lập lịch biểu là việc không thể thiếu ở bất kì tổ chức nào hoạt động trong xã hội loài người. Từ ngàn xưa, con người đã thực hiện việc lập kế hoạch bằng cách ghi chép bằng tay các kí hiệu hay số liệu, thông tin trên vách đá, trên tre, trên vải và trên giấy, … có thể gọi chung là trên sổ sách. Ngày nay, cùng với tiến bộ xã hội, khoa học máy tính đã có những bước tiến dài, đem lại sự tiện lợi và hiệu quả kinh tế cao trong rất nhiều lĩnh vực từ công nghiệp cho đến đời sống. Việc lập lịch biểu bắt đầu có sự giúp sức của máy tính, giúp ghi nhớ các số liệu lớn một cách dễ dàng và thuận lợi hơn so với ghi chép bằng tay trên sổ sách, nhất là khi vận chuyển. Nhiều phần mềm máy tính có chức năng hỗ trợ lập lịch như MS.Excel, MS.Project,… nhưng sự “thiếu thông minh” của chúng vẫn làm cho con người phải tiêu tốn nhiều thời gian cũng như công sức khi lập lịch. Nhu cầu máy tính thông minh như con người trở thành bức thiết. Các kỹ thuật mạnh mẽ của công nghệ tri thức đã sớm cho ra đời những cỗ máy có trí thông minh nhân tạo dạng hệ chuyên gia như máy chẩn đoán bệnh, máy dự báo thời tiết, … hoặc dạng hệ tư vấn hỗ trợ con người ra quyết định trong nhiều tình huống vô cùng hữu ích. Từ đó, những kỹ thuật này cũng hỗ trợ việc lập lịch biểu trên máy tính trở nên dễ dàng hơn. Thông thường, tại một trường đại học, nhu cầu có một công cụ hỗ trợ tự động lập lịch biểu hết sức cần thiết cho hai việc cụ thể: lập lịch giảng dạy (hay lịch công tác) và lập lịch thi. Tùy vào đặc thù và nhu cầu của mỗi trường mà các trường đã tự xây dựng công cụ lập lịch thi cho riêng mình, công cụ này được xây dựng bằng những kỹ thuật khác nhau nhằm đạt kết quả càng gần với mong muốn càng tốt. Một số kỹ thuật thường được dùng để giải quyết bài toán lập lịch thi như giải thuật di truyền, leo đồi, luyện thép, … Thế 2 nhưng, qua khảo sát cho thấy khi sử dụng các kỹ thuật trên kết quả của bài toán vẫn còn nhiều hạn chế. Vì thế, con người vẫn hướng đến một giải pháp sao cho kết quả bài toán lập lịch thi “tối ưu” hơn nữa. Đề tài: “Nghiên cứu bài toán tô màu đồ thị và ứng dụng lập lịch thi trong đào tạo theo hệ thống tín chỉ” tập trung nghiên cứu về lý thuyết đồ thị mà cụ thể ở đây là bài toán “Tô màu đồ thị”, qua đó tác giả đề xuất một phương pháp lập lịch thi dựa trên thuật toán tô màu đồ thị. 2. Mục đích nghiên cứu Nghiên cứu thuật toán tô màu đồ thị. Ứng dụng xây dựng chương trình lập lịch thi với 2 tiêu chí: phân bổ đều thời gian sao cho các môn học trong một hệ và các môn thi sử dụng chung phòng thực hành không thi trùng nhau, thời gian rải đều cho các môn trong một lớp và trong toàn thời gian. 3. Nhiệm vụ nghiên cứu Lưu các tham số của đơn đồ thị vô hướng hữu hạn vào cơ sở dữ liệu quan hệ, tô màu và lập lịch biểu. 4. Đối tượng và phạm vi nghiên cứu Lý thuyết đồ thị là ngành khoa học được phát triển từ lâu nhưng lại có nhiều ứng dụng hiện đại. Một đồ thị là một tập hợp các đỉnh và các đường nối các đỉnh gọi là cạnh (cung). Tô màu đồ thị là phép gán màu cho mỗi đỉnh sao cho không có hai đỉnh liền kề nhau được gán cùng màu. Bài toán lập lịch thi được mô hình hóa thành bài toán tô màu đồ thị như sau: lập đồ thị có các đỉnh là các môn thi, hai môn thi kề nhau nếu có một sinh viên thi cả hai môn này. Thời điểm thi của mỗi môn được biểu thị bằng các màu khác nhau. 5. Những đóng góp mới của đề tài Sự phát triển nhanh chóng của giáo dục song song với sự phát triển mạnh mẽ của công nghệ thông tin nói chung và đối với Trường Đại học Sư 3 phạm Hà Nội 2 nói riêng, đề tài nguyên cứu của tác giả giúp phần tin học hóa công tác đào tạo cụ thể là công tác lập lịch thi của các khoa. Hiện nay các khoa Trường Đại học Sư phạm Hà Nội 2 vẫn còn lập lịch thi thủ công, Trợ lý giáo vụ khoa xếp bằng tay trên file dữ liệu excel hoặc word. Với đề tài của tác giả nghiên cứu sẽ thích hợp với thực tiễn sử dụng của Trường Đại học Sư phạm Hà Nội 2. 6. Phương pháp nghiên cứu Nghiên cứu tài liệu, tìm hiểu các thông tin trên Internet về các phương pháp lập lịch biểu. Nghiên cứu về các thuật toán tô màu. Ứng dụng lý thuyết tô màu đồ thị vào việc lập lịch biểu, xây dựng chương trình demo. 4 Chương 1: CƠ SỞ LÝ THUYẾT 1.1. Tổng quan đơn đồ thị vô hướng hữu hạn 1.1.1. Đơn đồ thị vô hướng liên thông Định nghĩa: Đơn đồ thị hữu hạn vô hướng được kí hiệu là G =(V,E) trong đó: i) V là tập hợp khác rỗng mà các phần tử của nó gọi là đỉnh của G và card(V) = n . ii) E là tập các cặp (u,v) hai phần tử phân biệt không có thứ tự của E được gọi là cạnh của G. Cạnh của E được kí hiệu là e = (u, v) hoặc e = uv. Mỗi cặp đỉnh có nhiều nhất một cạnh.  Một số khái niệm và tính chất cơ bản: Bậc của đỉnh: Đồ thị vô hướng G=(V,E). Bậc của đỉnh v, ký hiệu là deg(v), là số cạnh kề với v, trong đó một khuyên tại một đỉnh được đếm hai lần cho bậc của đỉnh ấy. Định lý: Cho đơn đồ thị G=(V,E), m là số cạnh (cung). 1) 2m  vV deg(v) 2) Số đỉnh bậc lẻ của đồ thị là số chẵn Đẳng cấu: Cho hai đơn đồ thị G=(V,E) và G’=(V’,E’). Ta nói rằng G đẳng cấu G’, ký hiệu G  G’, nếu tồn tại song ánh f: V V’ sao cho: uv là cạnh của G  f(u)f(v) là cạnh của G’. Nếu G và G’ là các đơn đồ thị vô hướng đẳng cấu qua ánh xạ f thì chúng có: Cùng số đỉnh, cùng số cạnh, cùng số đỉnh với bậc cho sẵn và deg(v)=deg(f(v)). Đồ thị con:  G’ được gọi là đồ thị con của G, ký hiệu G’ ≤ G nếu V’  V và E’  E.  Nếu V’=V và E’ E thì G’ được gọi là đồ thị con khung của G. 5 Liên thông: Đồ thị G=(V,E) được gọi là liên thông nếu có đường đi giữa mọi cặp đỉnh u, v bất kỳ trong G. 1.1.2. Đồ thị phẳng Định nghĩa 1: Một đồ thị được gọi là phẳng nếu nó có thể vẽ được trên một mặt phẳng mà không có các cạnh nào cắt nhau (ở một điểm không phải là điểm mút của các cạnh). Hình vẽ như thế gọi là một biểu diễn phẳng của đồ thị. Thí dụ 1: 1) Một cây, một chu trình đơn là một đồ thị phẳng. 2) K4 là đồ thị phẳng bởi vì có thể vẽ lại như hình bên không có đường cắt nhau: 3) Xét đồ thị G như trong hình dưới đây. Có thể biểu diễn G một cách khác như trong hình bên phải, trong đó bất kỳ hai cạnh nào cũng không cắt nhau. 4) Đồ thị đầy đủ K5 là một thí dụ về đồ thị không phẳng. Định nghĩa 2: Cho G là một đồ thị phẳng. Mỗi phần mặt phẳng giới hạn bởi một chu trình đơn không chứa bên trong nó một chu trình đơn khác, gọi là một miền (hữu hạn) của đồ thị G. Chu trình giới hạn miền là biên của miền. 6 Mỗi đồ thị phẳng liên thông có một miền vô hạn duy nhất (là phần mặt phẳng bên ngoài tất cả các miền hữu hạn). Số cạnh ít nhất tạo thành biên gọi là đai của G; trường hợp nếu G không có chu trình thì đai chính là số cạnh của G. Thí dụ 2: 1) Một cây chỉ có một miền, đó là miền vô hạn. 2) Đồ thị phẳng ở hình dưới có 5 miền, M5 là miền vô hạn, miền M1 có biên abgfa, miền M2 có biên là bcdhgb, … Chu trình đơn abcdhgfa không giới hạn một miền vì chứa bên trong nó chu trình đơn khác là abgfa. Định lý (Euler, 1752): Nếu một đồ thị phẳng liên thông có n đỉnh, p cạnh và d miền thì ta có hệ thức: n  p + d = 2. Chứng minh: xem [2, 3, 4, 6]. Hệ quả: Trong một đồ thị phẳng liên thông tuỳ ý, luôn tồn tại ít nhất một đỉnh có bậc không vượt quá 5. Chứng minh: xem [5]. 1.1.3. Đồ thị vô hướng con đầy đủ và màu đồ thị Đồ thị đầy đủ n đỉnh, ký hiệu là Kn, là đơn đồ thị vô hướng mà giữa hai đỉnh bất kỳ của nó luôn có cạnh nối. Đồ thị Kn có tất cả n(n-1)/2 cạnh. Nó là đơn đồ thị có nhiều cạnh nhất, đồng thời là đồ thị chính quy bậc n-1. 7 Ví dụ: Đồ thị đầy đủ K7 Một đơn đồ thị vô hướng G là môt cặp (V,E) với V là một tập các đỉnh và E là một tập các cạnh của đồ thị G, trong đó u là một đỉnh liền kề v nếu và chỉ nếu {u,v} là một cạnh trong E. Đồ thị vô hướng con đầy đủ của G là một đồ thị vô hướng có tập đỉnh C  V sao cho mỗi cặp đỉnh trong C là kề nhau ở trong G. Bài toán xác định đồ thị vô hướng con đầy đủ là bài toán thuộc lớp NP- đầy đủ. Màu của đồ thị G (hay còn gọi là sắc số của đồ thị G) là số màu ít nhất (G) cần thiết để tô màu các đỉnh của G sao cho các đỉnh kề nhau được tô bởi các màu khác nhau. Ví dụ: Cho đơn đồ thị vô hướng G dưới đây: Ta thấy rằng 4 đỉnh b, d, g, e đôi một kề nhau nên phải được tô bằng 4 màu khác nhau. Do đó χ(G) ≥ 4. Ngoài ra, có thể dùng 4 màu đánh số 1, 2, 3, 4 để tô màu G như sau: 8 Như vậy χ(G) = 4.  Màu (sắc số) của một số đơn đồ thị vô hướng đặc biệt: Đồ thị G Đồ thị đầy đủ Kn Đồ thị vòng Cn Đồ thị bánh xe Wn Đồ thị hình sao Sn Đồ thị hình cây Tn Ví dụ: χ(K6) = 6 χ(S9) = 2 Màu của đồ thị χ(G) χ(Kn) = n χ(Cn) = 2 với n – chẵn χ(Cn) = 3 với n – lẻ χ(Wn) = 4 với n – chẵn χ(Wn) = 3 với n – lẻ χ(Sn) = 2 χ(Tn) = 1 χ(C6) = 2 χ(W7) = 3 χ(C7) = 2 χ(W8) = 3 9  Một số định lý và mệnh đề về màu (sắc số) đồ thị: Định lý 1: Nếu đồ thị G chứa một đồ thị con đẳng cấu với đồ thị đầy đủ Kn thì χ(G) ≥ n. Chứng minh: xem [5] Định lý 2: Nếu đơn đồ thị G không chứa chu trình độ dài lẻ thì χ(G) =2. Chứng minh: xem [5] Định lý 3: Với mỗi số nguyên dương n, tồn tại một đồ thị không chứa K3 và có sắc số bằng n. Chứng minh: xem [5] Định lý 4: Nếu mọi đỉnh của đồ thị G có bậc không lớn hơn k thì χ(G) ≤ k+1. Chứng minh: xem [5] Định lý 5: Với một đồ thị G bất kỳ, ta có thể tìm được một cách phân hoạch V(G)= V1  V2 (V1, V2 ≠ ) sao cho χ(G[V1]) + χ(G[V2])= χ(G). Định lý 6: Nếu G là đồ thị không đầy đủ, ta có thể tìm được một cách phân hoạch V(G)= V1  V2 (V1, V2 ≠ ) sao cho χ(G[V1]) + χ(G[V2]) > χ(G). Định lý 7: Giả sử |V(G)|=n và V(G) có một phân hoạch {V1,V2, …, Vk} sao cho ( 1≤ i 0) { x= đỉnh có bậc lớn nhất trong G; colornumber = colornumber+1; F(x)=colornumber; NN= tập hợp các đỉnh không kề với x; while (|NN| > 0) { // tìm đỉnh y  NN để có thể thu gọn với x maxcn= -1; // số đỉnh kề chung với x lớn nhất ydegree= -1; // bậc của đỉnh y cần tìm. for mọi đỉnh z  NN { cn= số lượng đỉnh kề chung của z và x; if (cn> maxcn or (cn==maxcn and bậc của z < ydegree)) { y=z; ydegree = bậc của đỉnh y; maxcn=cn; } } if (maxcn==0) { // trường hợp không thể thu gọn thêm