В.А. Емеличев, О.И. Мельников, В.И. Сарванов, Р.И. Тышкевич - Лекции по теории графов (1083735), страница 49
Текст из файла (страница 49)
Из этого определения непосредственно вытекает, что всякий порок денный подграф любого совершенного графа является совершенным. Очевидно, что все полные и пустые графы совершенны. Примером совершенного графа может служить также каждый двудольный граф, поскольку для любого его подграфа Н либо т(Н)=>р(Н) = 2 (если ХХ непустой), либо у (Н) = сг (ХХ) = 1 (при пустом Н) . Совершенные графы введоны К. Бержем в 1960 году.
Интерес к этим графам связан прежде всего с двумя обстоятельствами. Во-первых, многие трудно разрешимые в общем случае задачи теории графов успепшо решаются для совершенных графов. Во-вторых, ряд широко известных классов графов содержится в классе совершенных. Таковы, например, все двудольпые, пороговые, расщонляемые и триангулированные (см.
з 62) графы. Исследования, посвященные совершенным графам и, в частности, связанной с ними гипотезе Бержа, речь о которой пойдет нии<е, во многом определяют лицо современной теории графов. Теорема 61.1. Граф, дополнительный и совершенному графу, также является соввршвнныле Эту теорему в виде гипотезы сформулировал К.
Бер>к в 1961 г. Позже ее независимо доказали Д. Р. Фалкерсон ()971 г.) и Л. Ловас (1972 г.). Ниже прнводнтся доказательство Л. Ловаса. Л е и и а 61.2. Следующие два утверждения равное>гльньи 1) граф С является совершение лц 2) в л>обем непустом пороисдвнном подграфв С' графа С есть таков независимое множество вершин А, что Ч(С' — А)( >р(С'). '(2) ~> Пусть С вЂ” совершенный граф, С' — его непустой порожденный подграф.
Тогда у(С') = ~р(С ). Следовательно, существует правильная >р(С )-раскраска графа С'. Если А — какой-либо цветной класс при этой раскраске, 268 то множество Л независимо и у(С' — А)~ф(6')' — 1. Из последнего неравенства вытекает (2), поскольку ~р(Н)< ~х(Н) для любого графа Н. Пусть теперь для некоторого графа 6 верно утверждение 2).
Нужно доказать, что для любого порожденного подграфа 6 графа 6 выполняется неравенство Х(6') < р(6') Из неравенства (3) следует равенство плотности и хроматического числа, ибо противоположное неравенство всегда верно. Воспользуемся индукцией по ) 6'~. Если 6 — пустой граф, то (3) тривиально.
Пусть 6 непуст, )6 ~ = )г ) 1 и для каждого порожденного подграфа меньптето чем !с порядка верно неравенство, аналогичное неравенству (3). Для независимого множества А вершин графа 6', удовлетворяютцего неравенству (2), имеем по индуктивному предположению: у (6' — А ) = ~р (6' — Л ) ( ф (6') .
Но так как множество Л независимо, то т (6') ~ т(6' — Л) + 1 ( <р (6')+ 1, т (6') ~ (р(6'), и равенство (3) доказано. з Пусть 6 и Н вЂ” произвольные графы. Будем считать их множества вершин не пересекающимися и следующим образом определим новый граф Р. Отметим произвольную верпшпу о графа 6 и положим ЪР =(РС Б )тН)гш Вершины а и Ь графа Р будем считать смежными, если выполняется одно из следующих трех условий: 1) аЬшЕС, 2) аЬяЕН, 3) аш)тС, Ьш7Н, аосеЕС пли Ьж)тС, аяПХ, Ьо ве ЕС.
Скажем, что граф 1г получается пз графа С в результате замены вершины о графом Н. Л е м м а 61.3, !'раф, полученный из совершенного графа в результате замены вершин совершенными графами, также является совершенным. г Очевидно, что достаточно рассмотреть лишь одну замену вершины. Пусть 6 и Н вЂ” совершенные графы, а Г получается пз 6 в результате замены вертпины и графом Н.
Учитывая лемму 61.2, достаточно показать, что в любом порожденном подграфо !" графа Р есть независимое множество вершин А, пересекающеося с каждой 269 наиболыпей кликой графа Р'. Вначале пусть г"'=Р. Зафиксируем какую-либо правильную ф(6)-раскраску графа 6. Пусть  — цветной класс, содержащий вершину о. Выберем в графе Н такое независимое множество вершин С, что <р(Н вЂ” С)(ф(С). Теперь покажем, что множество (В У С) <о = А удовлетворяет нужным условиям.
В самом деле, В независимо в С, С независимо в Н. Если же Ь ш ~В>о, с ш С, то вершины Ь и о не смежны в С, а потому Ь и с не смежны в Р. Итак, А — независимое множество вершин графа р. Остается показать, что А пересекается с каждой наибольшей кликой графа г". Пусть К вЂ” одна иэ таких клик, Р = К П «Н. Если ВФ 8, то Р содержит какую-либо наибольшую клику Р графа Н, поскольку любая вершина графа С вЂ” о либо смежна в Г с каждой вершиной графа Н, либо ни с одной из них. Так как Р ПСчь 8, то КП П А Ф и. Если же Р = и, то К вЂ” <<С'>о, ф(г') =!К! < (<р(С вЂ” и)~<р(6).
Но очевидно, что <р(6)~ф(Р). Следовательно, )К! =ф(6), клика К пересекается с каждым цветным классом любой правильной ф (6) -раскраски графа С, К П(В<и)Ф Я<, значит, К ПА чь и. Доказано, что в графе р есть независимое множество вершин, которое пересекается с каждой наибольшей кликой этого графа.
Теперь заметим, что аналогичное свойство имеет любой порожденный подграф Г' графа г", поскольку Г' либо получается из некоторого порожденного подграфа С' графа 6 в результате замены вершины и порожденным подграфом Н' графа Н, либо является порожденным подграфом графа 6. < Лемма 61А. В любом совершенном ерафе С есть клика, пересекаюи<ая каждое наибольшее невависил<ое ли<ожество вершин графа С. > Проведем доказательство от противного. Пусть 6— совершенный граф, для каждой клики В которого существует такое наибольшее независимое множество вершин А, что В П А = И.
Пусть, далее, В>, ..., В, — список всех клик графа 6, Л,— наибольшее независимое множество вершин, такое что Л, П В;чь>З> (<= <, т). Для произвольной вершины о графа С обозначим через <о(о) число всех множеств А„содержащих эту вершину. Заменив в С каждую вершину о полным графом К <.и получим граф С', который по лемме 6<.3 окажется совершенным. Оценим число <р(6'). Очевидно, что всякая клика графа 6' есть объединение клик графов, заменивших в 6 вершины 2<э какой-либо клики. Поэтому <р(6') = шах ~~ ж(э). г<~~г юев; Поскольку каягдое из множеств А, вносит единицу в те и только те из чисел ю(э), для которых ож Аь то ~~!! ю(г) = ~ ! В~ () А, ! ° впв; 1=1 Но очевидно, что В, () А< = И, )В, П А,! ( 1.
Следовательно, <р (6') ( г — 1. (4) Далее, т(6') ~ )6'!/ае(6') (5) (теорема 54.7). Построим последовательность, выписав поочередно все элементы множества Ап все элементы множества Ам ..., все элементы множества А„. Пусть 1— длина этой последовательности. Очевидно, что 'г 1 = ~ !'А ! = га, (6).
С другой стороны, каждая вершина и графа С фигурирует в этой последовательности ровно ю(и) раз, поэтому 1= Х (.)=!С !. юБ уп Наконец, очевидно, сго(6 ) = иа(6) Неравенство (5) теперь принимает вид у(6') ъ Г. (6) Но ~р(6') =Х(6'), что противоречит совокупности неравенств (4) и (6). Полученное противоречие и доказывает лемму. <1 ~> Доказательство теоремы 61.1. Пусть С— совершенный граф, Н вЂ” непустой пороясдеяный подграф дополнительного графа 6. Тогда  — порожденный подграф графа С. Согласно лемме 61А в графе Й есп клика В, пересекающаяся с каждым наибольшим независимым подмножеством вершин.
П графе Н мноясество В независимо и пересекается с каждой наибольшей кликой. Следовательно, в силу леммы 61.2 граф С является совершенным. 0 271 Напомним читателю, что с(6) означает число кликового покрытия графа 6. Очевидно, что ис(6) = <р(6), с(6)=т(С), поэтому из теоремы 61.1 вытекает Следствие 61.5.
Граф является совершенным тогда и только тогда, когда иэ(Н) = с(П) для любого его порождеггного подгрофа Н. Приведем без доказательства теорему, характеризующую совершенные графы в терминах многогранников. С каждой бинарной матрицей А без нулевых столбцов можно связать два многогранника: многограннпк Р(А) = = (х: Ах < 1, х ~ 0), введенный в з 28, и многогранник Р,(А) — выпуклую оболочку множества целых точек многогранника Р(А). Очевидно, что Р,(А) — Р(А).
Теорема 61.6. (В. Хватал, 1075 г.). Пусть А— матрица клик графа 6. Тогда для того, чтобы граф 6 был совершеннььи, необходимо и достаточно выполнение равенства Р,(А) =Р(А). Легко видеть, что условием, необходимым для того, чтобы граф был совершенным, явлнется отсутствие в нем порожденных простых циклов нечетной длины 1~ 5. В самом деле, если С вЂ” такой цикл, то ~р(С) = 2 ( (у(С) = 3.
Из теоремы 61.1 вытекает, что таких циклов не должен содержать н граф, дополнительный к совершенному. В 1962 году К. Берж высказал предположение, что эти два условия не только необходимы, но и достаточны для того, чтобы граф был совершенным. Сильная гипотеза Бержа. Граф 6 является совершенгеым тогда и только тогда, когда ни он, ни его дополнение С ие содерлеат порояедеипых подграфов вида Сг,,.ь (с> 2. Эта гипотеза, не доказанная и пе опровергнутая до сего времени, инициировала исследование совершенных графов и привела ко многим интересным результатам. в 62. Триангулировапные графы Граф 6 называется триаигулироваиным (нлп хордальньгм), если ни один из его порожденных подграфов не является простым циклом длины Е> 4.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
