В.А. Емеличев, О.И. Мельников, В.И. Сарванов, Р.И. Тышкевич - Лекции по теории графов (1083735), страница 42
Текст из файла (страница 42)
Теорема 51.2. Для любой графической функции верно равенство «(/) = 111(6,). (2) ~> Пусть « — графическая функции, — пороговое разложение графа Сн Тогда система УС~ всех независимых подмножеств вершин графа С, есть пересечение ~6« = П РСа (3) а аналогичных систем длн пороговых графов С„.
Множество характеристических векторов элементов системы УС совпадает с множеством бинарных решений линейного неравенства, являющегося разделяющим для графа С . Из равенства (3) следует, что множество бинарных решений системы из «таких неравенств есть множество характеристических векторов злемептов из УСн т. е. множество пулей функции «. Следовательно, эта система неравенств задает функцию «, и потому «()) ~ «. Итак, «()) ( «5(С,).
Обратно, пусть функции 1 задается некоторой системой линейных неравенств (1). Следующим образом построим «графов 6„(й = 1, «); )тСь — — (1, 2,, и), «« ~ ЕСа тогда п только тогда, когда «т'-'«' п ссм+ам) рь Очевидно, что (3') Предполон«пм, что какой-либо из графов Се пе является пороговым. Тогда в пем есть порожденный подграф, запрещенный следствием 50.3; пусть это подграф, показанный па рве.
50.2, где пунктирные линии означают отсутствие соотвстству1ощпх ребер. Иэ определения графа Са следует, что ам+ам> ~н ам+ ам ~~м Но последняя система неравенств противоречива, следовательно, Се — пороговый граф. Итак, (3 ) — пороговое 230 (4) а(а)+ яэ(а) ( п, а если в С нет треугольников, то (5) 1)т(6)+сев(6) = п. > Пусть Я вЂ” наибольшее независимое мпоятество вершин графа С, 1тС~Я = (иь иг, ..., ив). Обозначим через Ь; множество ребер графа 6, ипцидентпых вершине и< (1=1, Ь). Поскольку ребра, входящие в Еь составляют звезду, являющуюся согласно теоромо 50.9 пороговым графом, то и граф 6, =(ГС, Е,) пороговый.
По ь () 6,=6. г=т (0) Следовательно, (6) — пороговое разложение графа 6. Поэтому 11~(6) — )с = и — ас(6), т. е. верно неравенство (4). Пусть теперь в графе С нет треугольников и пусть а=с 0а 0...06, — пороговое разлоягепие с минпмальным числом компонент. В пороговом графе 6~ таки е нет треугольников. Из теоромы 50.9 следует поэтому, что граф 6, является звездой или получается из звезды в результате присоединения изолированных вершин. В любом случае в графе С~ есть вершина иь ипцидептпая всем его ребрам. Так как () ЕС; = ЬС, то множество Ъ'С'~(иь ин ..., и,) нег=1 зависимо в графе С, Следовательно, сгэ(6) ~ и — й(6), что вместе с неравенством (4) приводит к равенству (5), а 231 разлохзение графа Со Поэтому 1(т(6,) < 1 и, следовательно, 11~(6,)~ г(1).
Равенство (2) доказано. Э Вычисление порогового числа произвольного графа 6 и, тем более, построение соответствующего порогового разложения графа — крайне трудные задачи. Пороговое число можно оценить с помощью числа нозависимости ав(С), однако последнее так же трудно вычислимо. Теорема 51.3 (В. Хватал, П. Хаммер, 1077 г,). Для любого пепустого графа 6 порядка п верно неравенство Заметим, что равенство (5) может быть верным и для графа с треугольниками. Таков, например, граф па рис.
51.1. Поскольку для лсобого и-вершинного графа 6 верно равенство ссь(6)+ рч(С)= сг (теорема 25.5), где (!г(6)— число покрытия графа 6, то пз предыдущей теоремы вытекает Следствие 51.4. Для любого графа 6, не соде!сгкащгго треувольссиков, верно равенство бй (6) = ра(6) . В частности, любой двудольный граф не рссс Э! ! сонержит треуголышков.
Кроме того, для двудольпого графа 6 верно равенство рч(6)=ис(С), где ас(С) — число паросочетапия (теорема 32.1). Поэтому из теоремы 51.3 вытекает Следствие 51.5. Для лсобого двудольпого графа С верссо равгссство !)с(6) = ас (С) . Таким образом, в классе двудольных графов параметр 1!с(С) вычислнетсн носложпо. в 52. Степенное множество графа Степенным лшожеством графа называется множество степеней его вершин. От степенной поссседовательссости это мносссество отличается тем, что в нем пе учитывается число вершин, имеющих заданную степень, тогда как в степенной последовательности каждое число фигурирует столько раз, степенью скольких верпсип опо является. Степенное множество графа С обозначин через Ь'(6). Так, для графа С, изображенного па рпс.
52.1, Ь'(6) == =(1, 2, 3). Хотя степенная последовательность Рссс. 523 графа удовлетворяет определенным ус- ловиям, однако степенным множеством графа может быть произвольное множество. Об этом свидетельствует следующая Теорема 52.1. Любое коне шов лснолгество Я натуральных чисел является степенным мпогквстволс некоторого порогового графа. Мипимальссьсй порядок таких графов равен г+1, гдв г — максимальное число из многкества Я. Очевидно, что пз этой теоремы вытекает Следствие 52.2, Любое конечное мпоясество целых пеотрицателы1ых чисел является степенным мнохсеством некоторого графа. 1Р Д о к а з а т е л ь с т в о т е о р е м ы 52.1. Если Я (6) = = Я, то ~6~ > 2+ 1, так что нужно только доказать существование подходящего графа 6.
Утверждение тривиально для одноэлементпого множества Я, поскольку Б(К„) =(и — 1). Пусть теперь Я=Ы1, Й, ..., Ы.), д1>б2»...д., п>1, — 1-,'— у +х рх +...+х =ар, х„+х„+...+х = — и (2) х +...+х =В вы х =в„. Очевидно, что система уравнений (2) относительно неизвестных хь у, (1=1, р, ) =1, р) имеет решение, все координаты которого положительны: У1 = А — с(2, у2 = с(2 оз, Х1 = д„, х2 = 11р-1 — 12р, (3) у,=б,— и„,+1. Хр = Орр1 — Ырр2, Подставив в выражение (1) числа, определяемые равенст- вами (3), получим граф С, для которого Я(6)=Б. Число его вершин равно х1+хг+...+х,+у1+уг+... + у, = 01+ 1.
и пусть, для определенности, и = 2р — четное число. Нужный граф будем искать в виде где К„.Н вЂ” граф, полученный нз графа Н добавлением х доминпрующик вершин, а Ор ° Н вЂ” граф, полученный из графа Н добавлением у изолированных вершин. Любой граф вида (1) является пороговым. Попытаемся подобрать числа х„и у„в вырая1екии (1) так, чтобы выполнялось равенство Я(6) =Я. Для этого должно быть — 2+у 1-у 1-...+у +ха+х +...+х =-В, Для нечетного и = 2р+ 1 построение аналогично, только вместо формулы (1) используется формула УПРАЖНЕНИЯ 1.
Докажпто, что прн л 4 асе графы порядка и лзляются униграфамн, а прп л 4 среди графов порядка л есть нак упиграфы, тан и пе упиграфы. 2. Найдите последовательность переключений, переводящую один из графов, представленных на рис. ЧП1.1, в другой. Рис. ЧП1.1 3. Докажите что последовательность (44, Зт, 2') является графичоской и постройте какуго-либо ее реализацию. 4. Постройте связную реализацию последовательности (6, 4, 3, 2", 1).
Есть ли у втой последовательности реализации, пе являгощиося связными? 5. Постройте реализацию П последовательности (6, 3', 2') с Л(6) = 2. 6. Дона(лите, что при и ( 3 асе графы порядка и расщепляемы, а при и ) 3 среди графов норядка л ость и расщепляемые, и не расщепляемые. 7. Является ли последовательность (5, 3', 2') расщспляемой7 8. Найдите все роализации последовательности (6, 5, 4', 2, 1). Рис. ЧП1.2 9.
Дока>инте, что граф, изображенный на рис. ЧН1.2, язляетсл пороговым, Найдите для него разделяющее неравенство. 10. Постройте какой-либо граф, степенное множество которого совпадает с 8 = (1, 3, 5). 1!. Докажите, что любое нонечпое множество натуральных чисел, содержащее 1, язлягтся степенным множсстаом некоторого дереза. Постройте дероео Т, степенное мпол(естао которого 8(Т) = (1, 2, 3). 12 Дока1ките, что если два пороговых графа С и Я пе нмоют пзолированных вершин и Ь'(С) =- 8(Н), то зти графы изоморфпы.
Глава 1Х Раскраски Задачи раскраски вершин илп ребер графа занимают важное место в теории графов. К построению раскрасок сводится целый ряд практических задач. Характерной особенностью этих задач является существование объектов, которые по каким-либо причинам пе могут быть объединены в одну группу. й 53. Правильная раскраска Пусть 6 — некоторьш граф, Й вЂ” натуральное число, Произвольная функция вида /:(т6 — ((, 2, ..., Й) называется вершшгиой Й-раскраской, или просто Й-раскраской, графа 6. Если позволяет контекст, то Й в этом определении опускается. Раскраска называется правильной, если /(и) чь/(и) для любых смеясных вершин и и ш Граф, для которого существует правильная Й-раскраска, называется Й-раскрашиваемым (или раскрашиваемым Й цветами).
В определении раскраски вместо множества ((, 2, ..., Й) можно взять произвольное Й-элементное множество. Правильную Й-раскраску графа можно трактовать как окрашивание каждой его вершины в одпп из Й цветов, при этом смежные вершины должны получать различные цвета.
Поскольку функция / пе обязательно сюрьектпвпа, то при Й-раскраске фактически может быть использовано менее Й цветов. Таким образом, правильную Й-раскраску графа 6 можно рассматривать как разбиение (т Н(т О...Н(т,=(т6, гапон(ества вершин (т6 на пе более чем Й пепустых классов, каждый нз которых являетсн независимым множеством. Классы этого разбиении называются цветными классамш Минимальное число Й, при котором граф 6 является Й-раскрашиваемым, называется ароматическим числом этого графа и обозначается )((6).
Если )((6)= Й, то граф 235 С назынаетсн 1е-хроматическим. Правильная й-раскраска графа С при й = у (С) называется минимальной. В качестве иллюстрации рассмотрим граф С, изобраигенный па рпс. ЗЗЛ, где укааана одна из правильных 4-раскрасок. Меньшим числом цветов этот граф раскрасить правильно нельзя. Действительно, граф содоржнт цикл (оь он оз, иь оь, щ), длн правильной раскраски которого ну1к- 1 г 1 г но пе меное трех цветов, а для вершины ов требуется новый цвет. Итак, у (С) = 4. Рассмотрим некоторые практические задачи, сводящиеся к правильной раскраске графов.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
