|
|
Регистрация Восстановить пароль |
Повторная активизация e-mail |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
|
Опции темы | Поиск в этой теме |
24.12.2016, 15:05 | #1 |
Новичок
Джуниор
Регистрация: 24.12.2016
Сообщений: 1
|
Раскраска графа, хроматическое число
Здравствуйте, есть код для нахождения хроматического числа. До 4 вершин работает правильно, но с 5 и выше находит не правильно, в данном примере необходимо 3 цвета, а он находит 2. Помогите исправить, пожалуйста:
#include "stdafx.h" #include <iostream> using namespace std; int main() { setlocale(LC_ALL, "Russian"); const int n = 5; int i, j; int mi[n][n] = { 0, 1, 1, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 1, 0, 1, 1, 0, 1, 0, 0, 1, 1, 0 }; cout << "Вывод матрицы: " << endl; for (i = 0; i < n; ++i) { for (j = 0; j < n; ++j) { cout << mi[i][j] << ' '; } cout << endl; } //Хроматическое число: 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]; cout << "\nХроматическое число графа равно: " << max<<endl; return 0; } |
25.12.2016, 09:10 | #2 |
Форумчанин
Регистрация: 25.01.2015
Сообщений: 472
|
Мне думается, что эта задача решается полным перебором, а не "распространением волны".
Перебор заключается в том, что назначаем хроматическое число и перебором пытаемся раскрасить вершины, для удовлетворения этого условия. Получилось - хорошо, нет - увеличиваем предполагаемое хроматическое число. Вот уже по поводу выбора следующего предполагаемого хроматического числа возможны алгоритмы: 1. На 1 больше предыдущей гипотезы. 2. Методом половинного деления. Т.е. изначально имеется интервал Xmin=1 Xmax=n. Проверяется гипотеза для X=(Xmin+Xmax)/2 и делается выбор для нового диапазона [Xmin, Xmax]. |
25.12.2016, 10:29 | #3 |
Форумчанин
Регистрация: 25.01.2015
Сообщений: 472
|
Удалил предыдущую запись - т.к. она была явно ошибочной.
------------------------------------ По ссылке http://it.kgsu.ru/C_DIN/din_0116.html описывается алгоритм нахождения хроматического числа. Видно, что он гораздо сложнее того, что вы предлагаете. В вашей программе незавершённая попытка получения начальной раскраски, и отсутствует дальнейший перебор. Последний раз редактировалось FPaul; 25.12.2016 в 11:37. Причина: Уточнение. |
Похожие темы | ||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
раскраска ребер графа | blackrabbit | C# (си шарп) | 0 | 13.05.2013 11:36 |
создание графа по матрице и поиск кратчайшего пути из одного графа в другой | lexflax | Общие вопросы C/C++ | 1 | 06.09.2012 07:32 |
Раскраска графа (или как найти баг) | KANDRAT | Помощь студентам | 0 | 07.05.2012 23:44 |
Раскраска графа(поиск с возвратом) | Electr0Fly | Помощь студентам | 0 | 22.03.2011 01:58 |
раскраска графа | PianeR | Помощь студентам | 0 | 11.11.2010 23:15 |