GIỚI THIỆU BI TOÁN
Bài toán tô mầu đồ thị
Tô màu đồ thị là một công cụ quan trọng trong việc mô hình hóa nhiều bài toán như xếp lịch, xây dựng chương trình và phân công công việc Bài toán này bao gồm nhiều loại hình thức, chẳng hạn như tô màu đỉnh đồ thị và tô màu cạnh đồ thị, giúp tối ưu hóa quy trình và nâng cao hiệu quả trong các lĩnh vực khác nhau.
2.1 Bài toán tô mầu cạnh
Cho G=(V,E) là một đồ thị vô hướng không có chu trình, nhiệm vụ là gán màu cho các cạnh của đồ thị sao cho hai cạnh chung một đỉnh không cùng màu Phép gán màu cho các cạnh này được gọi là tô màu cạnh đồ thị Mục tiêu là phân hoạch tập hợp các cạnh E của G thành k tập con, mỗi tập con tương ứng với một màu, sao cho sử dụng số màu ít nhất có thể.
Đồ thị G có thể được tô bằng k màu-cạnh nếu tồn tại một phép tô phù hợp với k màu Hầu hết các đồ thị không phải đồ thị khuyên đều có thể được tô màu Nếu đồ thị G thỏa mãn điều kiện này, thì nó cũng có khả năng được tô bằng l màu, với l lớn hơn k.
2.2 Bài toán tô mầu đỉnh
Phép tô màu k màu là phương pháp sử dụng tối đa k màu để tô các đỉnh của đồ thị G Sắc số đỉnh của đồ thị G là số lượng màu tối thiểu cần thiết để tô các đỉnh sao cho không có hai đỉnh kề nhau nào có 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
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ạ ỏ ớ
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 chương trình du lịch với chi phí tối thiểu là bài toán quan trọng trong việc tối ưu hóa lộ trình di chuyển trong thành phố, dựa trên ma trận chi phí C và điểm xuất phát U.
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ôế}ả
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:ặ ỏ ừ ỉ ư
Đ t V := W; {Gán đ xét bặ ể ước kêế tiêếp}
B ướ c 4 : {Chuyêến đi hoàn thành}
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}
Để ra lộ trình tập thành phố xuất phát riêng biệt, cần tìm chu trình của người bán hàng qua thành phố (1
