ЕГЭОГЭЕНТ
РУҚА
Задание № 9 · ОГЭ

Раскраска графа

Как разделить вершины графа на классы без конфликтов цветов
2 мин чтенияСложность: Обновлено 29 сентября 2026

Раскраска графа — это назначение цветов его вершинам так, чтобы любые смежные вершины имели разные цвета. Такая раскраска разбивает множество вершин на цветовые классы: внутри одного класса нет соединённых ребром вершин.

Раскраска графаТермин связан с обычной раскраской: цвет вершины обозначает её принадлежность к одному из классов.
Правильная вершинная раскраска графа — это такое отображение каждой вершины в один из цветов, при котором концы любого ребра окрашены в разные цвета. Если использовано не более \(k\) цветов, говорят о правильной \(k\)-раскраске графа.

Для понимания раскраски нужны граф и его элементы: вершины и рёбра. Проверяют конфликт цветов по смежности вершин — две вершины смежны, если между ними есть ребро.

Хроматическое число

Хроматическое число графа — минимальное количество цветов, достаточное для его правильной раскраски. Его обозначают \(\chi(G)\). Если граф можно раскрасить одним цветом, в нём нет рёбер. Если в графе есть хотя бы одно ребро, нужны минимум два цвета.

\[\chi(G)=\min\{k\mid G\text{ имеет правильную }k\text{-раскраску}\}\]
№
Пример

Пусть граф имеет вершины \(A\), \(B\), \(C\), причём рёбра соединяют \(A\) с \(B\) и \(B\) с \(C\), а \(A\) и \(C\) не соединены. Можно присвоить \(A\) и \(C\) красный цвет, а \(B\) — синий. Получается два цветовых класса: \(\{A,C\}\) и \(\{B\}\). Поэтому \(\chi(G)=2\).

!
Не путайте

Раскраска не требует, чтобы все цвета использовались одинаковое число раз. Важно только отсутствие одинаковых цветов у смежных вершин. Также раскраска графа отличается от графа переходов: граф переходов описывает состояния и переходы между ними, а раскраска лишь распределяет вершины по классам.

Проверьте себя

В графе есть одно ребро между вершинами \(A\) и \(B\). Каково его хроматическое число?

Главное за минуту

Главное

  • Правильная раскраска назначает цвета вершинам так, чтобы смежные вершины имели разные цвета.
  • Цветовые классы состоят из вершин, среди которых нет рёбер.
  • Хроматическое число \(\chi(G)\) — минимальное количество цветов для правильной раскраски графа.