Введение в прикладную комбинаторику, Кофман А. (984071), страница 27
Текст из файла (страница 27)
120. В силу (30.!5) Фз — — бе!а + аЩ$ + аЬа(Ь + абедЬ + асьзз)$ + + ай!76+ Ьь!е!$+ аса7еф = 1 (33,8) Теорема 1 (Кйниг). Граф является 2-хроматическим тогда и только тогда, когда он не содержит циклов нечетной длины. Достаточность. Пусть в графе 6 = (Е, (з) нет циклов нечетной длины.
Будем считать, что граф связный (в противном случае можно рассмотреть отдельно каждую компоненту связности). Раскрашиваем его следуюшим образом: 1) произвольную Рис. 187. вершину Хо окрасим цветом С,; 2) если вершина Хт окрашена цветом Сь то все смежные с ней вершины окрасим цветом С, а Х если Х, окрашена цветом Сз, то все смежные с ней вершины 3 окрасим цветом Сь Так как граф связный, то в конце концов все его вершины будут окрашены, причем никакая вершина не будет окрашена двумя разными цветами, так как в графе нет циклов нечетной длины. Необходимость. Если граф 2-хроматический, то он не содержит циклов нечетной длины, так как иначе вершины такого цикла нельзя раскрасить двумя цветами требуемым образом. Т е о р е м а П ') . Для того чтобы граф ст = ( Е, О) был р-хроматическим, необходимо и достаточно, чтобы существовал соответствующий ему симметрический граф 6 без петель, допускающий такую функцию Гранди д(Х), что шах д (Х) ( р — 1.
(33. 17) ') Доказательство заимствовано из 18!. 198 Условие достаточно. Если такая д(Х) существует, то каждому целому числу от О до р — 1 сопоставим некоторый цвет и окрасим вершину Х; в соответствии со значением д(Х;). Условие необходимо. Если граф р-хроматический, то покажем, что существует функция Гранди, максимальное значение которой не превосходит р — 1. Пусть Е,, Е„ ..., Ер, — такие подмножества, что вершины каждого из них окрашены одинаково. Каждую вершину Хг ен Его и ) 1, не смежную ни с какой вершиной из Е„присоединяем к Ео и получаем Еа =э Ео.
Затем каждую вершину Х, еи (Еа — Ео), й) 2, не смежную ни с какой вершиной из Е, — Е'„присоединяем к Е, — Ео и получаем Е1, Аналогично получаем Ет, Ез, ... Тогда функция д(Х,), равная й, если С Х~ен Еь, — функция Гранди, удов- l летворяюшая (33.! 7). Эта теорема показывает, что оты- А р скание функции Гранди для симме- Оа Оо трического графа без петель сводится к задаче о раскраске соответствующего неориентированного гра- О фа (любой раскраске отвечает Н функция Грандн) и, обратно, любой функции Гранди отвечает некоторая ОС раскраска графа. Рис.
138. Например, для симметрического графа без петель на рис. 138, соот. ветствующего неориентированному графу на рис. 138, исходя из раскраски, заданной Чг~ на рис. 137, получаем функцию Гранди соответствием: г О, )а — ь1, о ~2. Можно действовать и в обратном порядке. Теорем а 111. Пусть у(6) — хроматическое число графа 6 = (Е, !)), соответствующего графу 6 без петель. Тогда число ') внутренней устойчивости а(6) удовлетворяет неравенству а(6) у(6))! Е !. (33.18) В самом деле, Е можно разбить на у(6) устойчивых множеств, каждое из которых образовано из вершинами одного цвета, 1= 1, 2...
у. Тогда ~а)=,.к,.к ....к,< ~ят ~о)-'; ... к (й) = у (6) а (6). (33.19) Хроматический класс. Рассмотрим граф 6=(Е, О) и целое число д такое, что: 1) ребра графа можно окрасить д цветами ') Так как внутренняя устойчивость не связана с ориентацией цуг, то в а(6) можно заменить 0 на б. 199 так, что смежные ребра не окрашиваются одинаково; 2) зто невозможно осуществить <) — 1 цветами. Число <) называют хроматическим классом графа 6. "в Рис. 140 Рис. 139. Например, хроматический класс графа на рис. 139 равен 5: необходимо 3 цветов для требуемой раскраски.
Вычисление хроматического класса графа 6 сводится к задаче нахождения хроматического числа графа6'=(О, Ч) = О! Об Об О< Об Об О7 Об <А,ВХА,ВХВ,СХВО)(С,О)<СВ)<СВ)<В,В А В С В К 7 О«А В) С<и<А,О) Об(В,С) О, <вш) ()б (С, П) С<б(С,В) О,(С,В) Об<В В) Рис.
141, Рис. 142. =(О, Г"), вершинами которого служат ребра 6 и й)~ Г*й<, если й< и и) — смежные ребра в 6. На рис. 140 показано, как получить 6' (изображенный пунктиром) из 6 и тем самым раскраску всех ребер о цветами. Пусть 6=(Е, О), (33.20) где Е = (А, 8, С, 1), Е, и"), (33.21) С) =!й1 йз~ Йз Й4 мз~ йз Йг йз) ° (33.22) На рис, 141 и 142 изображены булевы матрицы графов 6 и 6* соответственно.
УПРАЖНЕНИЯ ЗЗА. Найти хроматическое число и раскрзсить вершины графов; а) б) б) ЗЗБ. Указать хроматический класс и раскрасить ребра графов из упражнения ЗЗА, ЗЗВ. Установить, польвуяоь теоремой Кенига, какие из графов являются 2-хроматическими. л) б) б) ЗЗГ. Каждому из графов из упражнения ЗЗВ сопоставить симметрический ориентированный граф без петель и для них найти функции Гранди и соответствующие им раскраски. ЗЗД. Вычислить сг(6) и у(6) графов, полученных в упражнении ЗЗГ. $34. Клика. Максимальная клика Пусть 6 = (Е, Г) — симметрический граф без петель и 6 = (Е, ٠— соответствующий ему неориентированный граф. Обозначим через 6*=(Е, О*) граф, дополнительный к 6, и через 6* — неориентированный граф, соответствующий 6*.
Подмножество Е» ~ Е называется кликой, если подграф 6з — — (Ем Г) полный, т. е. ()УХ; ви Ез) (ЧХ( ~ Еа) Х( ни ГХН (34.1) 201 Подмножество Емв~Е называется лгаксимальной кликои, если соответствуюгций полный подграф Ом не содержится (строго) ни в каком полном подграфе. Например, на рис. !46 выделен полный подграф графа на рис. 143 с кликой Еа = (А, С, г/, 6). Рис.
144. Рис. 143. Понятие клики, в частности максимальной клики, используется в различных социологических теориях (вопросы, связанные с голосованием, альянсами и т. п.), а также в теории !игр. Нахождение максимальной клики ') в графе 6 сводится к нахождению максимального внутренне устойчивого подмножества г' / А В 'А / В / / / / р ! Рис. 146. Рис. 146. в графе б', дополнительном к графу б. Действительно, дополнительный граф определяется согласно (25.23): (УХг ев Е) Г'Хг = Š— ГХо (34.2) Для каждой клики Еа имеем (вг?Хг ев Ев) (г)УХ) ен Еа) (Хг ен ГХг) й ((Х1) () Г'Х,) = — Д, (34,3) и, таким образом, максимальному внутренне устойчиволгу подмножеству в гг' соответствует максимальная клика в б. г) См.
также А нгер н Поль (Б. Н. !) и нег, ЬЕ С. Р а и1!), Лип1- ппыпк 1Ье )Чшпьег о1 61а1ев 1п 1псогпр!е1е!у прес)1!еа Беп1епиа! 6М1смпи Рппснопв, 1, д, Е, Тгапвасиопв оп Е1ес)гогнс Согпрп1егв, ЕС8, 366 — 36?, 202 П р и и е р. Пусть граф 6 изображен на рис, 143, граф б' изображен на рис. 144, Максимальное внутреннее устойчивое подмножество графа б' изображено на рис. 145. Это подмножество соответствует клике графа О, изображенной на рис. !46, его достаточно для образования полного неориентированного графа с вершинами (6, А, С, Р)1.
УПРАЖНЕНИЯ 34А. Перечислить максимальные клики графов; а( д( д( 34Б, Построить соответствующие неориентированные графы и перечислить их максимальные клики ллн слелующих графов; 1 2 3 4 3 6 т 3 а) 1 2 3 4 5 6 7 3 ГА=(А, С, Е( ГВ (А,В,О,Е,Р1 ГС = (А, С, О, Е( ГО = (А, В, С, О, Р1 ГЕ (В,С,Е1 ГР (А,С,О,Е,Р1 г) Например, объединяя графы 6н 6„6, на рис. 147 — 149 в один, получаем 3-цветный граф, изображенный на рис. 150. Понятие р-цветного графа не имеет, конечно, ничего общего с понятием неориентированного р-хроматического графа. Граф с р отображениями. Взяв в качестве вершин элементы некоторого конечного множества и предположив, что любые две вершины Х; и Х; могут быть соединены несколькими одинаково направленными дугами, получаем граф с р отображениями, если максимум числа одинаково на- С правленных дуг, идущих от одной вершины к другой, равен р.
Например, если в 3-цветном графе на рис. 150 не обращать анима- С Е ния на цвета, то его можно рас- Е сматривать как граф с р отображениями (рис. 151), но легко привести пример р-цветного графа, которыи Ю таким же путем приводит к графу с а отображениями, где а ( р. Н Каждому д-цветному графу можно сопоставить (неоднозначно из- Рис 152. за произвольной нумерации дуг) граф с р отображениями, где д ) р, и, обратно, каждому графу с р отображениями можно сопоставить (неоднозначно нз-за произвольного выбора цвета дуг) д-цветный граф, где д ) р.
Понятие графа с р отображениями используется в теории связи, теории автоматов и т. д. Граф с одним отображением представляет собой граф в смысле теории множеств. Мультиграф, или р-граф. Другое обобщение касается неориентированных графов. В качестве вершин рассматриваются элементы некоторого конечного множества и предполагается, что различные вершины могут быть соединены несколькими ребрами.
Если максимум числа ребер, соединяющих две вершины, равен р, то говорят о неориентированном мультиграфе порядка р, или р-графе. Например, на рис. !52 изображен 4-граф. Понятие р-графа имеет много применений (в химии, социологии, теории электрических цепей и т. д.). р-цветному графу или графу с р отображениями можно (вообще говоря, неоднозначно) сопоставить некоторый р-граф, Читателю следует учесть, что определения, приведенные в этом параграфе, разными авторами даются по-разному.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
