Вы точно человек?
Раскраска графа — теоретико-графовая конструкция, частный случай разметки графа. При раскраске элементам графа ставятся в соответствие метки с учётом определённых ограничений; эти метки традиционно называются «цветами». В простейшем случае такой способ окраски вершин графа , при котором любым двум смежным вершинам соответствуют разные цвета, называется раскраской вершин. Аналогично раскраска рёбер присваивает цвет каждому ребру так, чтобы любые два смежных ребра имели разные цвета [ 1 ].
Первоначально раскраски графов были нужны для составления географических карт [1]. Сегодня же они в частности раскраска с использованием минимального количества цветов используются, например, для составления расписаний, распределения регистров в микропроцессорах, распараллеливания численных методов. Материал из Викиконспекты. Перейти к: навигация , поиск. Определение: Правильной раскраской англ. Основная статья : Хроматический многочлен.
Правильная вершинная рёберная раскраска — это раскраска вершин рёбер графа, при которой любые смежные вершины рёбра окрашены в разные цвета. Правильную вершинную раскраску часто называют просто раскраской графа. Граф называется k k k -раскрашиваемым, если существует правильная вершинная раскраска графа k k k цветами. Граф является 2 2 2 -хроматическим тогда и только тогда, когда он не содержит простых циклов нечётной длины.
