- •Глава VII
- •§ 43. Эйлеровы графы
- •Глава VIII
- •§ 45. Графическая последовательность
- •§ 46. Критерии графичности последовательности
- •§ 47. Реализация графической последовательности с максимальной связностью
- •§ 48. Гамильтонова реализация графической последовательности
- •§ 49. Расщепляемые графы
- •§ 50. Пороговые графы
- •§ 51. Пороговое разложение графа
- •§ 52. Степенное множество графа
- •Глава IX
- •§ 53. Правильная раскраска
- •§ 54. Оценки хроматического числа
- •§ 56. Раскраска ребер
- •§ 57. Связь матроидных разложений графов с раскрасками
- •§ 58. Раскраска планарных графов
- •§ 59. Проблема четырех красок
- •§ 60. Другие подходы к раскраске графов
- •§ 61. Совершенные графы
- •§ 62. Триангулированные графы
- •Глава X Ориентированные графы
- •§ 63. Основные определения
- •§ 64. Полустепени исхода и полустепени захода
- •§ 65. Обходы
- •§ 66. Пути
- •§ 67. База и ядро
- •Глава XI
- •§ 68. Основные определения и свойства
- •§ 69. Независимые множества
- •§ 70. Раскраски
- •§ 71. Реализации гиперграфа
- •Глава XII
- •§ 72. Предварительные сведения
- •§ 73. Поиск в глубину
- •§ 74. Отыскание двусвязных компонент
- •§ 75. Минимальный остов
- •§ 76. Кратчайшие пути
- •§ 77. Наибольшие паросочетания и задача о назначениях
- •§ 78. Труднорешаемые задачи
§ 52. Степенное множество графа
Степенным множеством графа называется множество степеней его вершин. От степенной последовательности о множество отличается тем, что в нем не учитывается число вершин, имеющих заданную степень, тогда как в степенной последовательности каждое число фигурирует столько раз, степенью скольких вершин оно является.
С тепенное множество графа G обозначим через S(G). Так, для графа G, изображенного на рис. 52.1, S(G) = = {1, 2, 3}.
Хотя степенная последовательность графа удовлетворяет определенным условиям, однако степенным множеством графа может быть произвольное множество. Об этом свидетельствует следующая
Теорема 52.1. Любое конечное множество S натуральных чисел является степенным множеством некоторого порогового графа. Минимальный порядок таких графов равен s +1, где s — максимальное число из множества S. Очевидно, что из этой теоремы вытекает
Следствие 52.2. Любое конечное множество целых, неотрицательных чисел является степенным множеством некоторого графа.
Д оказательство теоремы 52.1. Если S(G) = = S, то \G\ ≥ s+ 1, так что нужно только доказать существование подходящего графа G. Утверждение тривиально для одноэлементного множества S, поскольку S(Kn)={n — 1}. Пусть теперь
и пусть, для определенности, п = 2р — четное число. Нужный граф будем искать в виде
где КХ°Н- граф, полученный из графа Н добавлением х доминирующих вершин, а ОУ°Н — граф, полученный из графа Н добавлением у изолированных вершин. Любой граф вида (1) является пороговым. Попытаемся подобрать числа ха и yβ в выражении (1) так, чтобы выполнялось - равенство S(G) = S. Для этого должно быть
О чевидно, что система уравнений (2) относительно неизвестных хi, yj (i =1,p,j =1, р) имеет решение, все координаты которого положительны:
Подставив в выражение (1) числа, определяемые равенствами (3), получим граф G, для которого S(G)=S. Число его вершин равно
Д ля нечетного п = 2р + 1 построение аналогично, толь-to вместо формулы (1) используется формула
Глава IX
Раскраски
§ 53. Правильная раскраска
Пусть G — некоторый граф, k — натуральное число. Произвольная функция вида
f:VG->{i, 2, ..., k} называется вершинной k-раскраской, или просто k-раскраской, графа G. Если позволяет контекст, то k в этом определении опускается. Раскраска называется правильной, если j(u) ≠ f(v) для любых смежных вершин и и v. Граф, для которого существует правильная k-раскраска, называется k-раскрашиваемым (или раскрашиваемым к цветами). В определении раскраски вместо множества {1, 2, ..., к} можно взять произвольное k-элементное множество.
П равильную k-раскраску графа можно трактовать как окрашивание каждой его вершины в один из k цветов, при этом смежные вершины должны получать различные цвета. Поскольку функция ƒ не обязательно сюрьективна, то при k-раскраске фактически может быть использовано менее k цветов. Таким образом, правильную k-раскраску графа G можно рассматривать как разбиение
множества вершин VG на не более чем k непустых классов, каждый из которых является независимым множеством. Классы этого разбиения называются цветными классами.
Минимальное число k, при котором граф G является k-раскрашиваемым, называется хроматическим числом этого графа и обозначается χ(G). Если χ(G) = k, то граф называется k-хроматическим. Правильная k-раскраска графа G при k = χ(G) называется минимальной.
В качестве иллюстрации рассмотрим граф G, изображеный на рис. 53.1, где указана одна из правильных раскрасок. Меньшим числом цветов этот граф раскрасить правильно нельзя. Действительно, граф содержит цикл (v1 ,v2 , v3, v4 , v5 , v1) для правильной раскраски которого нужно не менее трех цветов, а для вершины v 6 требуется новый цвет. Итак, χ (G) = 4.
Р ассмотрим некоторые практические задачи, сводящиеся к правильной раскраске графов.
1. Задача составления расписаний. Предположим, что нужно прочесть несколько лекций за кратчайшее время. Чтение каждой лекции в отдельности занимает один час, но некоторые лекции не могут
читаться одновременно (например, их читает один и тотже лектор). Построим граф G, вершины которого би-тивно соответствуют лекциям, и две вершины смежны тогда и только тогда, когда соответствующие лекции нельзя читать одновременно. Очевидно, что любая правильная раскраска этого графа определяет допустимое расписание: лекции, соответствующие вершинам графа, составляющим етной класс, читаются одновременно. И, обратно, любое пустимое расписание определяет правильную раскраску графа G. Оптимальные расписания соответствуют минимальным раскраскам, а число часов, необходимое для проведения всех лекций, равно χ (G)
2. Задача распределения оборудования. Заданы множества V = {v1 , v2 , ..., vn} и S = {s1 , s2 , ..., sm} работ и механизмов соответственно. Для выполнения каждой из работ требуется некоторое время, одинаковое для всех работ, и некоторые механизмы. При этом никакой из механизмов не может быть одновременно занят в нескольких работах. Нужно распределить механизмы так, чтобы будущее время выполнения всех работ было минимальным. Построим граф G, положив VG = V и объявив вершины vi и vj (i ≠ j) смежными тогда и только тогда, когда для выполнения работ vi и vj , требуется хотя бы один общий механизм. При правильной раскраске графа G ра-тьт. соответствующие вершинам одного пвета. Можно выполнять одновременно, а наименьшее время выполнения всех работ достигается при минимальной раскраске.
3. Задача о проектировании коробки скоростей. Коробка скоростей — механизм для изменения частоты вращения ведомого вала при постоянной частоте вращения ведущего. Это изменение происходит за счет того, что находящиеся внутри коробки шестерни (зубчатые колеса) вводятся в зацепление специальным образом. Одна из задач, стоящая перед конструктором коробки, заключается в минимизации ее размеров, а это часто сводится к минимизации числа валов, на которых размещаются шестерни.
Построим граф G, вершины которого биективно соответствуют шестерням. Если по какой-то причине две шестерни не должны находиться на одном валу (например, они могут быть в зацеплении, или их общий вес велик для одного вала и т. д.), то соответствующие вершины графа соединим ребром. Вершины, имеющие один цвет при правильной раскраске этого графа, определяют шестерни, которые могут находиться на одном валу, а хроматическое число χ (G) равно минимальному количеству валов, нужных для проектируемой коробки.
Для некоторых графов, хроматические числа найти несложно. Например, χ (Кп) = п, χ (Кп — е) = п—1, χ (Kn,m) =2, χ (С2п+1) = 2, χ (С2n+1) = 3.
Очевидно, что граф является 1-хроматическим тогда и только тогда, когда он пустой, а 2-хроматическим — когда он двудольный и непустой. Обычно 2-хроматический граф называют бихроматическим. Поэтому теорему Кёнига о двудольных графах можно сформулировать в следующем виде:
Теорема 53.1. Непустой граф является бихроматическим тогда и только тогда, когда он не содержит циклов нечетной длины.
Задачи определения хроматического числа и построения минимальной раскраски произвольного графа являются очень сложными, эффективные алгоритмы их решения неизвестны. Рассмотрим простой алгоритм построения правильной раскраски, в ряде случаев приводящий к раскраскам, близким к минимальным.
Алгоритм последовательной раскраски.
Произвольной вершине v1 графа G припишем цвет 1.
Если вершины v1 , v2 , ..., vi раскрашены l цветами 1, 2, ..., l, l ≤ i, то новой произвольно взятой вершине vi+1 припишем минимальный цвет, не использованный при раскраске вершин из ее окружения.
Раскраека, к которой приводит описанный алгоритм, называется пдследовательной. Очевидно, что это — правильная раскраска. Для некоторых классов графов (например, полных однодольных) последовательная раскраска является минимальной. В общем случае это не так.
Следующая теорема сводит задачу построения правильной раскраски графов к аналогичной задаче для двухсвязных графов.
Теорема 53.2. Если каждый блок графа к-раскрашиваем, то и сам граф также к-раскрашиваем.
Воспользуемся индукцией по числу блоков рассматриваемого графа. Для графа, являющегося блоком, утверждение тривиально. Предположим, что теорема верна для графов, состоящих из m ≥ 1 блоков. Пусть теперь G — граф, имеющий ровно m + 1 блоков, В — один из его концевых блоков, Н — объединение всех остальных блоков. По индуктивному предположению оба графа В и Н являются k-раскрашиваемыми. Зафиксируем для каждого из них правильную k-раскраску.
Графы В и Н имеют ровно одну общую вершину v. Если ее цвета в обеих фиксированных k-раскрасках совпадают, то получена правильная k-раскраска графа G. В противном случае нужно очевидным образом переставить цвета в одной из фиксированных раскрасок.