THUẬT TOÁN TÔ MÀU ĐỒ THỊ VÀ ỨNG DỤNG XẾP

LỊCH THI

THE GRAPH COLORING ALGORITHM AND EXAMS SCHEDULING

APPLICATION

SVTH: NGHIÊM VĂN HƯNG

Lớp: 04CCT02, Trường Đại học Sư Phạm

GVHD: PGS. TSKH TRẦN QUỐC CHIẾN

Khoa Tin học, Trường Đại học Sư Phạm

T́M TĂT

Lý thuyết đồ thị là một ngành khoa học có nhiều ứng dụng hiện đại. Đề tài này có mục tiêu là

nghiên cứu thuật toán tô màu đồ thị, mục đích là xây dựng chương trình xếp lịch thi học kỳ.

ABSTRACT

Graphics theory is an important science which has many modern application. This subject has

got the goal: research graph coloring algorithm, the purpose: build an exams scheduling

application.

1. MỞ ĐẦU

1.1. Lý do chọn đề tài

Với hình thức học chế tín chỉ, sinh viên có thể chủ động chọn đăng kí môn học theo kế

hoạch học tập của mình. Điều này làm cho việc xếp lịch thi trở nên khó khăn hơn. Phòng đào

tạo phải sắp xếp lịch thi sao cho không có sinh viên nào thi nhiều hơn một môn tại cùng một

thời điểm. Việc xếp lịch thủ công như trước đây là không khả thi. Do đó, đề tài này có mục

đích là xây dựng một chương trình xếp lịch thi, góp phần tin học hóa công tác đào tạo.

1.2. Đối tượng 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 kề nhau được gán cùng

màu.

Bài toán xế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.

1.3. Giải pháp công nghệ

- Phân tích, thiết kế hướng đối tượng với UML.

- Ngôn ngữ lập trình Visual C# 2005.

- Hệ quản trị cơ sở dữ liệu SQL Server 2000.

2. NỘI DUNG

2.1. Cơ sở lý thuyết

2.1.1. Thuật toán tô màu đồ thị

Input: đồ thị G = (V, E).

Output: đồ thị G = (V, E) có các đỉnh đã được gán màu.

Các bước:

 Lập danh sách các đỉnh của đồ thị E’:=[v1,v2, ,vn] được sắp xếp theo thứ tự bậc

giảm dần: d(v1) ≥ d(v2) ≥ ≥ d(vn)

Đặt i := 1;

 Tô màu i cho đỉnh đầu tiên trong danh sách. Duyệt lần lượt các đỉnh tiếp theo và tô

màu i cho đỉnh không kề đỉnh đã được tô màu i.

 Nếu tất cả các đỉnh đã được tô màu thì kết thúc, đồ thị được tô bằng i màu. Ngược

lại, sang bước .

 Loại khỏi E’ các đỉnh đã tô màu. Sắp xếp lại các đỉnh trong E’ theo thứ tự bậc giảm

dần. Đặt i := i + 1 và quay lại bước .

2.1.2. Xây dựng các heuristic

Largest degree first: Các đỉnh được sắp xếp theo bậc. Quá trình tô màu là chọn từng

môn thi từ đỉnh của danh sách và gán cho màu thấp nhất (để đơn giản các màu được

đánh theo số) không xung đột.

Largest degree first: fill from top - Các đỉnh vẫn được sắp xếp theo bậc. Chúng ta sẽ

duyệt hết danh sách các đỉnh, đặt càng nhiều đỉnh có thể được vào slot thời gian đầu

tiên (màu thấp nhất) sau đó trở về đầu danh sách tiếp tục cho màu thứ hai, và cứ như

vậy.

Largest degree first recursive: fill from top – tương tự như heuristic thứ hai, chỉ khác

ở chỗ khi tô màu xong đỉnh nào, ta loại bỏ đỉnh đó khỏi danh sách, tính toán lại bậc của

các đỉnh và sắp xếp lại danh sách. Heuristic này rất phù hợp với đề tài và đã được chọn

để cài đặt chương trình.

2.2. Phân tích – Thiết k