Мои Конспекты
Главная | Обратная связь

...

Автомобили
Астрономия
Биология
География
Дом и сад
Другие языки
Другое
Информатика
История
Культура
Литература
Логика
Математика
Медицина
Металлургия
Механика
Образование
Охрана труда
Педагогика
Политика
Право
Психология
Религия
Риторика
Социология
Спорт
Строительство
Технология
Туризм
Физика
Философия
Финансы
Химия
Черчение
Экология
Экономика
Электроника

Переборный алгоритм раскраски





Помощь в ✍️ написании работы
Поможем с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой

Рассмотрим алгоритм решения задачи о раскраске, основанный на полном рекурсивном переборе различных вариантов. Данный алгоритм оперирует деревом вариантов, обход которого позволяет найти точное решение (хроматическое число графа). Нахождение точного решения, однако, обеспечивается экспоненциальной временной сложностью алгоритма.

Выберем в данном графе G две несмежные вершины и и построим два новых графа: , получающийся добавлением ребра к графу G, и, получающийся из G слиянием вершин x и y. Операция слияния состоит в удалении вершин x и y и добавлении новой вершины z и ребер, соединяющих ее с каждой вершиной, с которой была смежна хотя бы одна из вершин x, y. На рис. 2 показаны графы и , получающиеся из графа G, изображенного на рис. 1, с помощью этих операций, если в качестве x и y взять вершины a и .


Рис. 2.

 

Если в правильной раскраске графа G вершины x и y имеют разные цвета, то она будет правильной и для графа . Если же цвета вершин x и y в раскраске графа G одинаковы, то граф можно раскрасить в то же число цветов: новая вершина z окрашивается в тот цвет, в который окрашены вершины x и y, а все остальные вершины сохраняют те цвета, которые они имели в графе G. И наоборот, раскраска каждого из графов , , очевидно, дает раскраску графа G в то же число цветов. Поэтому , что дает возможность рекурсивного нахождения раскраски графа в минимальное число цветов. Заметим, что граф имеет столько же вершин, сколько исходный граф, но у него больше ребер. Поэтому рекурсия, в конечном счете, приводит к полным графам, для которых задача о раскраске решается тривиально.

 

Доверь свою работу ✍️ кандидату наук!
Поможем с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой



Поиск по сайту:







©2015-2020 mykonspekts.ru Все права принадлежат авторам размещенных материалов.