Graph màu Algorithm

Question

Từ wiki http://en.wikipedia.org/wiki/Graph_coloring

Ở dạng đơn giản nhất, đó là một cách để tô đầy lên cái đỉnh của một đồ thị như rằng không có hai đỉnh kề nhau chia sẻ cùng màu; điều này được gọi là một màu đỉnh là . Tương tự, cạnh màu sẽ gán màu cho mỗi cạnh sao cho không có hai cạnh liền kề chia sẻ cùng màu và màu mặt biểu đồ phẳng gán màu cho từng mặt sao cho không có hai mặt chia sẻ đường biên có cùng màu .

Cho 'n' màu sắc và đỉnh 'm', thuật toán màu có thể dễ dàng thực hiện bằng ngôn ngữ lập trình?

Ngôn ngữ không có rào cản.

Chỉ cần trêu ghẹo não.

(Giả Graph và các đối tượng đỉnh tồn tại)

Edit:
Sau khi đọc wiki, vấn đề là NP-đầy đủ
Thời gian để xem lại cuốn sách toán học :)
xấu của tôi.
xin lỗi.

Chỉ tò mò,
Điều này đã được thử chưa? như bằng văn bản chương trình cho cùng?
Tôi nghe nói rằng điều này được sử dụng trong các mạng quang?

Điều này không giống với khối lập phương màu ??
(số lượng tối thiểu của màu sắc để khuôn mặt màu sắc của khối lập phương để không có hai bên chia sẻ cùng màu?)

Answer 1

Đây là một hoàn chỉnh vấn đề NP, đọc Wikipedia entry để biết thêm thông tin về phương pháp khác nhau giải quyết.

Answer 2

Nếu bạn được cung cấp 2 màu và biểu đồ có 2 màu (nghĩa là nó là bipartite graph), thì bạn có thể làm điều đó trong thời gian đa thức khá tầm thường.

Tôi đã cung cấp mã giả để trả lời cho câu hỏi này: Graph colouring algorithm: typical scheduling problem.

Answer 3

Như đã đề cập, vấn đề chung là hoàn thành np. Biểu đồ hai chiều có thể được tô màu chỉ bằng 2 màu. Một điều cũng đúng là đồ thị phẳng (đồ thị không chứa K3,3 or K5 dưới dạng đồ thị phụ, theo định lý của Kuratowski) có thể được tô màu với 4 màu. Hình minh hoạ.

Answer 4

Trong Luận văn Thạc sĩ của tôi, tôi thử nghiệm các thuật toán tô màu. Thuật toán đơn giản nhất là Cạnh Backtrace.

Đây là triển khai thực hiện của tôi trong Java:

public boolean edgeBackTrace (List<Edge<T>> edgesList, Map<Edge<T>, List<Edge<T>>> neighborEdges) { 
    for (Edge<T> e : edgesList) { 
    e.setColor(0); 
    } 
    int i = 0; 
    while (true){ 
    Edge<T> edge = edgesList.get(i); 
    edge.setColor(edge.getColor() + 1); 
    if (edge.getColor().equals(4)) { 
     edge.setColor(0); 
     if (i == 0) { 
     return true; 
     } else { 
     i--; 
     } 
    } else { 
     boolean diferentColor = false; 

     for (Edge<T> e : neighborEdges.get(edge)) { 
     if (e.getColor().equals(edge.getColor())) { 
      diferentColor = true; 
     } 
     } 

     if (diferentColor == false) { 
     i++; 
     if (i == edgesList.size()) { 
      return false; 
     } 
     } 
    } 
    } 
} 

Các thuật toán trả về một giá trị true nếu đồ thị có màu. Bạn có thể thấy trong edgeList làm màu, các cạnh riêng lẻ.