Задать вопрос юристу

§2.4. Раскраски графов. Планарность

Пусть задано несколько красок . Раскраской графа G называется правило, по которому каждой вершине графа присваивается номер , соответствующий краске, причем смежные вершины имеют разные номера.

Хроматическим числом графа G называется наименьшее число красок, требуемое для раскраски данного графа.

Для полного графа .

Граф называется бихроматичным, если для его раскраски требуется две краски ().

Теорема (Критерий бихроматичности). Для любого графа G эквивалентны условия:

(1) граф G бихроматичен;

(2) граф G двудольный;

(3) в графе G нет циклов нечетной длины.

Доказательство. Будем доказывать эквивалентность по схеме .

Пусть граф G бихроматичен. Нужно доказать, что в нем нет циклов нечетной длины. Предположим, что цикл нечетной длины существует: . В силу бихроматичности нечетные вершины одного цвета. Следовательно, вершины и одного цвета, но они смежные. Получили противоречие. Циклов нечетной длины нет.

Пусть в графе G нет циклов нечетной длины. Нужно доказать, что G двудольный. Пусть – компоненты связности графа G. Достаточно доказать, что каждая компонента связности является двудольным графом. Поэтому можно считать G связным графом, т.е. любые две вершины в нем соединены путем. Введем на множестве вершин графа V отношение “~” следующим образом:, если существует путь четной длины из вершины в вершину . Если из в существует путь четной длины, то из в не существует пути нечетной длины, иначе нашелся бы цикл нечетной длины.

Докажем, что “~” – отношение эквивалентности. Действительно, оно рефлексивно: (из в существует путь длины 0); симметрично: если , то (если из в существует путь четной длины, то существует путь четной длины из в ); транзитивно: если и , то (если существует пути четной длины из в и из в , то существует пути четной длины из в . Следовательно, множество вершин графа V разбивается на два класса эквивалентности V1 и V2 : V1 – множество вершин графа, до которых из фиксированной вершины а существует путь четной длины, V2 – множество вершин графа, до которых из фиксированной вершины а существует путь нечетной длины. Тогда концы произвольного ребра лежат в разных множествах V1 и V2, иначе для двух вершин одного множества существовал бы путь длины 1 по этому ребру. Следовательно, граф G двудольный.

Пусть G – двудольный граф. Нужно доказать, что он бихроматичен. Так как смежные вершины графа принадлежат разным долям, то вершины одной доли раскрасим в один цвет, второй – в другой. Теорема доказана.

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

Для полных графов

Если то, очевидно, .

Справедлива теорема Визинга. .

<< | >>
Источник: Дискретная математика. Лекции. 2016

Еще по теме §2.4. Раскраски графов. Планарность:

  1. Планарные графы
  2. 3.11. Одежда, раскраска и другие украшения
  3. Изоморфизм графов
  4. 3.1.4. Примеры графов. Операции над графами
  5. В.Н. Бурков, Д.А. Новиков. ЭЛЕМЕНТЫ ТЕОРИИ ГРАФОВ, 2001
  6. 6.2.2 Применение теории графов
  7. 3. ТЕОРИЯ ГРАФОВ
  8. 3.1. Элементы теории графов
  9. 1. Основные понятия теории графов
  10. Матрицы графов.
  11. 3.3.3. Минимальные остовные деревья нагруженных графов
  12. ряд примеров приложений теории графов.
  13. 3.1.3. Матричное задание графов. Матрицы смежности, инцидентности
  14. ЭЛЕМЕНТЫ ТЕОРИИ ГРАФОВ
  15. §2.2. Способы задания графов
  16. 2 Элементы теории графов
  17. 2.4. Графово-матричное представление взаимодействия популяций
  18. Алексеев В.В.. Элементы теории множеств и теории графов (Сборник задач и упражнений по курсу “Дискретная математика”), 2001
  19. Задачи для самостоятельного решения