Алгоритм приближенной раскраски графа - C (СИ)
Формулировка задачи:
Необходимо раскрасить граф
вот есть и на 3-ем пункте застрял ,может как то по другому представить вершины что посоветуете???
алгоритм приближенной раскраски:
1. Вычислить степени вершин. Положить K=1.Пример. 2. Просмотреть вершины в порядке не возрастания степеней и окрасить первую неокрашенную вершину в цвет № K. 3. Просмотреть вершины в порядке не возрастания степеней и окрасить в цвет №К все вершины, которые не смежны вершинам, уже окрашенным в цвет №К. 4. Если все вершины окрашены, то К-искомое хроматическое число. Пример.Иначе К=К+1 и переход к пункту 2. http://www.tisbi.ru/resource/lib/graph/TEOR4.htm#metka42 или тут http://rain.ifmo.ru/cat/view.php/the.../coloring-2004 вроде не сложно ну что то не как не соображу , представил каждую вершину в виде структуры:struct graf{
int stepeni;
int color;
int number;
};Решение задачи: «Алгоритм приближенной раскраски графа»
textual
Листинг программы
#include <iostream>
int main()
{
setlocale(LC_ALL, "Russian");
const int n(6);
int i, j;
int mi[n][n] = { 0, 1, 0, 1, 1, 0,
1, 0, 1, 1, 0, 0,
0, 1, 0, 1, 1, 1,
1, 1, 1, 0, 1, 0,
1, 0, 1, 1, 0, 1,
0, 0, 1, 0, 1, 0 };
for(i = 0; i < n; ++i, std::cout<<std::endl)
for(j = 0; j < n; ++j)
std::cout<<mi[i][j]<<' ';
int col[n];
for(i = 0; i < n; ++i)
col[i] = 1;
for(i = 0; i < n; ++i)
for(j = i + 1; j < n - 1; ++j)
if(mi[i][j] == 1 && col[j] == col[i])
col[j] = col[i] + 1;
int max = col[0];
for(j = 1; j < n; ++j)
if(max < col[j])
max = col[j];
std::cout<<"\nХроматическое число графа равно "<<max;
std::cin.get();
return 0;
}
Объяснение кода листинга программы
- Установка локали на русский язык
- Объявление константы n, которая определяет размер графа
- Объявление переменных i, j для использования в циклах
- Объявление двумерного массива mi[n][n] и инициализация его значениями 0 и 1, которые представляют собой цвета вершин графа
- Вывод значений массива mi на экран
- Объявление одномерного массива col[n] для хранения цветов вершин графа
- Инициализация всех элементов массива col значением 1
- Проверка цветов соседних вершин графа и изменение цвета при необходимости
- Поиск максимального цвета в массиве col
- Вывод максимального цвета на экран
- Получение ввода от пользователя для завершения работы программы
- Возврат значения 0, что означает успешное завершение программы