Введение в прикладную комбинаторику, Кофман А. (984071), страница 26
Текст из файла (страница 26)
Граф, не илгеюи(ий контуров не четной длины, допускает ядро. Доказательство приведено в !8), стр. 56. необходимо и достаточно для того, чтобы А было ядром графа 6=(Е, Г), Ас:.Е. При этом полагаем Р(А, 1Э) =О. (31.15) А ВСРЕг б) в) 1 й 3 4 5 Б 7 1 31Б.
Пользуясь теоремой 1, доказать, что подмножество (А, В, С]— максимальное внутренне устойчивое для графа 6 = (Е, Г): ГА=(Р), ГВ=О, ГС=(Е), ГР=(А,Е), ГЕ = (А, С, Е, Е), ГЕ = (А, В, Р]. 31В. Пользуясь теоремой П, показать, что подмножество (А, В, С, Е)— ядро графа 0 = (Е, Г): ГА =(Р), ГВ = (Р), ГС =(4), ГР = (А, В, Е), ГЕ = (Р, Е), ГЕ = (Е).
31Г. Обладают ли графы из упражнения 29В ядрами и есла обладают, то единственными ли? 31Д. Найти ядра симметрических графов; а) УПРАЖНЕНИЯ 31А. Методом Магу найти ядра графов: А А В СР Вг В А В С Р р 31Е. Найти ядра графов из упражнения 28А. 190 С Р В Е $32. Основные понятия для неориентированных графоп Ребро. Ребром графа 6= (Е, 1)) называется такая пара элементов Х; и Х; (Х, Ф Х;), что (Хп Х1) ~ 0 или (Х1, Х;) еп П.
(32.1) Другими словами, ребро — это пара вершин, которые связаны одной дугой (в том или другом направлении) или двумя дугами (в обоих направлениях). Ребро обозначается й=(ХО Х;) (32.2) или й=!Хс Х1) (32.3) Множество ребер графа обозначается через (). Множество вершин Е вместе с множеством ребер О определяют неориентнрованный граф, который обозначается через 6 =(Е, 1)).
(32.4) Каждому графу 6 = (Е, П) можно й однозначно сопоставить неориентирован- Рис. 129. ный граф 6 =(Е, О). Обратное, очевидно, неверно. Неориентированному графу 6 соответствуют 3"2' различных графов 6, где г — число ребер, з — число вершин. Например, граф на рис. 129 имеет 14 дуг и 8 ребер. Цепь. Цепью называется такая последовательность ребер (йь йь ...), что каждое ребро йх соприкасается одним из концов с ребром йх ~ (если оно существует), а другим — с йь+, (если оно существует).
Цепь можно обозначить последовательностью вершин, которые она содержит. Можно рассматривать как конечные, так и бесконечные цепи. Например, для графа на рис. 129 (А, В, С, О, В) и (Е, В, 6) — цепи. (32.5) Длина цепи. Длиной цепи называется число ребер, которые она содержит. Простая цепь. Элементарнач цепь. Эти понятия определяются точно так же, как соответствующие понятия для путей, только вместо дуг рассматриваются ребра. Цикл.
Циклом называется конечная цепь, которая начинается и заканчивается в одной и той же вершине. Например, для графа на рис. 129 цепи (А, В, О, С, В, Р, А), [В,С,Р,В) ~(...е,р,О,е) ь Понятие цикла графа не следует смешивать с понятием цикла, определенным в $16 и относящимся к подстановкам. 191 6,= (А, В, С, О), 6,= (Е, Р, 6). (32.6) Пусть бь 6м ...— компоненты связности, порожденные подмножествами вершин Сь С,, ... Тогда (32.7) а также Ц Ск, Е. Х1ев (32.8) Степень вершины.
Степенью вершины Х~ называется число ребер, для которых одним из концов служит Хг (другой конец отличен от Х;); она обозначается через д(Х;). Например, для графа на рис, 129 д(В)=3, й(Р) 2, д(Е)=2. (32.9) Регулярный подграф степени и'. Подграф называется регулярным степени г(, если степень каждой его вершины равна г(. 192 Иногда на множестве циклов графа рассматривают отношение эквивалентности, считая эквивалентными циклы, проходящие одни и те же вершины в одинаковом порядке.
Например, для графа на рис. 129 (В, С, О, В) (С, О, В, С) = (О, В, С, О), Простой цикл. Элементарный цикл. Эти понятия определяются точно так же, как соответствующие понятия для контуров, только вместо дуг рассматриваются ребра. Связный граф. Граф 6 =(Е,Г) называется связным, если для всех Х; и Х; ен Е (Х, + Х,) всегда существует цепь из Х; в Хь Сильно связный граф всегда связен. Например, граф на рис. 120 связный, не не сильно связный, граф на рис. 129 — не связный.
Компоненты связности графа. Для вершины Х; обозначим через Сх, совокупность вершин графа, которые можно соединить цепью с Хь Компонентой связности 6х, называется подграф графа 6, порожденный Схн Например, граф 6 = (Е, 11) на рис. 129 имеет две компоненты связности: Например, граф на рис. 130 имеет регулярный подграф 64 = = (А, Л) степени 3, где А = (А, В, О, В). Гамильтонова цепь. Гамильтонов цикл. Эти понятия определяются точно так же, как соответствующие понятия для путей и контуров, только вместо дуг рассматриваются ребра.
Рис. 132. Рис. 131. Р . 139. Замечания относительно неориентированных графов. 1) Как отмечалось, каждому графу 6 = (Е, 1)) можно сопоставить не- ориентированный граф, если дуги заменить ребрами. Например, ориентированному графу на рис. !31, а также графу на рнс. 133 сопоставляется один и тот же неориентированный граф на рис.
132. Не следует смешивать обозначения 6 =(Е, О) и 6 =(Е, О). Рис. 133 Рис. 134. 2) В некоторых случаях можно неориентированный граф не отличать от симметрического графа без петель, которому он соответствует (например, граф 6~ на рис. 134 и граф 6 на рис. !32). Но такое отождествление не всегда удобно и не всегда возможно. Понятие неориентированности не обязательно совпадает с понятием двусторонней ориентированности. Например (как мы увидим в $ 60), в транспортной сети симметрия некоторых дуг может сочетаться с несимметрией их пропускных способностей. 193 УПРЛЖНБНИЯ 32А. Сопоставить неориентированные графы следующим ориентированным графам: С в) 32Б. Принимая за начальную вершину А в графах из упражнения 32А, перечислить и пересчитать цепи каждой из длин 1, 2, 3, 4, 5. Для каждой цепи указать, является она простой, элементарной яли циклом. 32В.
Указать число компонент связности графов А В С Р и Е 6 Е А А В С' В Е Р А В С В Е Е В А В С В Е а) 32Г. Для каждой вершины каждого иэ графов б) и э) из упражнения 32А, б) и э) иэ упражнения 32В найти ее полустепени и степень. 194 32Д. Какие из указанных ниже графов регулярны? Для регулярных графов указать их степени. а) гу) е) ае) з) й ЗЗ. Хроматическое число. Хроматический класс Хроматическое число. Это понятие относится к неориентированным графам. Граф называют г-хромотическим, если его вершины можно раскрасить г различными цветами так, что никакие две смежные вершины не окрашены одинаково.
Наименьшее число г, для которого граф является г-хроматическим, называется хроматическим 3 числом неориентированного графа и обозначается через у(6). Например, на карте (рис. 135) / !,, ) изображены 10 департаментов. Ее / '1 " .' ', г' можно раскрасить четырьмя цвета- ', ь ми: голубым В, желтым У, зеленым '.,„. ' " г У и красным )с так, что никакие два соседних департамента не будут окрашены одинаково. Легко гроверить, что с меньшим числом цветов этого сделать невозможно. Вершины, окрашенные одинаково, образуют внутренне устойчивое множество"), и хроматическое число можно определить как минимальное число внутренне устойчивых множеств, которые покрывают в совокупности все вершины графа.
-г Рис. 135 ") Соответствуюпгего ориентированного графа без петель, см. стр. 180. (Пни и. перев.) 195 (33.3) Рис. 136 где А; — множество таких индексов а, что х; ФФ,. Следовательно, для такого способа раскраски графа необходимо и достаточно, чтобы Ч =И "Е уа=) ° ! очаг (33.4) Обозначим через Яг максимальное внутренне устойчивое множество, соответствующее Ф„.
Тогда одночлен в разложении (33.4) указывает следующий способ окраски графа р цветами: Ь, окрашиваем цветом 1, Ь, — Ь, — цветом 2, Ь,— 8,— 3,— цветом 3, ... Если представить (33.4) в виде 'р = 'рг+ Ч'в+ + Ч'л+. (33.6) то хроматическое число графа равно 9 (6) = пп'п ! ч'л !. (33.7) ') См. также Том еск у (Л. Тогпевсп), 5пг Чпе!Чаев ргоыегпев Чш 1п1егт)еппеп1 Йапв 1а Феоне пга)непга11Чпе ае 1а с!авжцса1юп, 51п611 М Сегсе1аг1 Ма1егпансе, № 9, 1967, Впспгев). 196 Отыскание хроматического числа графа. Вновь воспользуемся методом Магу' ).
Напомним формулу (30.1!): Фв=П ~х + П (и; +х1)~=! (33.!) г[ (Ф, которая (см. $ 30) позволяет получить все внутренне устойчивые подмножества. Принимая во внимание соотношение а+ а(г = а, можно записать (33.1) в виде Фв=Фг-)-Ф,+ ... +Ф, (33.2) где Ԅ— одночлен от переменных с отрицанием. Возьмем вершину Хг и член Ф„, не содержащий хь т. е.
член, определяющий максимальное внутренне устойчивое множество, содержащее Хо Введем булевы переменные у„, каждая у из которых принимает значение 1 в точи ности на одном подмножестве (соответствующем некоторому Ф„) таком, что его вершины предполагается окрасить одинаково, и 0 в остальных случаях. ТогГ да для окраски Х, необходимо, чтобы И (гг'г) Х Ре — 1, н амдг или Фз = Ф, + Фз + ...
+ Фв. (33,9) Так как аФФо Ф,; Ь ~Фу, Ф„Фв; с у=Фи Ф,, Ф„Ф„Ф„ то имеем 1з Уа = У! + У71 ~з Уа = Уз+Уз+Ув у в, увв А1 „, + „, + У, + У, + У,, ...; у ~ Аз Ч' = (У| '+ Уз)(Уь ! Уь'+ Уз)(У1+'Уз+ Уз'+ У4 ! Уз) (У1+ Уь) Х Х (Уз '+ Уз +' Уь + Уь) (Уь + Ув) (У~ '+ Уз '+ Уь) (Уз '+ Уь '+ Уз) = ! (33.11) и У1УзУв ! У~У4Уь '+ У1УьУв +' УзУвУз ! У1УзУ4Уь + '+ У1УзУтУв ! У1УвУ7Ув ! УзУ4УьУз ! УзУ4У7Ув = 1 (ЗЗ 12) Обозначим зр1= У1УзУв ! 4 УзУвУо 'Рь = У~УзУ4Уь Ч'з = У1У4Уь '1ь = У~УзУзУв ! в = УзУьУьУз Ч'з = У|УьУв 'Рз = У|УьУзУв 1з = УзУьУ7Ув.
(33.13) Тогда у (6) = ппп) Ч" х ) = 3. (33.14) Таким образом, граф можно раскрасить тремя цветами: красным г, зеленым о и желтым ! в соответствии с %, Ч'з, Чтз, Ч"е Из (33.8) получаем $~ (А С 6 6) $з=(С Е Н) Зз=(С Е 6) 8„(С,В,)з), $ь (В,Е,Н), Зь (В,Е,6), $,=(А, С, Н), 8,= (В, Е). (33.!5) Исходя нз Ч'1=У1УзУз 8,=(А, С, 0,6] окрашивается в красный (г), 8з — 8, = (Е, Н) окрашивается в зеленый (о), (33.!6) 8,— 8,— 8, = (В, Е) окрашивается в желтый (/). Иа рис. 137 изображены все возможные способы раскраски графа тремя цветами. Приведем теперь несколько теорем о хроматическом числе графа. 197 П р и м е р. Рассмотрим неориентированный граф 6 (рис. 136), соответствующий графу на рис.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
