Студопедия

КАТЕГОРИИ:

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


Раскраска графов




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

Хроматическое число пустого графа равно 1.
Хроматическое число .
Хроматическое число .

Алгоритм нахождения раскраски (хроматического числа)

1) Выделить все пустые подграфы графа.
2) Построить таблицу покрытий вершин графа пустыми подграфами.
3) Найти минимальное покрытие вершин графа пустыми подграфами (мощность минимального покрытия – это , а само покрытие определяет раскраску).

Пример


 

 
     
     
     
     
     
       


Поделиться:

Дата добавления: 2015-02-10; просмотров: 132; Мы поможем в написании вашей работы!; Нарушение авторских прав





lektsii.com - Лекции.Ком - 2014-2024 год. (0.006 сек.) Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав
Главная страница Случайная страница Контакты