раскраска графа ровно в k цветов

Прежде всего, обратите внимание на 2 предположения:

1. Если | V | ‹K, тогда это невозможно - поэтому допустим | V | > = к.
2. Если мы можем раскрасить граф менее чем в k цветов и | v | > k, тогда это возможно также с ровно k цветом - мы можем просто переключить повторяющийся цвет на тот, который мы еще не использовали.

Мы можем использовать жадный алгоритм, чтобы решить эту проблему.

Присвоим каждому цвету номер [1,2, ..., k] - обозначим цвет i символом Ci. Начните с произвольного узла v1 и назначьте ему C1. Теперь позвольте запустить BSF на графике для каждого узла и выбрать минимальный цвет, которого нет в его узле настройки - если другой узел еще не имеет цвета, игнорируйте их. Если d (v)> k и все его настройки другого цвета, верните false.

Псевдокод:

// v.color init as 0 for all V
Queue <- new Queue(v1)
While Queue not empty:
    current <- Queue.pop
    if (current.color != 0 )
         continue
    adjs <- current.getAdj()
    colors = new Set
    for each adjs as adj:
        colors.add(adj.colors)
    for i = 1 to k:
        if i not in colors: //found lowest color avilable
             current.color <- C[i]
             break
    if current.color == 0 return false // cannot assign any color
    Queue.insert(adjs)

В статье об алгоритмах раскраски графа в Википедии отмечается, что вопрос о том, допускает ли граф правильная (= нет двух вершин одного цвета, если они соединены ребром) раскраска ровно k цветов является NP-полной.

Алгоритм грубой силы - лучшее, на что вы можете надеяться (если у вас нет других ограничений, таких как двудольный или плоский граф). Алгоритм грубой силы следующий:

#include <iostream>
#include <string>

using namespace std;

// describes a partial answer to the problem
struct Coloring {
    static const int maxV = 5;

    // only the first k colors count
    int colors[maxV];

    void show(int k) const {
        cout << "{";
        for (int i=0; i<k; i++) {
            cout << colors[i] << " ";
        }                                  
        cout << "}" << endl;
    }     
};

// A graph
struct Graph {
    int availableColors;
    int numV;
    bool edges[Coloring::maxV][Coloring::maxV];

    void handleAnswer(Coloring &s) const {
        cout << "EUREKA: ";
        s.show(numV);
    }

    // checks if the k-th vertex avoids being same-color as neighbors
    bool isPartialAnswer(const Coloring &s, int k) const {
        cout << std::string(k, ' ') << "testing: ";
        s.show(k);
        for (int i=0; i<k; i++) {
            for (int j=0; j<i; j++) {
                if ((edges[i][j] || edges[j][i]) 
                    && (s.colors[i] == s.colors[j])) {
                    cout << std::string(k, ' ') << " .. but " 
                        << i << " & " << j << " have same color" << endl;
                    return false;
                }
            }
        }
        return true;
    }

    bool isAnswer(const Coloring &s, int k) const {
        return k == numV;
    }                        
};

void paint(Coloring &s, int k, const Graph &c) {
    // initializes level
    cout << std::string(k, ' ') << "entering k=" << k << ": ";
    s.show(k); 

    // test with each possible color for the next vertex
    for (int i=0; i<c.availableColors; i++) {
        // modify current partial answer
        s.colors[k] = i;
        // is it still a partial answer?
        if (c.isPartialAnswer(s, k+1)) {
            // is it a full answer?
            if (c.isAnswer(s, k+1)) {
                c.handleAnswer(s);
            } else {
                // continue down this road
                paint(s, k+1, c);
            }
        }
    }
    // backtrack: we have exhausted all continuations of this coloring
    cout << std::string(k, ' ') << "closing k=" << k << endl;
}

int main() {
    Graph c = {4, 4, 
        {{0, 1, 0, 0, 0},
        {0, 0, 1, 1, 0},
        {0, 0, 0, 1, 0},
        {0, 0, 0, 0, 0},
        {0, 0, 0, 0, 0},}};

    Coloring s;
    paint(s, 0, c);
    return 0;
}

Отказ от ответственности: это канонический пример алгоритма отслеживания с возвратом, и он разработан больше для ясности, чем для производительности или расширяемости.