Facebook: @ www.facebook.com/ 1 | P a g e TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI VIỆN CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG BÀI TẬP LỚN THIẾT KẾ VÀ PHÂN TÍCH THUẬT TOÁN ĐỀ TÀI 15: BÀI TOÁN TÔ MẦU ĐỒ THỊ Giáo viên hướng dẫn: PGS. NGUYỄN ĐỨC NGHĨA Sinh viên thực hiện : 1. Nguyễn Thị Thanh Vi 20073430 CNPM K52 2. Ngô Văn Vĩ 20073500 CNPM K52 3. Nhâm Ngọc Trung 20073050 CNPM K52 Hà Nội, 12/2010 Facebook: @ www.facebook.com/ 2 | P a g e MỤC LỤC I. GIỚI THIỆU BÀI TOÁN...................................................................................................................3 1. Tổng quan về đồ thị ........................................................................................................................3 1.1. Đồ thị và các cách biểu diễn đồ thị .............................................................................................3 1.2. Các bài toán điển hình.................................................................................................................5 2. Bài toán tô mầu đồ thị ....................................................................................................................5 2.1. Bài toán tô mầu cạnh ...................................................................................................................5 2.2. Bài toán tô mầu đỉnh....................................................................................................................6 2.3. Các khái niệm liên quan ..............................................................................................................6 2.4. Ứng dụng .......................................................................................................................................7 II. GIẢI THUẬT ..................................................................................................................................8 1. Bài toán tô mầu đỉnh.......................................................................................................................8 1.1. Các định nghĩa sử dụng:.........................................................................................................8 1.2. Thuật toán................................................................................................................................9 1.3. Ví dụ .......................................................................................................................................11 2. Bài toán tô mầu cạnh ....................................................................................................................16 2.1. Giải thuật...............................................................................................................................16 2.3. Độ phức tạp: ..........................................................................................................................25 III. CÀI ĐẶT THUẬT TOÁN............................................................................................................25 1. Bài toán tô mầu đỉnh.........................................................................................................................26 2. Bài toán tô mầu cạnh ........................................................................................................................35 2.1. Đọc dữ liệu từ file ..............................................................................................................35 2.2. Dữ liệu vào từ bàn phím.....................................................................................................47 3. Mã nguồn.......................................................................................................................................61 IV. TÀI LIỆU THAM KHẢO............................................................................................................61 PHỤ LỤC 1: DANH MỤC CÁC HÌNH ẢNH TRONG TÀI LIỆU .................................................62 PHỤ LỤC 2: PHÂN CHIA CÔNG VIỆC....................