PDA

View Full Version : Một bài về đồ thị



pdah
31-03-2004, 13:18
Đây là một bài toán đồ thị, em đã thử dùng thuật toán quay lui nhưng hình như không khả thi lắm, thầy em thì bảo là hãy thử dùng thuật toán tham lam, nhưng không biết dùng thế nào: Cho một đồ thị vô hướng , tìm cách phân các đỉnh của đồ thị thành ít nhóm nhất sao cho bất kỳ 2 đỉnh nào trong cùng 1 nhóm cũng được nối với nhau

Global
31-03-2004, 20:30
He he , gặp người quen cũ rồi . (lộn thì thôi , bỏ qua )
U nói đề thiệt rõ đi chớ chả hiểu gì cả .

Junior IT
31-03-2004, 22:18
"cũng được nối với nhau" = có đường đi đến nhau hay có cạnh nối trực tiếp ?

jiSh@n
01-04-2004, 00:40
Mỗi nhóm là 1 thành phần liên thông?

pdah
01-04-2004, 12:11
cũng được nối với nhau" = có cạnh nối trực tiếp

Junior IT
02-04-2004, 10:58
Nếu vậy thì đây là dạng đối ngẫu của bài toán tô màu đồ thị, bạn tìm trong các sách thuật toán có nói về dạng này. Ko có thuật toán tốt và thường thì dùng Greedy để giải

pdah
02-04-2004, 15:52
Nếu em tìm được sách thì em đâu có hỏi anh làm gì ,hix. Thầy em cũng bảo là thử dùng tham lam đó thôi, nhưng mà chả biết dùng thế nào

Junior IT
02-04-2004, 20:21
Bước 1 : Đưa G về G' theo đúng nguyên tắc của bài toán đối ngẫu
Bước 2 : ( ý tưởng chung của phương pháp Greedy )
"Thuật toán Greedy dùng tô màu đồ thị đơn.
Liệt kê các đỉnh v1, v2, ..., vn theo thứ tự giảm dần của bậc. Gán màu 1 cho v1 và cho các đỉnh khác trong danh sách không liền kề với v1 (nếu nó tồn tại) và lần lượt cho các đỉnh không kề với các đỉnh có màu 1. Sau đó gán màu 2 cho đỉnh đầu tiên trong danh sách còn chưa được tô màu, lần lượt gán màu 2 cho các đỉnh trong danh sách nếu chưa được tô màu và không nối với các đỉnh có màu 2. Nếu vẫn còn các đỉnh chưa được tô màu thì gán màu 3 cho đỉnh chưa được tô màu đầu tiên trong danh sách và các đỉnh chưa tô màu và không liền kề với các đỉnh có màu 3. Tiếp tục quá trình này cho đến khi tất cả các đỉnh được tô màu."