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

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. | Tuyển tập Báo cáo Hội nghị Sinh viên Nghiên cứu Khoa học lần thứ 6 Đại học Đà Nẵng - 2008 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 . 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. . Đố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. . 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. 271 Tuyển tập Báo cáo Hội nghị Sinh viên Nghiên cứu Khoa học lần thứ 6 Đại học Đà Nẵng - 2008 2. NỘI DUNG . Cơ sở

• Toán học
• Lý thuyết đồ thị
• thuật toán tô màu đô thị
• xếp lịch thi
• chuyên đề toán học
• kiến thức toán
• Bài giảng Lý thuyết đồ thị
• Giới thiệu Lý thuyết đồ thị
• Môn học Lý thuyết đồ thị
• Đại cương Lý thuyết đồ thị
• Hình thức thi Lý thuyết đồ thị
• tài liệu về lý thuyết đồ thị
• học lý thuyết đồ thị tốt
• phương pháp học lý thuyết đồ thị
• hàm trên đồ thị
• Đại cương về đồ thị
• Các mô hình đồ thị
• Thuật ngữ cơ bản của đồ thị
• Đường đi của đồ thị
• Sự liên thông đồ thị
• Biểu diễn đồ thị trên máy tính
• Sự đẳng cấu của đồ thị
• Phương pháp biểu diễn đồ thị
• Biểu diễn đồ thị bằng ma trận kề
• Đồ thị Euler
• Đồ thị Hamilton
• Chu trình Hamilton
• Kiểm tra đồ thị Hamilton
• Đơn đồ thị đặc biệt
• Đồ thị bánh xe
• Đồ thị con
• Mô hình đồ thị