Báo cáo áp dụng thuật giải heuristic cho bài toán tô màu tối ưu trên đồ thị
- 54 trang
- file .pdf
lOMoARcPSD|16911810
Nhóm07-Áp dụng thuật giải heuristic cho bài toán tô màu tối
ưu trên đồ thị
Công nghệ phần mềm (Trường Đại Học Điện Lực)
StuDocu is not sponsored or endorsed by any college or university
Downloaded by Dung Nguyen ([email protected])
lOMoARcPSD|16911810
TRƯỜNG ĐẠI HỌC ĐIỆN LỰC
KHOA CÔNG NGHỆ THÔNG TIN
BÁO CÁO CHUYÊN ĐỀ HỌC PHẦN
NHẬP MÔN TRÍ TUỆ NHÂN TẠO
ĐỀ TÀI:
Áp dụng thuật giải heuristic cho bài toán tô màu tối ưu trên đồ thị
Sinh viên thực hiện : PHẠM VĂN TUẤN
NGUYỄN HOÀNG HIỆU
NGUYỄN DỨC THUẬN
Giảng viên hướng dẫn : VŨ VĂN ĐỊNH
Ngành : CÔNG NGHỆ THÔNG TIN
Chuyên ngành : HỆ THỐNG THƯƠNG MẠI ĐIỆN
TỬ
Lớp : D14HTTMDT1
Khóa : 2019
Hà Nội, tháng 10 năm 2021
Phiếu chấm điểm
Downloaded by Dung Nguyen ([email protected])
lOMoARcPSD|16911810
STT Họ tên sinh viên Nội dung thực hiện Điểm Chữ ký
1 Phạm Văn Tuấn Làm báo cáo
Làm chương trình
2 Nguyễn Hoàng Hiệu Làm báo cáo
Làm chương trình
3 Nguyễn Đức Thuận Làm báo cáo
Làm chương trình
Họ tên giảng viên Chữ ký Ghi chú
Downloaded by Dung Nguyen ([email protected])
lOMoARcPSD|16911810
MỤC LỤC
I. GIỚI THIỆU BÀI TOÁN..................................................................................................................4
1. Tổng quan về heuristic..................................................................................................................4
1.1. Heuristic và các cách biểu diễn đồ thị.......................................................................................4
1.2. Các bài toán điển hình................................................................................................................6
2. Bài toán tô mầu đồ thị...................................................................................................................6
2.1. Bài toán tô mầu cạnh..................................................................................................................6
2.2. Bài toán tô mầu đỉnh..................................................................................................................6
2.3. Các khái niệm liên quan.............................................................................................................7
2.4. Ứng dụng......................................................................................................................................8
II. GIẢI THUẬT.................................................................................................................................9
1. Bài toán tô mầu đỉnh.....................................................................................................................9
1.1. Các định nghĩa sử dụng:........................................................................................................9
1.2. Thuật toán............................................................................................................................10
1.3. Ví dụ......................................................................................................................................12
2. Bài toán tô mầu cạnh...................................................................................................................17
2.1. Giải thuật..............................................................................................................................17
2.3. Độ phức tạp:.........................................................................................................................23
III. CÀI ĐẶT THUẬT TOÁN...........................................................................................................24
1. Bài toán tô mầu đỉnh.......................................................................................................................24
2. Bài toán tô mầu cạnh.......................................................................................................................30
2.1. Đọc dữ liệu từ fle..................................................................................................................30
2.2. Dữ liệu vào từ bàn phím........................................................................................................40
3. Mã nguồn......................................................................................................................................51
IV. TÀI LIỆU THAM KHẢO...........................................................................................................52
PHỤ LỤC 1: DANH MỤC CÁC HÌNH ẢNH TRONG TÀI LIỆU...................................................53
PHỤ LỤC 2: PHÂN CHIA CÔNG VIỆC..............................................................................................53
Downloaded by Dung Nguyen ([email protected])
lOMoARcPSD|16911810
I. GIỚI THIỆU BÀI TOÁN
1. Thuật giải heuristic
1.1.khái niệm heuristic
Là mở rộng khái niệm thuật toán.
o Thuờng tìm lời giải tốt nhưng không tốt nhất.
o Nhanh chóng tìm ra kết quả hơn so với giải thuật tối ưu, vì vậy chi phí thấp hơn.
o Thuờng thể hiện khá tự nhiên, gần gũi với cách suy nghĩ và hành động của con
nguời.
Các nguyên lý của thuật giải heuristic
Vét cạn thông minh
Nguyên lý thứ tự
Nguyên lý tham lam
Hàm heuristic
Kyỹ thuật heuristic:
Theo Từ điển tiêếng Anh Oxford: “Heuristics là nghệ thuật tm kiêếm chân lý. Nói riêng,
heuristics là đặc trưng của quá trình học nhờ đó các học sinh học được cách tự tm ra cách
giải thích các hiện tượng tự nhiên”.
Từ “Heuristics” có cùng một gôếc tiêếng Hy Lạp như từ Eureka. Feigenbaum Feldman đã
đưa ra định nghĩa :
“Heuristics (Các quy tắếc heuristics, các phương pháp heuristics) là các quy tắếc, phương
pháp, chiêến lược, mẹo giải hay phương cách nào đó nhắằm làm giảm khôếi lượng tm kiêếm lời
giải trong không gian bài tóan cực lớn”.
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ề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ụ
Downloaded by Dung Nguyen ([email protected])
lOMoARcPSD|16911810
Đồ 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 nguyên lý của thuật giải heuristic
1.Vét cạn thông minh
Hạn chêế vùng không gian tm kiêếm và có sự định hướng để nhanh chóng tm đêến mục
tiêu.
Tạo miêằn D’ râết nhỏ so với D
Vét cạn trên D’
2.Nguyên lý tham lam (Greedy):
Lâếy tiêu chuẩn tôếi ưu (trên phạm vi toàn cục) của bài toán để làm tiêu
chuẩn chọn lựa hành động cho phạm vi cục bộ của từng bước.
a)Thuật giải GTS1: (Greedy-Traveling Saleman)
Xây dựng một lịch trình du lịch có chi phí Cost tôếi thiểu cho bài toán
trong trường hợp phải qua n thành phôế với ma trận chi phí C và bắết đâằu tại
một đỉnh U nào đó.
Downloaded by Dung Nguyen ([email protected])
lOMoARcPSD|16911810
Thuật giải:
Bước 1: {Khởi đâằu}
Đặt Tour := {};
Cost := 0;
V := U; {V là đỉnh hiện tại đang làm việc}
Bước 2: {Thắm tâết cả các thành phôế}
For k := 1 To n Do
qua bước 3;
Bước 3: {Chọn cung kêế tiêếp}
Đặt (V, W) là cung có chi phí nhỏ nhâết tnh từ V đêến các đỉnh W chưa dùng:
Tour := Tour + {(V,W)};
Cost := Cost + Cost(V,W);
Nhãn W được sử dụng
Đặt V := W; {Gán để xét bước kêế tiêếp}
Bước 4: {Chuyêến đi hoàn thành}
Đặt Tour := Tour + {(V,U)};
Cost := Cost + Cost(V,U);
Dừng.
U= A
Tour = {}
Cost = 0
V =A
W ∈ {B, C, D, E}{Các đỉnh có thể đêến từ A}
→ W = B{Vì qua B có giá thành bé nhâết}
Tour = {(A, B)}
Cost = 1
V=B
W ∈ {C, D, E}→ W = EA
Tour = {(A, B),(B, E)}
Cost = 1 + 3 = 4
V =E
W ∈ {C, D} → W = C
b.Thuật giải GTS2:
Tạo ra lịch trình từ p thành phôế xuâết phát riêng biệt. Tìm chu trình của người bán
hàng qua n thành phôế (1 chu trình được giữ lại mà thôi (thuật giải này đòi hỏi phải nhập n, p và C)
Thuật giải:
Bước 1: {Khởi đâằu}
Downloaded by Dung Nguyen ([email protected])
lOMoARcPSD|16911810
k := 0; {Đêếm sôế thành phôế đi qua}
Tour = {(A, B), (B, E), (E, C)}
2.4. Ứng dụng Bước 2: {Bắết đâằu chu trình
mới}
Chuyển qua bước 3 khi k ngược lại dừng.
Bước 3: {Tạo chu trình mới}
k := k + 1;
Call (GTS1(Vk)) : Trả vêằ một chu
trình T(k) ứng với chi phí C(k).
Bước 4: {Cập nhật chu trình tôết
nhâết}
Nêếu C(k)< Cost thì
Best := T(k);
Cost := C(k);
Bước 2: {Bắết đâằu chu trình mới}
Downloaded by Dung Nguyen ([email protected])
lOMoARcPSD|16911810
Chuyển qua bước 3 khi k ngược lại dừng.
Bước 3: {Tạo chu trình mới}
k := k + 1;
Call (GTS1(Vk)) : Trả vêằ một chu
trình T(k) ứng với chi phí C(k).
Bước 4: {Cập nhật chu trình tôết
nhâết}
Nêếu C(k)< Cost thì
Best := T(k);
Cost := C(k);
2.Bài toán dồ thị
- 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
Downloaded by Dung Nguyen ([email protected])
lOMoARcPSD|16911810
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
Downloaded by Dung Nguyen ([email protected])
lOMoARcPSD|16911810
Số thanh ghi ít nhất cần sử dụng sẽ là số mầu của đồ thị trên
II. GIẢI THUẬT
1. Bài toán tô mầu đỉnh
1.1. 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.
Downloaded by Dung Nguyen ([email protected])
lOMoARcPSD|16911810
- 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.
1.2. 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
Downloaded by Dung Nguyen ([email protected])
lOMoARcPSD|16911810
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:
o (U 1 1, v 1), (u 1 2, v 1), ..., (u 1 i (1), v 1)
o (U 2 1, v 2), (u 2 2, v 2), ..., (u 2 i (2), v 2)
o ...
o (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.
Downloaded by Dung Nguyen ([email protected])
lOMoARcPSD|16911810
Phần I. Đối với i = 1, 2, ..., n và j = 1, 2, ..., n lần lượt
o Khởi tạo tập độc lập S i, j = {(u i, v j)}.
o Thực hiện thủ tục 3.1 trên S i, j.
o Đối với r = 1, 2, ..., n thực hiện thủ tục 3.2 lặp lại r lần.
o 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
o Khởi tạo S đặt độc lập i, j, k, l = S i, j ∩ S k, l.
o Thực hiện thủ tục 3,1 trên S i, j, k, l.
o Đố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.
o 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.
1.3. 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.
Downloaded by Dung Nguyen ([email protected])
lOMoARcPSD|16911810
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.
Downloaded by Dung Nguyen ([email protected])
lOMoARcPSD|16911810
Hình 04: tích đề các G×K3vớ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, Đỉnh có thể thêm
ρ (1,1 S ∪ {(u, v)})
v) củaS 1,1 của S 1,1 ∪{(u, v)}
(2, 2) (3, 3), (4, 2), (4, 3) 3
(3, 2), (4,
(2, 3) 3
2), (4, 3)
(3, 2) (2, 3), (4, 3) 2
(3, 3) (2, 2), (4, 2) 2
Downloaded by Dung Nguyen ([email protected])
lOMoARcPSD|16911810
(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 đỏ).
1.4. Độ 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.
Downloaded by Dung Nguyen ([email protected])
lOMoARcPSD|16911810
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.
2. Bài toán tô mầu cạnh
2.1. 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).
Downloaded by Dung Nguyen ([email protected])
lOMoARcPSD|16911810
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.
2.2. Ví dụ
Ta có đồ thị sau:
Ta sắp xếp các cạnh theo thứ tự như sau:
Downloaded by Dung Nguyen ([email protected])
lOMoARcPSD|16911810
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.
Downloaded by Dung Nguyen ([email protected])
Nhóm07-Áp dụng thuật giải heuristic cho bài toán tô màu tối
ưu trên đồ thị
Công nghệ phần mềm (Trường Đại Học Điện Lực)
StuDocu is not sponsored or endorsed by any college or university
Downloaded by Dung Nguyen ([email protected])
lOMoARcPSD|16911810
TRƯỜNG ĐẠI HỌC ĐIỆN LỰC
KHOA CÔNG NGHỆ THÔNG TIN
BÁO CÁO CHUYÊN ĐỀ HỌC PHẦN
NHẬP MÔN TRÍ TUỆ NHÂN TẠO
ĐỀ TÀI:
Áp dụng thuật giải heuristic cho bài toán tô màu tối ưu trên đồ thị
Sinh viên thực hiện : PHẠM VĂN TUẤN
NGUYỄN HOÀNG HIỆU
NGUYỄN DỨC THUẬN
Giảng viên hướng dẫn : VŨ VĂN ĐỊNH
Ngành : CÔNG NGHỆ THÔNG TIN
Chuyên ngành : HỆ THỐNG THƯƠNG MẠI ĐIỆN
TỬ
Lớp : D14HTTMDT1
Khóa : 2019
Hà Nội, tháng 10 năm 2021
Phiếu chấm điểm
Downloaded by Dung Nguyen ([email protected])
lOMoARcPSD|16911810
STT Họ tên sinh viên Nội dung thực hiện Điểm Chữ ký
1 Phạm Văn Tuấn Làm báo cáo
Làm chương trình
2 Nguyễn Hoàng Hiệu Làm báo cáo
Làm chương trình
3 Nguyễn Đức Thuận Làm báo cáo
Làm chương trình
Họ tên giảng viên Chữ ký Ghi chú
Downloaded by Dung Nguyen ([email protected])
lOMoARcPSD|16911810
MỤC LỤC
I. GIỚI THIỆU BÀI TOÁN..................................................................................................................4
1. Tổng quan về heuristic..................................................................................................................4
1.1. Heuristic và các cách biểu diễn đồ thị.......................................................................................4
1.2. Các bài toán điển hình................................................................................................................6
2. Bài toán tô mầu đồ thị...................................................................................................................6
2.1. Bài toán tô mầu cạnh..................................................................................................................6
2.2. Bài toán tô mầu đỉnh..................................................................................................................6
2.3. Các khái niệm liên quan.............................................................................................................7
2.4. Ứng dụng......................................................................................................................................8
II. GIẢI THUẬT.................................................................................................................................9
1. Bài toán tô mầu đỉnh.....................................................................................................................9
1.1. Các định nghĩa sử dụng:........................................................................................................9
1.2. Thuật toán............................................................................................................................10
1.3. Ví dụ......................................................................................................................................12
2. Bài toán tô mầu cạnh...................................................................................................................17
2.1. Giải thuật..............................................................................................................................17
2.3. Độ phức tạp:.........................................................................................................................23
III. CÀI ĐẶT THUẬT TOÁN...........................................................................................................24
1. Bài toán tô mầu đỉnh.......................................................................................................................24
2. Bài toán tô mầu cạnh.......................................................................................................................30
2.1. Đọc dữ liệu từ fle..................................................................................................................30
2.2. Dữ liệu vào từ bàn phím........................................................................................................40
3. Mã nguồn......................................................................................................................................51
IV. TÀI LIỆU THAM KHẢO...........................................................................................................52
PHỤ LỤC 1: DANH MỤC CÁC HÌNH ẢNH TRONG TÀI LIỆU...................................................53
PHỤ LỤC 2: PHÂN CHIA CÔNG VIỆC..............................................................................................53
Downloaded by Dung Nguyen ([email protected])
lOMoARcPSD|16911810
I. GIỚI THIỆU BÀI TOÁN
1. Thuật giải heuristic
1.1.khái niệm heuristic
Là mở rộng khái niệm thuật toán.
o Thuờng tìm lời giải tốt nhưng không tốt nhất.
o Nhanh chóng tìm ra kết quả hơn so với giải thuật tối ưu, vì vậy chi phí thấp hơn.
o Thuờng thể hiện khá tự nhiên, gần gũi với cách suy nghĩ và hành động của con
nguời.
Các nguyên lý của thuật giải heuristic
Vét cạn thông minh
Nguyên lý thứ tự
Nguyên lý tham lam
Hàm heuristic
Kyỹ thuật heuristic:
Theo Từ điển tiêếng Anh Oxford: “Heuristics là nghệ thuật tm kiêếm chân lý. Nói riêng,
heuristics là đặc trưng của quá trình học nhờ đó các học sinh học được cách tự tm ra cách
giải thích các hiện tượng tự nhiên”.
Từ “Heuristics” có cùng một gôếc tiêếng Hy Lạp như từ Eureka. Feigenbaum Feldman đã
đưa ra định nghĩa :
“Heuristics (Các quy tắếc heuristics, các phương pháp heuristics) là các quy tắếc, phương
pháp, chiêến lược, mẹo giải hay phương cách nào đó nhắằm làm giảm khôếi lượng tm kiêếm lời
giải trong không gian bài tóan cực lớn”.
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ề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ụ
Downloaded by Dung Nguyen ([email protected])
lOMoARcPSD|16911810
Đồ 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 nguyên lý của thuật giải heuristic
1.Vét cạn thông minh
Hạn chêế vùng không gian tm kiêếm và có sự định hướng để nhanh chóng tm đêến mục
tiêu.
Tạo miêằn D’ râết nhỏ so với D
Vét cạn trên D’
2.Nguyên lý tham lam (Greedy):
Lâếy tiêu chuẩn tôếi ưu (trên phạm vi toàn cục) của bài toán để làm tiêu
chuẩn chọn lựa hành động cho phạm vi cục bộ của từng bước.
a)Thuật giải GTS1: (Greedy-Traveling Saleman)
Xây dựng một lịch trình du lịch có chi phí Cost tôếi thiểu cho bài toán
trong trường hợp phải qua n thành phôế với ma trận chi phí C và bắết đâằu tại
một đỉnh U nào đó.
Downloaded by Dung Nguyen ([email protected])
lOMoARcPSD|16911810
Thuật giải:
Bước 1: {Khởi đâằu}
Đặt Tour := {};
Cost := 0;
V := U; {V là đỉnh hiện tại đang làm việc}
Bước 2: {Thắm tâết cả các thành phôế}
For k := 1 To n Do
qua bước 3;
Bước 3: {Chọn cung kêế tiêếp}
Đặt (V, W) là cung có chi phí nhỏ nhâết tnh từ V đêến các đỉnh W chưa dùng:
Tour := Tour + {(V,W)};
Cost := Cost + Cost(V,W);
Nhãn W được sử dụng
Đặt V := W; {Gán để xét bước kêế tiêếp}
Bước 4: {Chuyêến đi hoàn thành}
Đặt Tour := Tour + {(V,U)};
Cost := Cost + Cost(V,U);
Dừng.
U= A
Tour = {}
Cost = 0
V =A
W ∈ {B, C, D, E}{Các đỉnh có thể đêến từ A}
→ W = B{Vì qua B có giá thành bé nhâết}
Tour = {(A, B)}
Cost = 1
V=B
W ∈ {C, D, E}→ W = EA
Tour = {(A, B),(B, E)}
Cost = 1 + 3 = 4
V =E
W ∈ {C, D} → W = C
b.Thuật giải GTS2:
Tạo ra lịch trình từ p thành phôế xuâết phát riêng biệt. Tìm chu trình của người bán
hàng qua n thành phôế (1
Thuật giải:
Bước 1: {Khởi đâằu}
Downloaded by Dung Nguyen ([email protected])
lOMoARcPSD|16911810
k := 0; {Đêếm sôế thành phôế đi qua}
Tour = {(A, B), (B, E), (E, C)}
2.4. Ứng dụng Bước 2: {Bắết đâằu chu trình
mới}
Chuyển qua bước 3 khi k
Bước 3: {Tạo chu trình mới}
k := k + 1;
Call (GTS1(Vk)) : Trả vêằ một chu
trình T(k) ứng với chi phí C(k).
Bước 4: {Cập nhật chu trình tôết
nhâết}
Nêếu C(k)< Cost thì
Best := T(k);
Cost := C(k);
Bước 2: {Bắết đâằu chu trình mới}
Downloaded by Dung Nguyen ([email protected])
lOMoARcPSD|16911810
Chuyển qua bước 3 khi k
Bước 3: {Tạo chu trình mới}
k := k + 1;
Call (GTS1(Vk)) : Trả vêằ một chu
trình T(k) ứng với chi phí C(k).
Bước 4: {Cập nhật chu trình tôết
nhâết}
Nêếu C(k)< Cost thì
Best := T(k);
Cost := C(k);
2.Bài toán dồ thị
- 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
Downloaded by Dung Nguyen ([email protected])
lOMoARcPSD|16911810
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
Downloaded by Dung Nguyen ([email protected])
lOMoARcPSD|16911810
Số thanh ghi ít nhất cần sử dụng sẽ là số mầu của đồ thị trên
II. GIẢI THUẬT
1. Bài toán tô mầu đỉnh
1.1. 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.
Downloaded by Dung Nguyen ([email protected])
lOMoARcPSD|16911810
- 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.
1.2. 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
Downloaded by Dung Nguyen ([email protected])
lOMoARcPSD|16911810
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:
o (U 1 1, v 1), (u 1 2, v 1), ..., (u 1 i (1), v 1)
o (U 2 1, v 2), (u 2 2, v 2), ..., (u 2 i (2), v 2)
o ...
o (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.
Downloaded by Dung Nguyen ([email protected])
lOMoARcPSD|16911810
Phần I. Đối với i = 1, 2, ..., n và j = 1, 2, ..., n lần lượt
o Khởi tạo tập độc lập S i, j = {(u i, v j)}.
o Thực hiện thủ tục 3.1 trên S i, j.
o Đối với r = 1, 2, ..., n thực hiện thủ tục 3.2 lặp lại r lần.
o 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
o Khởi tạo S đặt độc lập i, j, k, l = S i, j ∩ S k, l.
o Thực hiện thủ tục 3,1 trên S i, j, k, l.
o Đố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.
o 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.
1.3. 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.
Downloaded by Dung Nguyen ([email protected])
lOMoARcPSD|16911810
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.
Downloaded by Dung Nguyen ([email protected])
lOMoARcPSD|16911810
Hình 04: tích đề các G×K3vớ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, Đỉnh có thể thêm
ρ (1,1 S ∪ {(u, v)})
v) củaS 1,1 của S 1,1 ∪{(u, v)}
(2, 2) (3, 3), (4, 2), (4, 3) 3
(3, 2), (4,
(2, 3) 3
2), (4, 3)
(3, 2) (2, 3), (4, 3) 2
(3, 3) (2, 2), (4, 2) 2
Downloaded by Dung Nguyen ([email protected])
lOMoARcPSD|16911810
(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 đỏ).
1.4. Độ 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.
Downloaded by Dung Nguyen ([email protected])
lOMoARcPSD|16911810
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.
2. Bài toán tô mầu cạnh
2.1. 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).
Downloaded by Dung Nguyen ([email protected])
lOMoARcPSD|16911810
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.
2.2. Ví dụ
Ta có đồ thị sau:
Ta sắp xếp các cạnh theo thứ tự như sau:
Downloaded by Dung Nguyen ([email protected])
lOMoARcPSD|16911810
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.
Downloaded by Dung Nguyen ([email protected])