![]() |
Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | |
|
Раскраска связана с решением задач оптимизации: Задан граф G. Нужно раскрасить вершины графа в разные цвета так, чтобы смежные вершины были окрашены в разные цвета, а при раскраске использовался минимум разных цветов. Минимальное количество цветов связано с понятием хроматического числа.
Определения:
1. Множество вершин графа называется внутренне устойчивым, если у любой пары вершин этого множества отсутствует соединительное ребро.
2. Множество вершин графа называется максимальным внутренне устойчивым, если при добавлении к нему одной вершины оно превращается во внутренне неустойчивое.
3. Множество вершин графа называется внутренне неустойчивым, если в нем найдется хотя бы одна пара вершин, связанная ребром.
Пример: Задан граф без петель. Выполним разбиение вершин графа на внутренне устойчивые взаимно непересекающиеся подмножества.
Вариантов несколько:
А1 = {1, 4} | А1 = {1, 5, 7} | А1 = {3, 5, 7} |
А2 = {2, 5, 8} | А2 = {2, 4, 8} | А2 = {2, 4,8} |
А3 = {3, 6} | А3 = {3, 6} | А3 = {1, 6} |
А4 = {7}
Тогда каждому множеству Ai в каждом варианте разбиений можно сопоставить свой цвет.
Варианты 2 и 3 требуют 3-х цветов, 1 – 4-х цветов для раскраски.
Граф называется K-хроматическим, если он допускает раскраску своих вершин в K цветов при условии, что смежные вершины окрашены в разные цвета.
Минимальное число K цветов, при котором граф ещё остается K-хроматическим, называется хроматическим числом. Его можно получить (как в примере) перебором всех вариантов разбиения множества вершин на множество взаимно непересекающихся внутренне устойчивых подмножеств. Выбирается вариант с минимальным числом подмножеств. Это и есть хроматическое число .
Дата публикования: 2015-07-22; Прочитано: 416 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!