Rox11vi
1

Алгоритм с перекраской двуцветных подграфов

19.04.2011, 23:27. Показов 515. Ответов 0
Метки нет (Все метки)

Здравствуйте! Помогите пожалуйста реализовать алгоритм на си++, точнее мне нужна программа раскраски вершин графа. Она должна выводить число шагов, количество цветов и время. Есть псевдокод алгоритма:

Вход: Граф G с ПН – упорядоченными вершинами.
Выход: Субоптимальная раскраска вершин.

начало
j∶=1;
для i от 1 до n шаг 1 цикл
начало
m:= наименьший номер цвета, отсутствующего на вершинах, смежных с вершиной υ_i;
если m<=j то
окрасить вершину v_i в цвет c_m;
иначе начало
К:= множество цветов, представленных ровно один раз на вершинах, смежных с вершиной v_i;
Если найдется пара α,β∈K, такая, что верши¬ны v_α и v_β, смежные с v_i, и окрашенные в цвета α и β, не соединены двуцветной цепью то
начало
перекрасить ту компоненту двуцветного графа G_αβ, которая содержит вершину v_α;
окрасить вершину v_i в цвет α;
конец
иначе начало
j≔j+1;
окрасить вершину v_i в цвет c_j;
конец
конец
конец цикла;
конец
__________________
Помощь в написании контрольных, курсовых и дипломных работ здесь
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
19.04.2011, 23:27
Ответы с готовыми решениями:

Число подграфов
Здравствуйте. Как найти число подграфов в полном графе с n вершинами ? Спасибо.

Поиск элементарных подграфов
Всем привет! Сразу оговорюсь, возможно я не совсем корректно обозвал тему, просто потому что не...

Найти число подграфов
Найти число подграфов K_{7} изоморфных графу C_{4} 840?

Найдите количество остовных подграфов
Найдите количество остовных подграфов, являющихся деревьями, в полных подграфах с 3-мя, 4-мя, 5-ю,...

0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
19.04.2011, 23:27

Найдите число различных остовных подграфов графа
Вот такие задачи задали. Подскажите как решить 2. Пусть F и H — подграфы помеченного...

Определить все варианты остовных подграфов полного графа с заданным количеством ребер
Всем привет! Помогите, пожалуйста:) Не могу никак понять алгоритм действий для выполнения задания...

Нужен алгоритм поиска пути в этом лабиринте (будь то волновой алгоритм или алгоритм правой/левой руки )
#include &quot;stdafx.h&quot; #include &lt;iostream&gt; #include &lt;conio.h&gt; using namespace std; void lab...

Волновой алгоритм поиска (Алгоритм A* / Алгоритм А стар)
Хочу разработать алгоритм для решения головоломки с подвижными дисками (перестановочная...

Линейный алгоритм, Алгоритм с ветвлениями, Циклический алгоритм Линейный алгоритм
Линейный алгоритм, Алгоритм с ветвлениями, Циклический алгоритм Линейный алгоритм 1. Объясни, что...

Разработать алгоритм методом пошаговой детализации и программу, реализующую этот алгоритм
Расставить строки данной матрицы в порядке возрастания наибольших элементов в строках.


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
1
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2022, CyberForum.ru