В.А. Емеличев, О.И. Мельников, В.И. Сарванов, Р.И. Тышкевич - Лекции по теории графов (1083735), страница 21
Текст из файла (страница 21)
Покрытие графа 6 называется минима.льны, если оно не содержит покрытия с меньшим числом вершин, н наименыиим, если число вершин в нем наименьшее среди всех покрытий графа С. Число вершин в наименьшем покрытии графа 6 называется числом покрытия (или числом вершинного покрытия) графа С и обозначается через ро(6). Например, на рис. 25.2 каждое из множеств Х~ =(4, 5, 6, 8), Хг =(4, 5, 6, 7), Хз = (1, 2, 3, 5, 6, 8) является покрытием, причем Х~ и Хг — наименьшие покрытия, а Хо — минимальное покрытие.
Следующая теорема указывает на тесную связь между покрытиями и независимыми мпояоествами графа. Теорема 25.5. Мкоокество У вершин графа С является (наименьшим, минимальным) покрытием тогда и только тогда, когда Ю = )тС' У вЂ” (наибольшее, максимальное) независимое мноокеетво. Следовательно, ао(6)+ (оо(6) =!С!. с По определенизо множество 17 независимо тогда н только тогда, когда в графе пет ребра, оба конца которого содержатся в Г, т. е.
когда хотя бы один из концов каждого ребра принадлежит ст. Последнее означает, что У— вершинное покрытие. Поскольку ! И + !Е = 16(, то, очевидно, наибольшим 17 соответствуют наименыпие У и наоборот, о С помощью этой теоремы все приведенные выше оценки числа ооо(6) очевидным образом преобразуются в оценки для ро(6). э 26. Клика Антиподом понятия независимого множества является понятие клики. Подмножество Г вершин графа С называется кликой, если любые две входящие в него вершины смежны, т.
е. еслк порожденный подграф С(Р ) является полным. Клика называется максимальной, если она не содерокится в клике с ббльпгим числом вершин, и наиболыией, если чпсло вершин в ней наибольшее среди всех клик, '1исло вершин в наибольшей клике графа С называется его плотностью (или кликовым числом) и обозначается через ор(6). Как и в случае независимых 111 множеств, максимальная клика графа может оказаться не наибольшей, и это обстоятельство делает задачи нахождения числа ф(6) и наибольшей клики для произвольного графа 6 крайне трудными.
Очевидно следующее Утверждение 26.1. Подмножество вершин графа С является кликой тогда и только тогда, когда оно независимо в дополнительном графе С. Следовательно, ф(6)=— = со»(6). О помощью этого утверждения и приведенных в $ 25 оценок числа ао(6) просто получаются соответствугощие оценки числа ф(6).
Очевидно, что все клики графа, как и все максимальные клики, составляют покрытие множества вершин. Наименьшее число клин графа С, 1 покрывающих множество тС, называется числом кликового покрытия и обозначается через г 5 с(С). Очевидно, что с(6) ) ао(6) для любого графа С. О взаимном расположении клик в графе можно судить по свойствам вводимого ниже графа клик. Граф пересечений максимальных клик графа С назовем графом клик и обозначим через 0(6).
Таким образом, вершины графа Ст(6) бпентивно соответству»от максимальным кликам графа 6 п две вершины смел«ны тогда и только тогда, когда соответствующие клики пересекаются. Если для некоторого графа Н существует такой граф С, что Нее(1(6), то Н татке называется графом клик. Очевидно, что граф (т(6) может быть как «большим», так н «малым». Например, С(0„) =О., 0(К.) =К» С(К, „)=К„, ()(Р,)=Р„ь ()(С„)=С„. Для графа С, изображенного на рис. 26.1, (1(6) = Кс Известно, что существуют графы, не являющиеся графамп клик.
Таков, например, граф, представленный на рис. 26.1. Тем не менее следующая теорема свидетельствует о том, что распопов«ение клик в произвольном графа достаточно произвольно. Теорема 26.2. Для любого (и, т)-графа Н суи1сствует такой граф С порядка и+ т, что Н изоморфен некоторому порожденному подграфу графа клик Д(6). Если О2 при этолс Н не содержит треугольррипов, то граф 6 можно выбрать так, что Н=--С(6).
~' Пусть УН= — (1, 2, ..., п), ЕН=(еь еь ..., е„). Описанным кирке способом построим граф 6 с мноятеством воршвн (иь ор~ ° ° ~ о ~ Еп Е2, ° ° ~ Кв). Если Е(р) = (еа, еа,, ..., еьь ~ — множество всех ребер графа Н, пнцпдентпых вершине 1, то положим (тр = (Реп Еа ~ Еа ~ ° ° ° ~ Еа .Р( 6; = К((т,) — полный граф с множеством вершин (те 6=6~ 0 Сгб...66„.
Рассмотрим граф клик С(6). Очевидно, что каждое из множеств (тр слултнт максимальной кликой графа 6. Кроме этого, гозможны еще максимальные клики, нс содержатцпе вершин вида о,. Пусть Х вЂ” одна из них, Е„, Ер рн Х, Е„ш рт,Ть Ер ~ (т,Гь (1) Заметим, что Е„Ер рн ЕС тогда и только тогда, когда реб- ра е п ер графа Н смежны.
Поэтому из (1) следует, что существует вершина (р, инцидентная каждому из ребер е п ер, и потому Е„рн (т„Ер рн Рь Таким образом, ~Х~ ) 2 и любые две вершины, прпнадлежатцие клике Х, вместе входят в каное-:шбо пз множеств Гь Поскаль- е ет ку клика Х пе совпадает нн с одним из Еь то в ней есть три вершины Ь, Е„Е, такие, что Е Ерш Ер, Е, Ер~ ~е с ('ь Ер, Е,~ 'ртр н индексы р, 1, Й по- Рнс. 26.2 парно различны. Тогда ребра е, ер, е„составляют в графе Н треугольник (рис.
26.2). По- скольку в графе Н нет четвертого ребра, смежного с каж- дым из ребер е„, ер, е„то 1Х! = 3, Х = Х„р„—— (Е„, Ер, Е,). Очевидно и обратное: осли ребра е„, е„е, составляют треугольник в графе Н, то множество Х„р, является мак- симальной кликой графа С. Таким образом, если в Н нет треугольников, то (тД(6) = ()ть Рм ..., 'рт ). Если в графе Н есть треуголь- ники, то вершинами графа С(6) служат все мноркества (тр и все клики графа С вида Х ри 8 в л.
впрзрчер и др. ИЗ В любой ситуации обозначим через В подграф графа (~(6), порожденный множеством вергппн 'г' =($'н Уг, ... г"„). Очевидно, что отображение )гН- г", при котором г Го является изоморфизмом графов П п!. Итак, если в Н нет треугольников, то П==-6(6). В противном случае граф Н нзоморфен поронсдепному подграфу Г графа 6(6). <3 Иа рнс. 26.3 изобрансен граф 6, описанный в доказательстве прсдыдугцей теоремы; в качестве П взят граф, Рнс. 26.3 Рнс. 26.4 представленный на рпс. 26.1, а на рис. 26.4 показан граф клик 6(6).
Следствие 26.3. Всякий граф, яе содерлсащий треугольников, является графом клик. 444 Иногда полезно понятие матрицы клик. Пусть С— произвольный граф, сг = (сгь Ьсг, ..., ф,) — мноясество всех его максимальных клик, сгС=Ь~, ог, ..., о„). Следующим образом определим бинарную р Х и-матрицу С = =С(6), строки которой соответствусот кликам из множества С, а столбцы — вершинам графа С: !'1, если оз ~ Сс, !О в противном случае. 111000 010110 011010 001011 С(6) = й 27. Проблемы клики, изоморфной вложимости и нзоморфного подграфа Пусть С и С' — два графа.
Требуется установить, существует ли в графе С подграф, пзоморфный графу С. Эта проблема изоморфиого подграфа является одной из труднейших алгоритмических проблем теории графов. Другой вариант этой проблемы — проблема изоморфиой впозсгимсогти: требуется установить, существует ли в графо С порол денный подграф, изоморфный графу С. Проблема изоморфпого подграфа превратится в проблему изоморфизлса графов, если дополнительно полонсить !С! = !С'! и !Р76! = %6'!.
Аналогично проблема пзоморфной вложимостп превратится в проблему изоморфизма, если положить !С! =- !С !. Проблему клики часто рассматривают в таком виде: заданы граф С и натуральное число с; установить, верно лп неравенство ср(6) > с? Очевидно, что проблема клики является частным случаем как проблемы изоморфного подграфа, так и проблемы изоморфной вложимости: требуется установить, является лп полный граф К, подграфом графа С.
На самом деле эти трп проблемы эквивалентны, т. е. и проблема нзоморфной вложимости, и проблема изоморфного подграфа могут рассматриваться, в свою очередь, как частные случаи проблемы клики. Этот факт первым доказал 8в П5 Матрица С(6) называется матрицей клик графа С. Очевидно, что матрица клик определяется с точностью до перестановок строк и столбцов. Например, для графа С, изображенного на рис. 26.1, В. Г. Визинг, использовав свою конструкцию модульного произведения графов.
Удобнее рассматривать не само произведение Визинга, а дополнительный к нему граф. Именно зта конструкция ниже названа модульным произведением. Модульным произведением С,"гС' графов 6 и С' называется граф, определяемый следующими условиями: 1) )т(6 .> С') = ИС Х )тС' — декартово произведение множеств )тС и )тС'; 2) вершины (и, и') и (о, о') графа СОС' смежны тогда и только тогда, когда одновременно иФо, и' Ф о' и (и„Ю ~се гв Гас. 27Л либо ио~ЕС, и'о'~ЕС', либо иоФЕС, и'о'ФЕС' (рнс. 27.1). Теорема 27.1 (В. Г.
Визннг, 1975 г.). Храф С игоморфно вкладывается в граф С' тогда и только тогда, когда су(С<> 6') ~) ~ С ~. г' Полоявим ~6~ = п. Пусть в графе С существует лоро;кденный подграф ХХ, изоморфный графу С, ф: )т6- )тН вЂ” изоморфизм графов, )тС= (1, 2, ..., и), ~Р(1)= о, (1=1, к). Из определения модульного произведения непосредственно вытекает, что вершины (1, о~), (2, ог), ... (и, о„) попарно смежны в графе СС>С' и, следовательно, <у(СС> С')) и. Обратно, пусть ~р (6<> 6') ) )к, С вЂ” клина в графе 6 г С', содержащая ровно п вершин.
Тогда С = ((1, о~), (2, ог), ..., (и, о„)), причем вершины о~ (1= 1, и) попарно различны. Положим Н= С (оь ог, ..., о„). Очевидно, что соответствие 1 о; является изоморфизмом графов 6 и Н. 0 Заметим, что вершины (1, о,) с равными одноименными координатами не смежны, позтому <р(6 О 6')~(п. 118 Следовательно, неравенство из формулировки предыдущей теоремы на самом деле является равенством. Перейдем к проблеме изоморфного подграфа. Здесь требуется слегка изменить конструкцию модульного произведения.
Большим модульным произведением СОС' графов С и С назовем граф, определяемый следующими услоВиямн: 1) )т (С С С') = УС Х )тС', 2) вершины (и, и') и (и, и') графа СОС' смежны тогда и только тогда, когда и Ф и, и' Ф и' и либо но ~ ЕС, и'и'~нЕС', либо иоФЕС. Теорема 27.2. В графе С есть подграф, изоморфный графу С, тогда и только тогда, когда гр(СО С') = =)С!. Доказательство аналогично доказательству предыдущей теоремы.
5 28. Интерпретации независимых множеств Независимые множества вершин графа связаны с самыми разными вопросами, на первый взгляд кажущимися далекими от теории графов. Рассмотрим некоторые пз этих связей. Поскольку клики графа суть независимые множества вершин его дополнения, то все сказанное ниже о независимых множествах в равной мере относится к кликам. 1. Связь с многогранниками. Пусть Л вЂ” бинарная т Х п-матрица без нулевых столбцов. Рассмотрим многогранник Р(Л)=(х: Ах~1, х~О) — мпонзество всех и-мерных векторов х с неотрицательными вещественными координатами, удовлетворяющих системе линейных неравенств Ах <1. (1) Здесь 1 (О) — столбец соответствующей высоты, каждая компонента которого равна 1 (0). Нас будут интересовать целые точки многогранника Р(Л), т, е. такие решения системы (1), координаты которых — целые неотрицательные числа.
Поскольку все столбцы матрицы А ненулевые, то очевидно, что все решения системы (1) удовлетворяют и системе неравенств х < 1. Следовательно, 117 целыми точками многогранника Р(А) служат все (О, 1)- решения системы (1) и только онн. Определим граф 6 = Сл — граф перееечепий столбцов матриуы А — положив УС =(1, 2, ..., и) и объявив вершины 1 и 1 смежными тогда и только тогда, когда неизвестные х, и х; вмес-.е входят в какое-либо нз неравенств (1), т.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
