ХРОМАТИЧЕСКОЕ ЧИСЛО ГРАФА
Будем рассматривать неориентированные графы без петель. Граф G называется p- раскрашиваемым, если все его вершины можно раскрасить с использованием p цветов так, чтобы никакие две соседние вершины G не были окрашены одинаково.
Иначе говоря, p- раскраска графа G =(V, U) ¾ это такое разбиение множества V на p непустых подмножеств V 1,..., Vp, что всякое ребро из U соединяет вершины из разных множеств разбиения.
Например, граф, изображенный на рис. 5.30, является
3- раскрашиваемым и 4- раскрашиваемым, но не является
2- раскрашиваемым.
Рис. 5.30
Дата добавления: 2015-09-27 | Просмотры: 435 | Нарушение авторских прав
|
