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ị

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 MỤC LỤC GIỚI THIỆU BÀI TOÁN 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ối từ 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ột mạ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 trang web, 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ọi là đồ 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. Hình 01: Đồ thị vô hướng Cá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ử 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,b 1.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ị 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) ... 2.1. Bài toán tô mầu cạnh Bài toán Cho 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ùng mộ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ói cá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ập cạ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 i nhất định. Bài toán đặt ra là tìm cách tô màu nào sử dụng số màu ít nhất có thể. Ví dụ Đồ thị trong hình trên có thể tô bởi 4 màu. Đồ thị G gọi là tô được bởi k màu-cạnh nếu G có một phép tô k màu-cạnh phù hợp.Thông thường hầu hết các đồ thị không là đồ thị khuyên đều tô được.Và nếu G có tính chất như vậy thì G cũng có thể tô bởi l màu với l>k. 2.2. Bài toán tô mầu đỉnh Một phép tô mầu sử dụng nhiều nhất k mầu gọi là một phép tô k mầu. Số lượng mầu nhỏ nhất cần để tô các đỉnh của đồ thị G gọi là sắc số đỉnh của đồ thị G, sao cho không có hai đỉnh kề nhau nào được tô cùng mầu. Một đồ thị có thể tô được bằng k mầu, trong đó mỗi một tập các đỉnh cùng mầu gọi là một lớp mầu. Một đồ thị có thể được tô bằng k mầu nghĩa là có có k tập độc lập trong đồ thị 2.3. Các khái niệm liên quan Định nghĩa 1: Sắc số cạnh: của đồ thị không là đồ thị khuyên χ’(G): là số màu k nhỏ nhất dùng để tô tất cả các cạnh của G sao cho không có 2 cạnh kề cùng màu.Khi đó χ’(G)=k.Theo đồ thị G hình 1.1 ta có thể thấy không có cách nào phù hợp để tô G bởi 3 màu.Do đó G có sắc lớp=4. Các tính chất của sắc số cạnh: χ′(G) = 1 khi và chỉ khi đồ thị G chỉ có 1 bộ (mỗi bộ là 1 tập các cặp cạnh không kề nhau mà có thể tô bằng đúng 1 màu ). χ′(G) ≥ Δ(G). χ′(G) ≤ Δ(G) + 1. (Định lý Vizing) χ′(G) ≤ Δ(G) + μ(G), G là đa đồ thị. χ′(G) = Δ(G) nếu G là đồ thị 2 phía χ′(G) = Δ(G) nếu G là đơn đồ thị, phẳng và Δ(G) ≥ 7. (chứng minh bởi Vizing 1965 và Sanders & Zhao 2001) χ′(G) = Δ(G) với hầu hết các đồ thị (chứng minh bởi Erdős & Wilson 1977). Rõ ràng, trong tất cả các cách tô màu cạnh đồ thị thì những cạnh kề với cùng một đỉnh phải có màu khác nhau.Khi đó nếu gọi ∆ là giá trị lớn nhất trong tập bậc của đỉnh v ( ∆=maxdeg(v) ) thì hiển nhiên: Χ’(G) ≥ ∆ Từ nhận xét trên cộng với tính chất 3 của sắc số cạnh χ′(G) ta suy ra được nhận xét sau: Δ(G)≤ χ′(G) ≤ Δ(G) + 1 ( Công thức trên cũng là công thức biểu diễn của định lý Vizing mà chúng ta sẽ phát biểu dưới đây. Định lý Vizing: Bất kì một đơn đồ thị G nào cũng có số : χ’(G) thỏa mãn χ’(G)=∆ hoặc χ’=∆+1 Chứng minh: Vì chúng ta chỉ quan tâm đến nội dung của các định lý, lấy cơ sở cho việc xây dựng thuật toán giải quyết bài toán tô màu cạnh đồ thị. Do đó trong báo cáo này, tất cả những phần chứng minh các định lý các bổ để sẽ được trình bày ở phần phụ phía cuối báo cáo. Đến đây, chúng ta đã biết được sắc số cạnh của một đơn đồ thị biến thiên trong khoảng [Δ(G), Δ(G) +1] . Bài toán tô màu cạnh đồ thị đặt ra yêu cầu phải xác định một cách tô màu với số màu ít nhất có thể để tô màu tất cả các cạnh của đồ thị. Vậy trong hệ bất đẳng thức (1) khi nào bất đẳng thức bên trái xảy ra dấu bằng. Định lý 1: Nếu G là đồ thị 2 phía thì χ’(G) = ∆ 2.4. Ứng dụng - Bài toán lập lịch: Ở đây nhóm xin đưa ra một ví dụ cụ thể là bài toán lập lịch thi: hãy lập lịch thi trong một trường đại học sao cho không có sinh viên nào thi hai môn cùng một lúc Giải pháp: Biểu diễn bằng đồ thị với: Mỗi môn học là một đỉnh Nếu hai môn học nào được dự thi bởi cùng 1 sinh viên thì sẽ nối bằng 1 cạnh Các lập lịch sẽ tương ứng với bài toán tô mầu của đồ thị này: số các mầu được tô là số các đợt thi, các đỉnh có cùng mầu sẽ thi cùng 1 đợt. Ví dụ: Có 7 môn thi với thông tin như sau: Môn 1: có các sinh viên A, B, C và D thi Môn 2: có các sinh viên A, E, F, G và H thi Môn 3: có các sinh viên B, E, I, J và K thi Môn 4: có các sinh viên B, F, L và M thi Môn 5: có các sinh viên G, L, N và O thi Môn 6: có các sinh viên J, M, N và P thi Môn 7: có các sinh viên D, H, K, O và P thi Hãy xếp lịch thi thành các đợt sao cho các sinh viên đều có thể dự thi tuần tự các môn mình đăng ký Hình 02: Đồ thị G của bài toán lập lịch trên Bài toán phân phối các thanh ghi chỉ số (register allocation) Trong lập trình các thanh ghi thường được dung để lưu trữ giá trị các biến tạm thời. Bài toán yêu cầu tìm số thanh ghi ít nhất cần sử dụng trong một chương trình Giải pháp: Biểu diễn bằng đồ thị với: Mỗi biến tương ứng là 1 đỉnh Hai đỉnh được nối với nhau nếu hai biến cùng được ghi xuống tại một thời điểm Số thanh ghi ít nhất cần sử dụng sẽ là số mầu của đồ thị trên GIẢI THUẬT Bài toán tô mầu đỉnh Các định nghĩa sử dụng: Để mô tả giải thuật nhóm bắt đầu với việc diễn giải các thuật ngữ, định nghĩa mà giải thuật đề cập tới. ⌊x ⌋:  biểu thị các chức năng sàn tức là số nguyên lớn nhất không lớn hơn x ⌈ x⌉:  biểu thị chức năng  trần nghĩa là số nguyên bé nhất là không bé hơn x Một đồ thị đơn giản G với n đỉnh bao gồm một tập các đỉnh V,với | V |= n, và một bộ các cạnh E, sao cho mỗi cạnh là một cặp không có thứ tự của các đỉnh khác nhau. Lưu ý rằng định nghĩa của G rõ ràng cấm các vòng lặp(cạnh nối một đỉnh với chính nó) và các cạnh đa (nhiều cạnh tham gia một cặp đỉnh), khi thiết lập E cũng phải được giới hạn. Chúng tôi có thể gán nhãn các đỉnh của G với 1 số nguyên, 2, ..., n. Nếu các cặp không có thứ tự của các đỉnh {u, v} là một cạnh trong G, chúng ta nói u đó là một lân cận của v (hoặc u kề với v) và viết uv ∈ E. Lân cận đối xứng rõ ràng là một mối quan hệ: uv ∈ E nếu và chỉ nếu vu ∈ E . Bậc của một đỉnh v, ký hiệu là d (v), là số lân cận của v. Số bậc tối đa của tất cả các đỉnh của G được ký hiệu là Δ.  Các ma trận kề của G là một ma trận n × n  với các mục trong  hàng u và cột v bằng 1 nếu uv ∈ E và bằng 0 nếu ngược lại.  Cho đồ thị G và H, tích đề các G × H được định nghĩa là các đồ thị mà tập các đỉnh là V (G) × V (H)với một cạnh  đang kết nối đỉnh (u 1, v 1) với đỉnh (u 2, v 2) nếu và chỉ nếu hoặc u 1 = u 2 và {v 1, v 2} là một cạnh trong H hoặc v 1 = v 2 và {u 1, u 2} là một cạnh trong G. Đồ thị đầy đủ với m đỉnh được ký hiệu là K m.  Tập độc lập S của đồ thị G là một tập các đỉnh như vậy mà không chứa cặp không có thứ tự của các đỉnh trong S là một cạnh. Với một bộ độc lập S củaG và một đỉnh v bên ngoài S, chúng ta nói v là có thể thêm vào nếu đặt S∪ {v} vẫn là một tập độc lập của G. Ký hiệu ρ (S) là số đỉnh có thể thêm vào của một tập độc lập S của G. Một tập độc lập tối đa không có đỉnh có thể thêm vào. Một tập độc lập tối đa là một tập độc lập với số lượng các đỉnh lớn nhất. Lưu ý rằng một tập độc lập tối đa luôn luôn là tối đa, nhưng không nhất thiết phải ngược lại. Cho một tập m màu {1, 2, ..., m}, một tập m-màu của các đỉnh của đồ thị G là sự phân một màu duy nhất cho mỗi đỉnh của G sao cho không có hai đỉnh kề nhau có cùng màu. Số màu χ(G) của đồ thị G là giá trị nhỏ nhất của m mà tồn tại tương ứng một một m-màu của các đỉnh củaG.  Thuật toán là một phương pháp giải quyết vấn đề thích hợp để thực hiện như một chương trình máy tính. Trong khi thiết kế thuật toán chúng ta thường phải đối mặt với một số phương pháp tiếp cận khác nhau.  Thuật toán thời gian - đa thức A có số lượng các bước tính toán luôn luôn bị chặn bởi một hàm đa thức của các kích thước của đầu vào. Do đó, một thuật toán thời gian đa thức là một vấn đề thực sự hữu ích trong thực tế. Các lớp của tất cả các vấn đề như vậy có thuật toán thời gian đa thức được ký hiệu là P. Đối với một số vấn đề, không có thuật toán thời gian đa thức được biết đến, nhưng những vấn đề này có thuật toán thời gian đa thức bất định: hãy thử tất cả các ứng viên cho các giải pháp cùng một lúc và cho mỗi ứng viên nhất định, xác minh xem đó là một giải pháp chính xác trong thời gian đa thức. Thuật toán Nhóm bắt đầu với tích Đề Các cho phép chúng ta chuyển đổi các vấn đề của việc tìm kiếm một tập m-màu của các đỉnh n của một đồ thị tương đương như việc tìm kiếm một bộ độc lập kích thước n trong tích đề các G × Km . Tích Đề Các Một đơn đồ thị G với n đỉnh là tô được bằng m mầu khi và chỉ khi tích đề các G × K m có một tập độc lập kích thước n. Chứng minh. Giả sử có một tập m-màu của các đỉnh của G. Xác định một tập con S của các đỉnh của tích đề các G × K m như sau. Một đỉnh (u, v) của G × Km thuộc S nếu và chỉ nếu đỉnh u  của G được giao màu v đối với tập m màu thích hợp. Vì mỗi đỉnh của G được giao một màu duy nhất, | S | = n. Bây giờ chúng ta sẽ chỉ ra rằng S là một tập độc lập.  Cho (u 1, v 1) và (u 2, v 2) thuộc S, giả sử có một cạnh {(u 1, v 1), (u 2, v 2)} trong G × K m. Do đó, theo định nghĩa của tích đề các, có hai khả năng: u 1 = u 2 và {v 1, v 2} là một cạnh trong K m. Nhưng u 1 = u 2 với v 1 = v2, từ mỗi đỉnh trong G đượcgiao một màu duy nhất. Nhưng sau đó {v 1, v1} không thể là một cạnh trong K m  khi K m là một đơn đồ thị (mâu thuẫn). {U 1, u 2} là một cạnh trong G, và v 1 = v 2. Nhưng điều này vi phạm các định nghĩa của một tập m màu của G từ đỉnh kề phải được giao các màu khác nhau (mâu thuẫn). Vì vậy không thể có một cạnh giữa hai đỉnh trong S và S phải là một tập độc lập.  Ngược lại, giả sử có một tập độc lập S kích thước n trong tích đề các G × K m. Chúng ta sẽ chỉ ra rằng G có m màu riêng biệt. Nếu m lớn hơn hoặc bằng n thì G có thể được m màu một cách tầm thường , do đó giả sử m nhỏ hơn n. Sự phân chia các đỉnh của S vào nhiều nhất là m lớp tương đương C 1, C 2 ,..., C m, nơi một đỉnh (u, v) trong S thuộc về lớp  tương đương C i khi và chỉ khi v = v i. Rõ ràng , điều này đưa ra một định nghĩa phân chia tốt của các đỉnh trong S. Bây giờ các đỉnh của G vào nhiều nhất là m lớp tương đương C '1, C' 2, ..., C'm, nơi một u đỉnh của G thuộc lớp tương đương C 'i nếu và chỉ nếu (u, v i) thuộc về lớp tương đương C i. Để chứng tỏ điều đó ta đưa ra một định nghĩa phân chia tốt của các đỉnh các đỉnh của G tuân theo: Cho một đỉnh u của G, nếu u thuộc về cả hai C 'i và C' j thì (u, v i) thuộcC i và (u, v j) thuộc C j. Khi K mđầy đủ, {v i, v k} là một cạnh trong K m, do đó, {(u, v i), (u, v j)} là một cạnh trong tích đề các G ×K m. Điều này mâu thuẫn với thực tế là S là một tập độc lập .Vì vậy, các bộ C '1, C' 2 ,..., C 'm là cặp phân chia. Danh sách các phần tử của S sắp xếp như sau: (U 1 1, v 1), (u 1 2, v 1), ..., (u 1 i (1), v 1) (U 2 1, v 2), (u 2 2, v 2), ..., (u 2 i (2), v 2) ... (U m 1, v m), (u m 2, v m), ..., (u m i (m), m v) Nếu một số u i j = l k u trong danh sách, thì, khi K m đầy đủ, {v i, v l} là một cạnh trong K m, do đó, {(u i j, v i), (u k l , v l)} là một cạnh trong tích đề các G × K m. Điều này mâu thuẫn với thực tế S là một tập độc lập. Vì vậy, tất cả các u i j xuất hiện trong danh sách là riêng biệt và từ | S | = n , có n u i j i phân biệt mọi đỉnh của G được chứa trong một số lớp tương đương 'C Do đó,.. Chỉ định màu i đến đỉnh u của G nếu u thuộc về các lớp tương đương C i' . Điều này tạo ra một tập m-màu của các đỉnh của G.  Bây giờ chúng ta định nghĩa hai thủ tục để thực hiện với tập độc lập trong tích đề các G × K m. Thủ tục 1  Với một tập độc lập S của tích đề các G×Km nếu S không có đỉnh có thể thêm, đầu ra S. Ngược lại, cho mỗi đỉnh có thể thêm (u, v) của S, tìm số ρ (S∪ {(u, v)}) của đỉnh có thể thêm của tập độc lập S ∪ {(u, v)}. Cho (u,v ) max  biểu thị một đỉnh có thể thêm sao cho ρ (S ∪ {(u, v) max}) là lớn nhất và chứa tập độc lập S ∪ {(u, v) max}. Lặp lại cho đến khi tập độc lập không có đỉnh có thể thêm vào. Thủ tục 2 Cho một tập độc lập tối đa S của tích đề các G × K m, nếu không có đỉnh (u 1, v 1) bên ngoài S sao cho (u 1, v 1) có đúng một lân cận (u 2, v 2 ) trong S, đầu ra S.Ngược lại, tìm thấy một đỉnh (u 1, v 1) ngoài S sao cho (u 1, v 1) có đúng một lân cận (u 2, v 2) trong S 1. Xác định S(u1, v1), (u2, v2) bằng cách thêm (u1, v1) vào S và bỏ (u 2, v 2) từ S. Thực hiện thủ tục 3.1 trên S (u 1, v 1), (u 2, v 2) và đầu ra các tập độc lập kết quả. Giải thuật Với đầu vào là một đơn đồ thị G với n đỉnh, tìm kiếm một tập m-màu của các đỉnh của G. Để {u 1, u 2, ..., u n} biểu thị các đỉnh của G và để {v1, v 2, ..., v m} biểu thị các đỉnh của K m.. Chúng ta tạo các tập độc lập tối đa trong tích đề các G×Km. Ở mỗi giai đoạn, nếu tập độc lập thu được có kích thước n nhỏ nhất, thì đi đến phần III. Phần I. Đối với i = 1, 2, ..., n và j = 1, 2, ..., n lần lượt Khởi tạo tập độc lập S i, j = {(u i, v j)}. Thực hiện thủ tục 3.1 trên S i, j. Đối với r = 1, 2, ..., n thực hiện thủ tục 3.2 lặp lại r lần. Kết quả là một tập độc lập tối đa S i, j. Phần II. Với mỗi cặp tập độc lập tối đa S i, j, S k, l tìm thấy trong phần I Khởi tạo S đặt độc lập i, j, k, l = S i, j ∩ S k, l. Thực hiện thủ tục 3,1 trên S i, j, k, l. Đối với r = 1, 2, ..., n thực hiện thủ tục 3,2 lần r lặp đi lặp lại. Kết quả là một tập độc lập tối đa S i, j, k, l. Phần III. Nếu một tập độc lập S với kích thước n đã được tìm thấy tại bất kỳ giai đoạn của phần I hoặc phần II, đầu ra S như là một tập m-màu của các đỉnh của G theo Bổ đề Đề các. Ngược lại, kết luận thuật toán không thể tìm thấy bất kỳ tương ứng m-màu của các đỉnh của G. Ví dụ Chúng ta thể hiện các bước của thuật toán bằng một ví dụ nhỏ. Đồ thị đầu vào được thể hiện dưới đây trong hình 3.1 với n = 4 đỉnh có nhãn V = {1, 2, 3, 4}. Các thuật toán tìm kiếm cho một tương ứng 3- màu của các đỉnh bằng cách sử dụng các thiết lập của các màu {1, 2, 3} đại diện bởi màu xanh lá cây, đỏ và màu xanh tương ứng.  Hình 03. Các đồ thị đầu vào G với 3- màu tương ứng của các đỉnh của nó được tìm thấy bởi thuật toán Thuật toán đầu tiên xây dựng tích đề các G × K 3 hiển thị dưới đây trong các con số 3,2 với 12 đỉnh {(1,1), (1,2), (1,3), (2,1), (2,2), (2,3), (3,1), (3,2), (3,3), (4,1), (4,2), (4,3)}. Chúng ta tách các đỉnh {1, 2, 3} của thành phần thứ hai K 3 như các màu sắc xanh, đỏ và màu xanh tương ứng.  Hình 04: tích đề các G × K 3 với một tập độc lập với kích thước 4 được  tìm thấy bằng thuật toán Thuật toán bây giờ tìm kiếm một tập độc lập với kích thước 4 trong tích đề các G × K 3. Phần I cho i = 1 và j = 1 khởi tạo tập độc lập như S 1,1 = {(1, 1)}. Bây giờ chúng ta thực hiện các thủ tục 1. Sau đây là các kết quả dưới dạng bảng:  Tập độc lập S 1,1 = {(1, 1)}. Kích thước: 1. Đỉnh có thể thêm (u, v) củaS 1,1 Đỉnh có thể thêm của S 1,1 ∪{(u, v)} ρ (1,1 S ∪ {(u, v)}) (2, 2) (3, 3), (4, 2), (4, 3) 3 (2, 3) (3, 2), (4, 2), (4, 3) 3 (3, 2) (2, 3), (4, 3) 2 (3, 3) (2, 2), (4, 2) 2 (4, ) (2, 2), (2, 3), (3, 3) 3 (4, 3) (2, 2), (2, 3), (3, 2) 3 Tối đa ρ (1,1 S ∪ {(u, v)}) = 3 cho (v, u) = (2, 2). Thêm đỉnh (2, 2) vào S 1,1. Tập độc lập  S 1,1 = {(1, 1), (2, 2)}. Kích thước: 2. Đỉnh có thể thêm (u, v) củaS 1,1 Đỉnh có thể thêm của S 1,1 ∪{(u, v)} ρ (1,1 S ∪ {(u, v)}) (3, 3) (4, 2) 1 (4, 2) (3, 3) 1 (4, 3) Không ai 0 Tối đa ρ (1,1 S ∪ {(u, v)}) = 1 cho (v, u) = (3, 3). Thêm đỉnh (3, 3) vào S 1,1. Tập độc lập  S 1,1 = {(1, 1), (2, 2), (3, 3)}:. Kích thước 3. Đỉnh có thể thêm (u, v) củaS 1,1 Đỉnh có thể thêm của S 1,1 ∪{(u, v)} ρ (1,1 S ∪ {(u, v)}) (4, 2) Không ai 0 Tối đa ρ (1,1 S ∪ {(u, v)}) = 0 với (v, u) = (4, 2). Thêm đỉnh (4, 2) để S 1,1. Chúng ta có được một tập độc lập tối đa S 1,1 = {(1, 1), (2, 2), (3, 3), (4, 2)} của  kích thước yêu cầu n  = 4. Bây giờ đầu ra phần III S 1,1 được yêu cầu đúng 3-màu của đầu vào đồ thị G  và thuật toán kết thúc. Lưu ý rằng chúng ta giải thích kết quả như sau: đỉnh 1 được tô với màu 1 (màu xanh), đỉnh 2 được tô với màu 2 (màu đỏ), đỉnh 3 được tô với màu 3 (màu xanh) và đỉnh 4 được tô với màu 2 ( màu đỏ). Độ phức tạp: Tiếp theo để đánh giá độ phức tạp của giải thuật, nhóm sẽ chỉ ra rằng thuật toán kết thúc trong thời gian đa thức, trong khi tìm kiếm một tập m-màu cho một đồ thị với n đỉnh, bằng cách xác định một đa thức của N=nm đó là một cận trên trên tổng số bước tính toán thực hiện bởi thuật toán.Lưu ý rằng chúng ta xem xét kiểm tra xem một cặp của các đỉnh được kết nối bởi một cạnh trong G, và so sánh xem một số nguyên cho trước nhỏ hơn một số nguyên cho trước được tính toán các bước cơ bản. Mệnh Đề 1  Cho một đồ thị đơn giản G với n đỉnh và một tập độc lập S của G×Km , thủ tục 1 mất ít nhất (nm) 5 bước. Chứng minh  Kiểm tra việc một đỉnh riêng có thể thêm thì mất tối đa (nm) 2 bước, từ đỉnh có ít hơn các lân cận nm và cho mỗi lân cận phải mất ít hơn nm bước để kiểm tra xem nó là ở ngoài tập độc lập. Đối với một tập độc lập riêng, việc tìm kiếm số ρ của các đỉnh có thể thêm mất ít nhất (nm) 3 = (nm) (nm) 2 bước, khi nhiều nhất nm đỉnh bên ngoài tập độc lập chúng ta phải kiểm tra xem nó có thể thêm hay không. Đối với một tập độc lập riêng, việc tìm kiếm một đỉnh sao cho ρ là tối đa thì mất ít nhất (nm) 4 = (nm) (nm) 3 bước, khi có hầu hết nm đỉnh bên ngoài. Thủ tục 1 kết thúc khi hầu hết nm đỉnh được thêm, do đó phải mất một tổng của hầu hết (nm) 5 = (nm) (nm) 4bước.  Mệnh Đề 2  Cho một đơn đồ thị G với n đỉnh  và một tập độc lập tối đa S của G×Km , thủ tục 2 mất ít nhất (nm) 5 +(nm) 2 +1 bước. Chứng minh  Để tìm một đỉnh (u 1, v 1) bên ngoài S mà có đúng một lân cận (u 2, v 2) bên trong S có tối đa (nm) 2 bước, khi có ít hơn nm đỉnh ngoài S và chúng ta phải tìm ra nếu ít nhất một trong các lân cận bé hơn nm của bất kỳ đỉnh nào ở trong S. Nếu như một đỉnh (u 1, v 1) đã được tìm thấy, phải mất một bước để hoán đổi  (u 1, v 1) và  (u 2, v 2).  Sau đó, bằng mệnh đề 4.1, phải mất ít nhất (nm) 5 bước để thực hiện các thủ tục 1 vào tập độc lập kết quả. Như vậy, thủ tục 2 mất ít nhất (nm) 2 +1 + (nm) 5 bước.  Mệnh Đề 3 Cho một đơn đồ thị G với n đỉnh và m màu, phần I của thuật toán có tối đa  (nm) 7 + (nm) 6 + (nm) 4+ (nm) 2 bước. Chứng minh  Tại mỗi lượt, thủ tục 1 mất ít nhất (nm) 5 bước bằng mệnh đề 1. Sau đó, thủ tục 2 được thực hiện tối đa nm lần mà theo mệnh đề 2, mất tối đa nm((nm) 5 + (nm) 2+1) = (nm) 6 + (nm)3 + nm bước .Vì vậy, tại mỗi lượt, tối đa (nm) 5 + (nm) 6 + (nm) 3 + nm bước được thực hiện. Có nm lượt cho i = 1, 2, ..., n, và j = 1, 2, ..., m, do đó, một phần I thực hiện tổng cộng tối đa là nm((nm) 5 + (nm) 6 + (nm) 3 +nm) = (nm) 6 + (nm) 7 + (nm) 4 + (nm) 2 bước.  Mệnh Đề 4  Cho một đơn đồ thị G với n đỉnh và m màu, thuật toán mất ít hơn (nm) 8 +2 (nm) 7 + (nm) 6 + (nm) 5 +(nm) 4 + (nm) 3 + (nm) 2 bước để kết thúc. Chứng minh  Có ít hơn (nm) 2 cặp riêng biệt của tập độc lập tối đa được tìm thấy bởi phần I, mà được thực hiện lần lượt. Tương tự như các thực nghiệm về mệnh đề 3, phần II có ít hơn(nm) 2 nm (() 5 nm (+ ) 6 + (nm) 3 + nm) = (nm) 7 + (nm) 8 +(nm) 5 + (nm) 3). Do đó, phần I và phần II cùng nhau mất ít hơn tổng cộng của ((nm 7 + (nm) 6 + (nm) 4 + (nm) 2) + ((nm) 8 +(nm) 7 + (nm) 5 + (nm) 3) = (nm) 8 +2 (nm) 7 + (nm) 6 + (nm) 5+ (nm) 4 + (nm) 3 + (nm) 2 bước để kết thúc. Bài toán tô mầu cạnh Giải thuật Về thuật toán giải quyết bài toán tô màu cạnh đồ thị hiện nay trên thế giới có nhiều thuật toán được đề suất như Thuật toán thu gọn (Contraction algorthms) được đề xuất bởi Zykov Thuật toán tô màu theo dãy (sequential coloring). Trong đó thuật toán tô màu theo dãy lại được ứng dụng theo nhiều cách khác nhau. Ý tưởng của thuật toán này xoay quanh việc sắp xếp thứ tự các cạnh của đồ thị theo một thứ tự nhất định. Đánh trọng số cho các màu được dung để tô. Sau đó duyệt các cạnh theo thứ tự nêu trên. Trong quá trình duyệt sẽ tô màu cho cạnh bằng màu có trọng số nhỏ nhất mà chưa được sử dụng để tô cho các cạnh kề. Đây là một vận dụng của sử dụng thuật toán tham lam. Kết quả của bài toán khác nhau nếu chúng ta chọn được thứ tự của các cạnh khác nhau. Do đó các cải tiến hay các thuật toán khác nhau dựa trên thuật toán này hầu hết đều là cải tiến việc lựa chọn thứ tự cho các cạnh ban đầu. Trong chương trình ứng dụng của nhóm, giải thuật đưa ra ở mức minh hoạ một cách tô màu cạnh của đồ thị vô hướng. Trong đó, việc xếp thứ tự của đỉnh được đồng nghĩa với thứ tự các đỉnh được sắp xếp của đầu vào. Do đó thuật toán được thu gọn như sau : Thứ tự các cạnh được sắp xếp trong quá trình nhập dữ liệu về đồ thị. Các cạnh được đánh số theo thứ tự E1, E2, ...,En. Tìm bậc lớn nhất của đồ thị (Δ) Chuẩn bị (Δ+1) màu để tô Bước i: Tô màu cạnh Ei bởi màu có chỉ số nhỏ nhất trong số các màu chưa được sử dụng để tô màu cạnh kề của nó. Trong đó ở bước i tùy theo cách cài đặt sẽ có những cách đánh màu khác nhau. Với thuật toán trên chúng ta có thể tìm được 1 cách tô màu cho các cạnh của đồ thị với số màu không quá Δ+1 màu ( vấn đề này sẽ thấy rõ hơn khi đi sâu vào phần cài dặt). Vậy đó đã là số màu nhỏ nhất hay chưa. Theo định lý Vizing chúng ta phát biểu ở trên, ta có Δ(G)≤ χ′(G) ≤ Δ(G) + 1. Vậy sắc số cạnh chỉ có thể nằm ở 1 trong hai giá trị là Δ(G) và Δ(G) + 1. Với việc chọn số màu lớn nhất có thể tô là Δ(G)+1, thuật toán đã kẹp được cận trên của sắc số cạnh. Với việc lựa chọn màu có chỉ số nhỏ nhất chưa được sử dụng để tô các cạnh kề cho một cạnh, số màu được sử dụng là số màu nhỏ nhất. Ví dụ Ta có đồ thị sau: Ta sắp xếp các cạnh theo thứ tự như sau: Bước 1: tô màu cạnh thứ 1 Cạnh này tô màu đỏ trước tiên Bước 2: tô màu cạnh 2. Cạnh 2 kề với cạnh 1 (tô màu đỏ) do đó cạnh 2 sẽ tô màu xanh lá cây Bước 3: tô màu cạnh 3 Cạnh 3 kề với cạnh 1 (tô màu đỏ), cạnh 2 (tô màu xanh lá cây) do đó cạnh 3 phải tô màu xanh da trời Bước 4: tô màu cạnh 4 Cạnh 4 kề với cạnh 1 (tô màu đỏ) nên sẽ tô màu xanh lá cây Bước 5: tô màu cạnh 5 Cạnh 5 kề với cạnh 3 (tô màu xanh da trời), cạnh 4 (tô màu xanh lá cây) nên cạnh 5 tô màu đỏ Bước 6: tô màu cạnh 6 Cạnh 6 kề với cạnh 1,5 (tô màu đỏ), cạnh 3 (tô màu xanh da trời), cạnh 4 (tô màu xanh lá cây) nên cạnh 6 phải tô màu tím Bước 7: tô màu cạnh 7 Cạnh 7 kề với cạnh 2 (tô màu xanh lá cây), cạnh 3 (tô màu xanh da trời), cạnh 5 (tô màu đỏ), cạnh 6 (tô màu tím) do đó cạnh này tô màu vàng Bước 8: tô màu cho cạnh thứ 8 Cạnh 8 kề với cạnh 5 (tô màu đỏ), cạnh 7 (tô màu vàng) nên sẽ tô màu xanh lá cây Bước 9: tô màu cạnh 9 Cạnh 9 kề với cạnh 4 (tô màu xanh lá cây), cạnh 5 (tô màu đỏ) nên sẽ tô màu xanh da trời Kết luận: Đồ thị này có thể tô được với 5 màu. Mặt khác Δ = 5 nên đây chính là số màu nhỏ nhất có thể dùng để tô cạnh của đồ thị trong trường hợp này. Độ phức tạp: Độ phức tạp của giải thuật là: O (E+V2) CÀI ĐẶT THUẬT TOÁN Trong phần cài đặt này bài toán tô mầu cạnh có 2 cách nhập dữ liệu (bằng file và nhập từ bàn phím), bài toán tô mầu đỉnh cho phép nhập dữ liệu từ file. Menu chương trình hiển thị các lựa chọn nhập dữ liệu: 1. Bài toán tô mầu đỉnh - Cài đặt: Đọc dữ liệu từ file: graph.txt Kết quả sẽ trả ra ở file: coloring.txt Mã nguồn chương trình Bool removable(vector neighbor, vector cover);  int max_removable(vector > neighbors, vector cover);  vector procedure_1(vector > neighbors, vector cover);  vector procedure_2(vector > neighbors, vector cover, int k);  int cover_size(vector cover);  ifstream infile ( "graph.txt" );  ofstream outfile ( "coloring.txt" ); int main() //hàm chính {    //Read Graph    cout<< "Vertex Coloring Algorithm." <<endl;  int C, N, n, i, j, k, K, p, q, r, s, min, edge, counter= 0 ;  infile>>N;  vector > Graph;  for (i= 0 ; i<N; i++)  {  vector row;  for (j= 0 ; j<N; j++)  {  infile>>edge;  row.push_back(edge);  }  Graph.push_back(row);  }    //COLORING to INDEPENDENT SET conversion    cout<< "Graph has N = " <<N<< " vertices." <<endl; cout<< "Find a vertex coloring using at most C colors. Enter C = " ;  cin>>C;    //Complete garph on C verteices    vector > KC;  vector row1;  for ( int i= 0 ; i<C; i++) row1.push_back( 1 );  for ( int i= 0 ; i<C; i++) KC.push_back(row1);  for ( int i= 0 ; i<C; i++) KC[i][i]= 0 ;    //Cartesian product of Graph and KC    vector > graph;  vector rowind;  for ( int i= 0 ; i<C*N; i++) rowind.push_back( 0 );  for ( int i= 0 ; i<C*N; i++) graph.push_back(rowind);  for ( int i= 0 ; i<C*N; i++)  for ( int j= 0 ; j<C*N; j++)  {  int i_G=i/C, i_KC=i%C, j_G=j/C, j_KC=j%C;  if ((i_G==j_G) && (KC[i_KC][j_KC]== 1 )) graph[i][j]= 1 ;  if ((Graph[i_G][j_G]== 1 ) && (i_KC==j_KC)) graph[i][j]= 1 ;  }    //Assign parameters for finding independent sets in the graph    n=N*C; K=n/C; k=nK;    //Find Neighbors    vector > neighbors;  for (i= 0 ; i<graph.size(); i++)  {  vector neighbor;  for (j= 0 ; j<graph[i].size(); j++)  if (graph[i][j]== 1 ) neighbor.push_back(j);  neighbors.push_back(neighbor);  }   //Find Independent Sets    bool found= false ;  cout<< "Finding Vertex Colorings..." <<endl;  min=n+ 1 ;  vector > covers;  vector allcover;  for (i= 0 ; i<graph.size(); i++)  allcover.push_back( 1 );  for (i= 0 ; i<allcover.size(); i++)  {  if (found) break ;  counter++; cout<<counter<< ". " ;  outfile<<counter<< ". " ;  vector cover=allcover;  cover[i]= 0 ;  cover=procedure_1(neighbors,cover);  s=cover_size(cover);  if (s<min) min=s;  if (s<=k)  {  outfile<< "Vertex Coloring (" <<ns<< "): " ;  for (j= 0 ; j<cover.size(); j++) if (cover[j]== 0 ) outfile<< "(" <<j/C+ 1 << "," <<j%C+ 1 << ") " ;  outfile<<endl;  cout<< "Vertex Coloring Size: " <<ns<<endl;  covers.push_back(cover);  found= true ;  break ;  }  for (j= 0 ; j<nk; j++)  cover=procedure_2(neighbors,cover,j);  s=cover_size(cover);  if (s<min) min=s;  outfile<< "Vertex Coloring (" <<ns<< "): " ;  for (j= 0 ; j<cover.size(); j++) if (cover[j]== 0 ) outfile<< "(" <<j/C+ 1 << "," <<j%C+ 1 << ") " ;  outfile<<endl;  cout<< "Vertex Coloring Size: " <<ns<<endl;  covers.push_back(cover);  if (s<=k){ found= true ; break ; }  }  //Pairwise Intersections    for (p= 0 ; p<covers.size(); p++)  {  if (found) break ;  for (q=p+ 1 ; q<covers.size(); q++)  {  if (found) break ;  counter++; cout<<counter<< ". " ;  outfile<<counter<< ". " ;  vector cover=allcover;  for (r= 0 ; r<cover.size(); r++)  if (covers[p][r]== 0 && covers[q][r]== 0 ) cover[r]=0 ;  cover=procedure_1(neighbors,cover);  s=cover_size(cover);  if (s<min) min=s;  if (s<=k)  {  outfile<< "Vertex Coloring (" <<ns<< "): " ;  for (j= 0 ; j<cover.size(); j++) if (cover[j]== 0 ) outfile<< "(" <<j/C+ 1 << "," <<j%C+ 1 << ") " ;  outfile<<endl;  cout<< "Vertex Coloring Size: " <<ns<<endl;  found= true ;  break ;  }  for (j= 0 ; j<k; j++)  cover=procedure_2(neighbors,cover,j);  s=cover_size(cover);  if (s<min) min=s;  outfile<< "Vertex Coloring (" <<ns<< "): " ;  for (j= 0 ; j<cover.size(); j++) if (cover[j]== 0 ) outfile<< "(" <<j/C+ 1 << "," <<j%C+ 1 << ") " ;  outfile<<endl;  cout<< "Vertex Coloring Size: " <<ns<<endl;  if (s<=k){ found= true ; break ; }  }  }  if (found) cout<< "Found complete Vertex Coloring using at most " <<C<< " colors." <<endl;  else cout<< "Could not find complete Vertex Coloring using at most " <<C<< " colors." <<endl  << "Maximum partial Vertex Coloring found for " <<n-min<< " vertices." <<endl;  cout<< "See coloring.txt for results." <<endl;  system( "PAUSE" );  return 0 ;  } bool removable(vector neighbor, vector cover)  {  bool check= true ;  for ( int i= 0 ; i<neighbor.size(); i++)  if (cover[neighbor[i]]== 0 )  {  check= false ;  break ;  }  return check;  } int max_removable(vector > neighbors, vector cover)  {  int r=- 1 , max=- 1 ;  for ( int i= 0 ; i<cover.size(); i++)  {  if (cover[i]== 1 && removable(neighbors[i],cover)==true )  {  vector temp_cover=cover;  temp_cover[i]= 0 ;  int sum= 0 ;  for ( int j= 0 ; j<temp_cover.size(); j++)  if (temp_cover[j]== 1 && removable(neighbors[j], temp_cover)== true )  sum++;  if (sum>max)  {  max=sum;  r=i;  }  }  }  return r;  } vector procedure_1(vector > neighbors, vector cover)  {  vector temp_cover=cover;  int r= 0 ;  while (r!=- 1 )  {  r= max_removable(neighbors,temp_cover);  if (r!=- 1 ) temp_cover[r]= 0 ;  }  return temp_cover;  } vector procedure_2(vector > neighbors, vector cover, int k)  {  int count= 0 ;  vector temp_cover=cover;  int i= 0 ;  for ( int i= 0 ; i<temp_cover.size(); i++)  {  if (temp_cover[i]== 1 )  {  int sum= 0 , index;  for ( int j= 0 ; j<neighbors[i].size(); j++)  if (temp_cover[neighbors[i][j]]== 0 ) {index=j; sum++;}  if (sum== 1 && cover[neighbors[i][index]]== 0 )  {  temp_cover[neighbors[i][index]]= 1 ;  temp_cover[i]= 0 ;  temp_cover=procedure_1(neighbors,temp_cover);  count++;  }  if (count>k) break ;  }  }  return temp_cover;  } int cover_size(vector cover)  {  int count= 0 ;  for ( int i= 0 ; i<cover.size(); i++)  if (cover[i]== 1 ) count++;  return count;  } Hướng dẫn sử dụng Đồ thị 2 phía K (3,3): Chúng ta chạy chương trình trên đồ thị hai phía Kuratowski K 3, 3 với n = 6 đỉnh. Thuật toán tìm được đúng m-màu của các đỉnh cho m = χ( G ) = 2.  graph.txt 6  0 0 0 1 1 1  0 0 0 1 1 1  0 0 0 1 1 1  1 1 1 0 0 0  1 1 1 0 0 0  1 1 1 0 0 0 coloring.txt Vertex Coloring ( 6 ): ( 1 , 1 ) ( 2 , 1 ) ( 3 , 1 ) ( 4 , 2 ) ( 5 , 2 ) ( 6 , 2 ) Hình 05: Đồ thị hai phía Kuratowski K 3, 3 với tập đúng m-màu ( n = 6, m = χ( G ) = 2 ).  b. Đồ thị Octahedron Chúng ta chạy chương trình trên đồ thị Octahedron với n = 6 đỉnh. Thuật toán tìm được đúng m-màu của các đỉnh cho m = χ (G) = 3. graph.txt 6  0 1 1 0 1 1  1 0 1 1 0 1  1 1 0 1 1 0  0 1 1 0 1 1  1 0 1 1 0 1  1 1 0 1 1 0 coloring.txt Vertex Coloring ( 6 ): ( 1 , 1 ) ( 2 , 2 ) ( 3 , 3 ) ( 4 , 1 ) ( 5 , 2 ) ( 6 , 3 ) Hình 05: Đồ thị Octahedron với tập đúng m-màu ( n = 6, m = χ( G ) = 3 ) c. Đồ thị Bondy-Murty G 1 Chúng ta chạy chương trình trên đồ thị Bondy-Murty G 1 với n = 7 đỉnh. Thuật toán tìm được đúng m-màu của các đỉnh cho m = χ (G) = 4. graph.txt 7  0 1 1 0 1 1 0  1 0 1 1 0 1 0  1 1 0 1 1 0 0  0 1 1 0 0 0 1  1 0 1 0 0 0 1  1 1 0 0 0 0 1  0 0 0 1 1 1 0 coloring.txt Vertex Coloring ( 7 ): ( 1 , 1 ) ( 2 , 2 ) ( 3 , 3 ) ( 4 , 1 ) ( 5 , 2 ) ( 6 , 3 ) ( 7 , 4 ) Hình 06: Đồ thị Bondy-Murty G 1 với tập đúng m-màu ( n = 7, m = χ( G ) = 4 ) 2. Bài toán tô mầu cạnh 2.1. Đọc dữ liệu từ file Cài đặt Đọc dữ liệu từ File văn bản .txt ,file .txt có cấu trúc dạng Dòng đầu là số đỉnh, các dòng tiếp theo dòng thứ i là các đỉnh kể với đỉnh i. Với ví dụ minh họa ở phần trước Ta sẽ có file .txt dạng 7 0 1 0 1 1 0 0 1 0 1 1 0 0 0 0 1 0 1 0 0 0 1 1 1 0 1 0 1 1 0 0 1 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 Dữ liệu được đọc từ file được lưu vào mảng 2 chiều a. Khởi tạo các giá trị ban đầu cho màu với giá trị mã nhỏ nhất là 2 Tìm bậc lớn nhất của đồ thị (Δ) Chuẩn bị (Δ+1) màu để tô Tô màu các cạnh: Tại bước thứ i: +) Với các đỉnh j kề với i trong danh sách đã được xây dựng ở trên +)A[i][j] = t (t>1) tức là cạnh [I,j] được tô bởi màu có mã là t +)A[i][j] = 1 tức là có cạnh [i,j] và cạnh [I,j] chưa được tô Khi tô cạnh i,j ta xét đỉnh i và đỉnh j Ta tất cả các cạnh có 1 đầu cạnh là I hoặc j và đánh dấu các màu đã được tô Sau đó ta tìm mã màu gần nhất chưa được tô bởi các cạnh có 1 đầu cạnh là i hoặc j và gắn mã màu cho a[i][j] Gán a[j][i] = a[i][j] Lấy lại ví dụ trên ta được kết quả như sau: Bước 1 Bước 2: 1 2 3 4 5 6 7 ấy lại ví dụ trên ta được kết quả như sau: .............................................................h bày 2 cách cài đặt khMàu 2 1 2 3 4 5 6 7 Màu 3 Màu 2 1 2 3 4 5 6 7 Màu 4 Màu 3 Màu 2 Màu 4 Màu 3 Màu 2 1 2 3 4 5 6 7 Bước 3 Bước 4 Bước 5 Bước 6 Màu 4 Màu 3 Màu 2 Màu 4 Màu 3 Màu 2 1 2 3 4 5 6 7 1 2 3 4 5 6 7 1 2 3 4 5 6 7 Màu 4 Màu 3 Màu 2 Màu 5 1 2 3 4 5 6 7 Màu 4 Màu 3 Màu 2 Màu 5 Bước 7 Bước 8 Bước 9: Màu 4 Màu 3 Màu 2 Màu 5 Màu 6 1 2 3 4 5 6 7 Vậy trong ví dụ trên đồ thị được tô bằng 5 màu đánh số từ 2 cho đến 6. - Mô tả chương trình và đánh giá độ phức tạp cài đặt Đọc dữ liệu từ file lưu các giá trị vào mảng 2 chiều a int input(filename) // lay so lieu dau vao tu file du lieu { int i,j; f = fopen(filename,"r"); //mở file if (f== NULL) //nếu không có file như vậy { printf("\n Khong ton tai file \n"); return(1); } else //nếu có file { printf("File mane: %s \n",filename); printf("Content :\n"); fscanf(f,"%d",&n); //lấy số đỉnh printf("Co % d dinh\n",n); for(i=1;i<=n;i++) { for(j=1;j<=n;j++) //đưa vào ma trận a { fscanf(f,"%d",&a[i][j]); printf("%d ",a[i][j]); } printf("\n"); } return(0); } } Hàm có 2 câu lệnh for lồng nhau nên độ phức tạp là O(n2) Hàm khởi tạo các mã màu ,mã màu nhỏ nhất là 2 void initcolor() // khoi tao mau ban dau co toi da somau_max // voi somau_max bang bac lon nhat cua dinh do thi { int i; for(i=2;i<=somau_max;i++) mau[i]= i; } Hàm trên có độ phức tạp O(n) Hàm tìm bậc lớn nhất có độ phức tạp O(n) int maxbac() // ham tinh gia tri maxbac { int max; int i; int j; int dem=0; for(i=1;i<=n;i++) { dem = 0; for(j=1;j<=n;j++) if (a[i][j] == 1) dem++ ; if (max < dem) max = dem; } return max+1; } Hàm duyệt đồ thị void duyet(int x,int y) có độ phức tạp O(n) void duyet(int x,int y) // kiem tra cac canh mau xung quanh no { int i; initcolor(); // moi dinh lai su dung mang mau 1 lan for(i=1;i<=n;i++) { if (a[x][i] != 0) // neu canh [x,ke[i]] duoc to mau t mau[a[x][i]] = 0; // thi mau[t] = 0 } for(i=1;i<=n;i++) { if (a[y][i] != 0) mau[a[y][i]] = 0; } } Ví dụ với cạnh [3,4] lúc này trạng thái các cạnh như hình sau 1 2 3 4 5 6 7 Đỉnh 3 Vàng Đỉnh 4 tím Vàng Từ đó suy ra màu vàng và tím bị loại Hàm Tô màu các cạnh.Dùng hàm duyệt để kiểm tra xem những màu nào Ko được phép tô sau đó tìm màu gần nhất có thể tô được. Hàm này có độ phức tạp O(n3) void tomau() { int i,j; int t; for(i=1;i<=n;i++) for(j=1;j<=n;j++) if (a[i][j] == 1) { duyet(i,j) ; for(t=2;t<=somau_max;t++) if (mau[t] == t) { a[i][j] = t; a[j][i] = t; break; } } } Qua bước trên ta đã loại màu vàng và tím, màu gần nhất được phép tô là màu đỏ nên ta tô [3,4] màu đỏ Hàm void main() : hàm sử dụng các hàm con có độ phức tạp O(n3) (như hàm tô màu), độ phức tạp O(n2) ( như hàm input()), độ phức tạp O(n) ( như hàm tìm bậc lớn nhất maxbac()) nên chương trình có độ phức tạp là O(n3) initcolor(); somau_max = maxbac() ; tomau(); printf("\n Result:\n"); for(i=1;i<=n;i++) { for(j=1;j<=n;j++) if (a[i][j] >0) { printf(" Canh [%d,%d] duoc to mau %d ",i,j,a[i][j]) ; a[i][j] = 0; a[j][i] = 0; } printf("\n") ; } 1 2 3 4 5 6 7 - Hướng dẫnsử dụng chương trình Với cách cài đặt đầu tiên này, việc nhập dữ liệu được tách ra thành một khâu riêng bằng cách chúng ta phải tạo một file txt theo chuẩn đã trình bày ở trên. ( Trong bộ báo cáo có một bộ các file txt chính là ví dụ đi kèm với cách cài đặt này). Với cách nhập dữ liệu như thế này sẽ đơn giản hơn khi thực hiện chương trình. Lúc này việc nhập dữ liệu chỉ còn là nhập filename của file chứa ví dụ cần thực hiện và xem kết quả Nhập filename Sau đó ấn enter để xem nội dung file và kết quả - Kết quả thực nghiệm Trong phần kết quả sẽ in ra Nội dung của ma trận biểu diễn đồ thị Các cạnh cụ thể được tô màu theo thứ tự Kết quả của ví dụ trên Kết quả này hòan tòan phù hợp với ví dụ chúng ta đã trình bày ở phần mô tả giải thuật. Sau đây ta sẽ so sánh lại : Màu 4 Màu 3 Màu 2 Màu 5 Màu 6 1 2 3 4 5 6 7 2.2. Dữ liệu vào từ bàn phím Cài đặt Sắp xếp các cạnh theo thứ tự E1, E2, ...,En Tìm bậc lớn nhất của đồ thị (Δ) Chuẩn bị (Δ+1) màu để tô Bước i: tô cạnh Ei bởi màu có chỉ số nhỏ nhất trong số các màu chưa được sử dụng để tô cạnh kề của nó Trong đó việc sắp xếp các cạnh theo thứ tự được người sử dụng nhập vào. - Mô tả chương trình và đánh giá độ phức tạp Trước tiên ta tổ chức các cạnh là một danh sách gồm 3 thông tin: - Đỉnh đầu của cạnh - Đỉnh cuối của cạnh - Màu của cạnh typedef struct { int dau; int cuoi; int mau; } Danhsachcanh; Để lưu những màu đã tô của cạnh giao tại một đỉnh ta tổ chức n mảng (n là số đỉnh) với độ lớn là (Δ+1) phần tử. Trước hết ta đưa tất cả các phần tử này về 0 (chưa có màu nào được tô) Ta sử dụng con trỏ để trỏ tới vị trí mảng màu của một đỉnh: int *p[20]; //mảng con trỏ đến các mảng màu của đồ thị Để xác định vị trí của con trỏ của một đỉnh ta dùng đoạn code sau: int temp[20]; //mảng lưu vị trí con trỏ của các đỉnh int j=0; for (i=0;i<edge;i++) //thực hiện lưu vị trí con trỏ mảng màu của đỉnh { if (temp[G[i].dau]<0) {temp[G[i].dau]=j;j++;} if (temp[G[i].cuoi]<0) {temp[G[i].cuoi]=j;j++;} } Để xác định bậc lớn nhất của đồ thị ta dùng hàm maxdegree: Độ phức tạp của hàm là O(E) với E là số cạnh của đồ thị int maxdegree(Danhsachcanh a[],int edge) //hàm tìm bậc lớn nhất của đỉnh { int temp[20]; for (int i=0;i<20;i++) temp[i]=0; for (i=0;i<edge;i++) { temp[a[i].dau-1]++; temp[a[i].cuoi-1]++; } int max=temp[0]; for (i=1;i<21;i++) if (max<temp[i]) max=temp[i]; return max; } Hàm findcolor: Trong trường hợp tồi nhất độ phức tạp của hàm là O(V) với V là số đỉnh int findcolor(int *a,int *b,int maxdegree) //Hàm tìm màu tô cho cạnh { int i=0; while (((a[i]>0)||(b[i]>0))&&(i<maxdegree+1)) i++; return i; } Hàm này sẽ duyệt 2 mảng màu của 2 đỉnh và đưa ra vị trí thứ i đầu tiên là vị trí mà chưa có màu nào được tô, tại vị trí đó các phần tử của 2 mảng đều bằng 0. Ví dụ: với 2 mảng màu của 2 đỉnh 1 và 2 Thì hàm findcolor sẽ trả về giá trị là 2. Thì hàm findcolor sẽ trả về giá trị là 3. Theo cách này thì cạnh đầu tiên sẽ luôn được tô là màu đỏ (màu đỏ là màu có chỉ số thấp nhất) Đoạn chương trình thực hiện tô màu từng cạnh, khi duyệt qua lần lượt mỗi cạnh sẽ thực hiện những công việc sau: - Tìm vị trí thứ j là vị trí đầu tiên trong 2 mảng màu của 2 đỉnh chưa có màu tô - Sử dụng biến maxcolor để ghi nhận số màu lớn nhất khi đã tô cạnh này - Gán màu cho cạnh - Lưu lại vị trí j trong mảng màu của 2 đỉnh thuộc cạnh for (i=0;i<edge;i++)//duyet cac canh va to mau { j=findcolor(p[temp[G[i].dau]],p[temp[G[i].cuoi]],maxdeg); if(maxcolor<j+1) maxcolor=j+1; G[i].mau=j; *(p[temp[G[i].dau]]+j)=j+1; *(p[temp[G[i].cuoi]]+j)=j+1; } Dựa vào những đánh giá trên và dựa vào chương trình nguồn ta có thể đánh giá được độ phức tạp của chương trình Cai_dat_2 này là : O(E+V2) Một ví dụ Ta có đồ thị với 8 đỉnh và 10 cạnh như sau: Ta có bậc lớn nhất: maxdeg=5. Mảng màu các đỉnh được tạo như sau: Các bước tô màu: Bước 1: Bước 2: Bước 3: Bước 4: Bước 5: Bước 6: Bước 7: Bước 8: Bước 9: Bước 10: Kết quả: - Đồ thị tô được bởi 5 màu: red, blue, yellow, green, pink Cạnh 1(5,1): red Cạnh 2(2,1): blue Cạnh 3(4,5): blue Cạnh 4(7,8): red Cạnh 5(6,5): yellow Cạnh 6(5,7): green Cạnh 7(4,8): yellow Cạnh 8(3,1): yellow Cạnh 9(4,3): red Cạnh 10(5,2): pink - Hướng dẫn sử dụng chương trình Bước 1:Với cách cài đặt này người sử dụng phải tự nhập các đỉnh và các cạnh của đồ thị với quy tắc cho trước như sau: Yêu cầu người dùng nhập số đỉnh và số cạnh của đồ thị Với mỗi cạnh yêu cầu người dùng nhập vào 2 đỉnh là đỉnh đầu và đỉnh cuối Ví dụ như trong đồ thị trình bày ở trên ta có thể nhập như sau : Với thứ tự nhập các cạnh: Cạnh Đỉnh đầu Đỉnh cuối 1 5 1 2 2 1 3 4 5 4 7 8 5 6 5 6 5 7 7 4 8 8 3 1 9 4 3 10 5 2 Bước 2: Xem từng bước các kết quả. Với cách cài đặt này, người sử dụng được xem từng bước của quá trình tính tóan, tô màu thực hiện trong chương trình. Ấn enter trong mỗi lần chuyển đến bước kế tiếp. Kết quả cuối cùng sẽ được hiện lên màn hình - Kết quả thực nghiệm Kết quả sẽ hiện ra theo từng cạnh và màu tương ứng Sau đây là kết quả của ví dụ trên theo từng bước Kết quả này phù hợp với ví dụ ta trình bày trước đó Mã nguồn - File mã nguồn: Algo2010N15.cpp - File biên dịch: Algo2010N15 - File dữ liệu đầu vào của cài đặt tô mầu cạnh: edge-coloring.txt - File dữ liệu đầu vào của cài đặt tô mầu đỉnh: graph.txt - File dữ liệu đầu ra của cài đặt tô mầu đỉnh: coloring.txt TÀI LIỆU THAM KHẢO Bài giảng của thầy Nguyễn Đức Nghĩa. Coloring random graphs : organization of solutión and computational hardness - Lenka Zdeborova’ và Florent Krzakala Graph coloring problems and their applications in scheduling - Da’niel Mark Graph coloring algorithms - Walter Klotz Reducibility among combinatorial problems, Complexity of Computer Computations, Plenum Press, 1972- R.M. Karp The Vertex Coloring Algorithm - Ashay Dharwadker Các bài viết trên wikipedia và các trang web: PHỤ LỤC 1: DANH MỤC CÁC HÌNH ẢNH TRONG TÀI LIỆU Hình 01: Đồ thị vô hướng Hình 02: Đồ thị G của bài toán lập lịch trên Hình 03:  Các đồ thị đầu vào G với 3- màu tương ứng của các đỉnh của nó được tìm thấy bởi thuật toán Hình 04: tích đề các G × K 3 với một tập độc lập với kích thước 4 được  tìm thấy bằng thuật toán Hình 05: Đồ thị Octahedron với tập đúng m-màu (n = 6, m = χ( G ) = 3 ). Hình 06: Đồ thị Bondy-Murty G 1 với tập đúng m-màu PHỤ LỤC 2: PHÂN CHIA CÔNG VIỆC Họ tên SV Nội dung công việc Đóng góp Nguyễn Thị Thanh Vi Cài đặt bài toán tô mầu đỉnh Lập báo cáo 35% Ngô Văn Vĩ Cài đặt bài toán tô mầu cạnh với dữ liệu từ file Tìm hiểu thuật toán giải quyết bài toán tô mầu cạnh 35% Nhâm Ngọc Trung Cài đặt bài toán tô mầu cạnh với dữ liệu nhập từ bàn phím Tìm hiểu thuật toán giải quyết bài toán tô mầu đỉnh 30%