Bài tập lớn: Thiết kế và phân tích thuật toán - Bài toán tô màu đồ thị

Tô màu đồ thị và sự tổng quát của nó là công cụ hữu dụng trong việc mô hình hóa rất nhiều bài toán khác nhau trong vấn đề xếp lịch, xây dựng chương trình và vấn đề phân công công việc. Bài toán tô màu đồ thị bao gồm nhiều loại: tô màu đỉnh đồ thị (vertex graph coloring) , tô màu cạnh đồ thị (edge graph coloring)
Nội dung trích xuất từ tài liệu:
Bài tập lớn: Thiết kế và phân tích thuật toán - Bài toán tô màu đồ thịAlgo2010N15-NguyenThiThanhVi-NgoVanVi-NhamNgocTrung-CNPMK52 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 1|PageAlgo2010N15-NguyenThiThanhVi-NgoVanVi-NhamNgocTrung-CNPMK52 MỤC LỤCMỤC LỤC.........................................................................................................................................2 2.4. Ứng dụng...........................................................................................................................7 2.1. Đọc dữ liệu từ file............................................................................................................36 2.2. Dữ liệu vào từ bàn phím..................................................................................................49PHỤ LỤC 1: DANH MỤC CÁC HÌNH ẢNH TRONG TÀI LIỆU.......................................................64I. GIỚI THIỆU BÀI TOÁN1. Tổng quan về đồ thị1.1. Đồ thị và các cách biểu diễn đồ thịĐồ thị là gì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ởi cá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ạn thẳng (các cạnh).Đồ thị biểu diễn được rất nhiều cấu trúc, nhiều bài toán thực tế có thể được biểu di ễn b ằngđồ thị. Ví dụ, cấu trúc liên kết của một website có thể được biểu di ễn bằng m ột đ ồ th ị cóhướng như sau: các đỉnh là các trang web hiện có tại website, tồn tại một c ạnh có h ướng n ốitừ trang A tới trang B khi và chỉ khi A có chứa 1 liên kết tới B.Cấu trúc đồ thị có thể được mở rộng bằng cách gán trọng số cho mỗi cạnh. Có th ể sử d ụngđồ thị có trọng số để biểu diễn nhiều khái niệm khác nhau. Ví dụ, nếu đồ thị bi ểu diễn mộtmạng đường giao thông, các trọng số có thể là độ dài của m ỗi con đ ường. M ột cách khác đ ểmở rộng đồ thị cơ bản là qui định hướng cho các cạnh của đồ thị (như đối với các trangweb, A liên kết tới B, nhưng B không nhất thiết cũng liên kết tới A). Loại đồ thị này được gọilà đồ thị có hướng. Một đồ thị có hướng với các cạnh có trọng số được gọi là một lưới. 2|PageAlgo2010N15-NguyenThiThanhVi-NgoVanVi-NhamNgocTrung-CNPMK52 Hình 01: Đồ thị vô hướngCác cách biểu diễn đồ thị - Ma trận kề (Adjaceny matrix) - một ma trận N × N, trong đó N là số đỉnh của đồ thị. Nếu có một cạnh nào đó nối đỉnh vivới đỉnh vj thì phần tử Mi,j bằng 1, nếu không, nó có giá trị 0. Cấu trúc này tạo thuận lợi cho vi ệc tìm các đ ồ th ị con và đ ể đ ảo các đ ồ thị. Labeled graph Adjacency matrix - Danh sách kề (Adjacency list) - Mỗi đỉnh của đồ thị có một danh sách các đỉnh k ề nó (nghĩa là có một cạnh nối từ đỉnh này đến m ỗi đ ỉnh đó). Trong đ ồ th ị vô h ướng, c ấu trúc này có thể gây trùng lặp. Chẳng hạn nếu đỉnh 3 n ằm trong danh sách c ủa đ ỉnh 2 thì đỉnh 2 cũng phải có trong danh sách của đỉnh 3. Lập trình viên có th ể ch ọn cách s ử 3|PageAlgo2010N15-NguyenThiThanhVi-NgoVanVi-NhamNgocTrung-CNPMK52 dụng phần không gian thừa, hoặc có thể liệt kê các quan hệ kề c ạnh ch ỉ m ột l ần. Biểu diễn dữ liệu này thuận lợi cho việc từ một đỉnh duy nh ất tìm m ọi đ ỉnh đ ược n ối với nó, do các đỉnh này đã được liệt kê tường minh. The graph pictured above has this adjacency list representation: a adjacent to b,c b adjacent to a,c c adjacent to a,b1.2. Các bài toán điển hình - Bài toán tập con độc lập - Bài toán tô mầu đồ thị - Bài toán tìm đường đi ngắn nhất - Bài toán luồng cực đại - Bài toán phủ tối thiểu - Kiểm tra tính liên thông của đồ thị - Duyệt đồ thị - …2. Bài toán tô mầu đồ thịTô màu đồ thị và sự tổng quát của nó là công cụ hữu dụng trong vi ệc mô hình hóa r ất nhi ềubài toán khác nhau trong vấn đề xếp lịch, xây dựng chương trình và v ấn đ ề phân công công 4|PageAlgo2010N15-NguyenThiThanhVi-NgoVanVi-NhamNgocTrung-CNPMK52việc. Bài toán tô màu đồ thị bao gồm nhiều loại: tô màu đỉnh đồ thị (vertex graph coloring) , tômàu cạnh đồ thị (edge graph coloring) ...2.1. Bài toán tô mầu cạnhBài toánCho G=(V,E) là đơn đồ thị vô hướng ( G không là đồ thị khuyên) , hãy tìm cách gán (tô màu)cho mỗi cạnh của đồ thị một màu sao cho hai cạnh có cùng chung 1 đ ỉnh không b ị tô b ởi cùngmột màu. Một phép gán màu cho các cạnh như vậy gọi là m ột phép tô màu c ạnh đ ồ th ị. Nóicách khác, phép tô cạnh đồ thị bởi k màu nói trên có thể được hi ểu là m ột phân ho ạch c ủa t ậpcạnh E của G thành k tập con (tương ứng với k màu) sao cho m ỗi t ập con ứng v ới m ột màu inhất định. Bài toán ...