Раскрашиваем вершины и рёбра графа

Известна задача о раскраске графа, в наиболее популярной её постановке нам требуется раскрасить вершины плоского графа так, чтобы никакие две смежные (соединённые между собой) вершины не были закрашены одним цветом.

В нашем подходе используется не более заданного количества m цветов, граф из N вершин задан как динамическая матрица размерностью N*N, состоящая из нулей (между вершинами нет ребра) и единиц (есть ребро).

Ниже приводится наспех сделанная программка, проверенная в консоли Visual Studio 2015, для простого теста (показан в коде) и классического веретена Мозера сработало. Немного пояснений есть в коде, он выглядит довольно просто.

#include <iostream> 
#include <string> 
#include <cstdlib> 
using namespace std;

//Служебные функции

void printSolution(int color[], int V) {
 cout << "Solution:" << endl;
 for (int i = 0; i < V; i++) cout << "Color("<< i <<")=" << color[i] << endl;
}

void error(int code) {
 string msg[] = {
  "OK, normal shutdown",
  "No memory for graph!"
 };
 if (code > -1 && code < sizeof(msg)) cout << endl << msg[code];
 else cout << endl << "Unknown error!";
 cin.get(); exit(code);
}

//Решение

bool isSafe(int v, int **graph, int V, int color[], int c) {
 for (int i = 0; i < V; i++)
  if (graph[v][i] != 0 && c == color[i]) return false;
 //ребро существует и цвет уже использован
 return true;
}

bool graphColoringUtil(int **graph, int V, int m, int color[], int v) {
 if (v == V) return true; //Всё раскрашено
 for (int c = 1; c <= m; c++) {
  if (isSafe(v, graph, V, color, c)) {
   color[v] = c;
   if (graphColoringUtil(graph, V, m, color, v + 1) == true) return true;
   color[v] = 0;
  }
 }
 return false;
}

bool graphColoring(int **graph, int V, int m) {
 //Рекурсивное решение проблемы m цветов
 int *color = new int[V];
 if (!color) error(1);
 for (int i = 0; i < V; i++) color[i] = 0;
 if (graphColoringUtil(graph, V, m, color, 0) == false) {
  return false;
 }
 printSolution(color, V);
 return true;
}

int main() {
 const int V = 4; //количество вершин теста 1
 int **graph = new int *[V];
 if (!graph) error(1);
 for (int i = 0; i < V; i++) {
  graph[i] = new int[V];
  if (!graph[i]) error(1);
  for (int j = 0; j < V; j++) graph[i][j] = 0;
 }

 // (3)---(2)
 //  |   / |
 //  |  /  |
 //  | /   |
 // (0)---(1)
 graph[0][1] = graph[0][2] = graph[0][3] =
  graph[1][0] = graph[1][2] =
  graph[2][0] = graph[2][1] = graph[2][3] =
  graph[3][0] = graph[3][2] = 1; //Переписываем связи в граф

 int m = 3; // Количество цветов
 if (!graphColoring(graph, V, m)) 
  cout << "No solution found!" << endl;

 //Веретено Мозера - минимальный граф, которому нужно 4 краски
 const int N = 7;
 int **moser = new int *[N];
 if (!moser) error(1);
 for (int i = 0; i < N; i++) {
  moser[i] = new int[N];
  if (!moser[i]) error(1);
  for (int j = 0; j < N; j++) moser[i][j] = 0;
 }
 //ABCDEFG
 //0123456
 moser[0][1] = moser[0][2] = moser[0][4] = moser[0][5] =
 moser[1][0] = moser[1][2] = moser[1][3] =
 moser[2][0] = moser[2][1] = moser[2][3] =
 moser[3][1] = moser[3][2] = moser[3][6] =
 moser[4][0] = moser[4][5] = moser[4][6] =
 moser[5][0] = moser[5][4] = moser[5][6] =
 moser[6][3] = moser[6][4] = moser[6][5] = 1;

 if (!graphColoring(moser, N, 3)) 
  cout << endl << "No solution found!" << endl << endl; //Решения нет тремя цветами
 
 graphColoring(moser, N, 4); //Решение есть четырьмя цветами!

 error(0);
}

веретено Мозера - минимальный граф, для раскраски которого нужно четыре цвета

Вот другая версия, с контейнерами STL, для того же исходного графа Мозера, но раскрашиваем здесь рёбра.

#include <iostream>
#include <vector>
#include <queue>
#include <set>
using namespace std;

//Определить цвета ребер
void colorEdges(int ptr, vector<vector<pair<int, int> > >& graph,
  vector<int>& edgeColors, bool isVisited[]) {
 queue<int> q;
 int c = 0;
 set<int> colored;
 if (isVisited[ptr]) return;
 isVisited[ptr] = 1;
 for (int i = 0; i < graph[ptr].size(); i++) {
  if (edgeColors[graph[ptr][i].second] != -1)
   colored.insert(edgeColors[graph[ptr][i].second]);
 }
 for (int i = 0; i < graph[ptr].size(); i++) {
  if (!isVisited[graph[ptr][i].first]) q.push(graph[ptr][i].first);
  if (edgeColors[graph[ptr][i].second] == -1) {
   while (colored.find(c) != colored.end()) c++;
   edgeColors[graph[ptr][i].second] = c;
   colored.insert(c);
   c++;
  }
 }
 while (!q.empty()) {
  int temp = q.front();
  q.pop();
  colorEdges(temp, graph, edgeColors, isVisited);
 }
 return;
}

int main() {
 set<int> empty;
 vector <vector<pair<int, int> > > graph;
 vector <int> edgeColors;
 bool isVisited[100000] = { 0 };

 int ver = 7;
 int edge = 11;
 graph.resize(ver);
 edgeColors.resize(edge, -1);

 // Введем ребра и вершины
 // Если граф не ориентирован, вводим обе пары, 
 // (x, y) и (y, x) 
 // graph[x].push_back(make_pair(y, i)); 
 // graph[y].push_back(make_pair(x, i)); 
 graph[0].push_back(make_pair(1, 0)); 
 graph[1].push_back(make_pair(0, 0));
 graph[0].push_back(make_pair(4, 1));
 graph[4].push_back(make_pair(0, 1));
 graph[0].push_back(make_pair(2, 2));
 graph[2].push_back(make_pair(0, 2));
 graph[0].push_back(make_pair(5, 3));
 graph[5].push_back(make_pair(0, 3));

 graph[1].push_back(make_pair(2, 4));
 graph[2].push_back(make_pair(1, 4));
 graph[1].push_back(make_pair(3, 5));
 graph[3].push_back(make_pair(1, 5));

 graph[2].push_back(make_pair(3, 6));
 graph[3].push_back(make_pair(2, 6));

 graph[3].push_back(make_pair(6, 7));
 graph[6].push_back(make_pair(3, 7));

 graph[4].push_back(make_pair(5, 8));
 graph[5].push_back(make_pair(4, 8));
 graph[4].push_back(make_pair(6, 9));
 graph[6].push_back(make_pair(4, 9));

 graph[5].push_back(make_pair(6, 10));
 graph[6].push_back(make_pair(5, 10));

 colorEdges (0, graph, edgeColors, isVisited);

 for (int i = 0; i < edge; i++)
  cout << "Edge " << i + 1 << " is of color "
  << edgeColors[i] + 1 << "\n";

 cin.get(); return 0;
}

31.05.2019, 19:43 [1759 просмотров]