В.А. Емеличев, О.И. Мельников, В.И. Сарванов, Р.И. Тышкевич - Лекции по теории графов (1083735), страница 22
Текст из файла (страница 22)
е. хотя бы в одной из строк матрицы А позиции 1 и ( занимают 1. Для произвольного подмножества ь' — 'г'С следующим образом введем характеристический вектор хе =(хь хг, ... ..., х„): если 1~ П, хе = (О, если 1 ф С. Очевидно, что С хп — биективное соответствие между подмножествами множества е'С и и-морпымн бинарными векторамн.
Набор всех независимых подмножеств вершин графа С обозначим через тС. Удобно считать, что И ~,УС, т. е. что пустое множество вершин независимо. Теперь очевидно, что подмножество 6': — ' 'е'С является элементом мнояеества х С тогда и тольно тогда, когда вектор хе является решением системы (1).
Следовательно, целые точни многогранника Р(А) мояшо трактовать как характеристические векторы независимых подмножеств вершин графа 6 . С другой стороны, легко видеть, что для произвольного графа С существует такая матрица А, что СлжС. В самом деле, в качестве А можно взять матрицу клик С(6). Заметим, что матрица А определяется графом С неоднозначно. Так, при непустом 6 в качестве А можно еще взять транспонированную матрицу инцидентности 1(6)т.
В общей ситуации одному графу соответствует несколько матриц А, их многогранники Р(А) могут быть различны, но множества целых точек этих многогранников совпадают. 2. Связь с булевыми функциями. Другая интерпретация независимых множеств связана с булевыми функциями. Пусть В= (О, 1), В" — множество всех бинарных венторов длины и. Произвольное отображение из В" в В называется булевой фупкуией и переменных.
Положив х ( у для х =(хь хп ..., х„), у = =(уп ум °, у„), если х~ ( у; для всех 1 = 1, и, определим на множестве В" частичный порядок <. Булеза функция 118 называется э>онотоннои если истинна импликация (х ( у) =- (((х) - 1(у) ) . Пусть > — булева функция >г переменных, х ~ В". Если >(х)=1, то х называется единиией функции >. Если, к тому же, истинна имплнкация (у(х)~-(1(у)=0), то х называется ни»>сией единицей функции >'. Аналогично определясотся пуль и верхний нуль: если 1(х) =О, то х называется нулем функции /; если при этом истинна импликацня (у)х)= (1(у)=1), то х называется верхнии нулелс.
Очевидно, что монотонная булеза функция определяется множеством всех своих нижних единиц (верхних нулей), причем роль множества нижних единиц монотонной булевой функции может играть любая система попарно пе сравнимых элементов иэ В". «1исло координат бинарного вектора, равных единице, называется его нормой. Монотонная булеза функция называется графической, если норма каждой ее нижней единицы равна 2, либо если эта функция топсдественно равна нулю.
Пусть 1' — графическая булеза функция п переменных. Следующим образом определим граф 6>. Его множество вершин 1>6> = (1, 2, ..., и); вершины» и 1 смежны тогда и только тогда, когда бинарный вектор нормы 2, >-я и 1-я координаты которого равны единице, является едипяцей функции 1. Очевидно, что если хв — характеристический вектор подмножества с> — 'г'б„то 1(хв)= 0 тогда и только тогда, когда У~У6>. Следовательно, нули графической булевой функции >' можно трактовать как характеристические векторы независимых подмножеств вершин графа 6ь С другой стороны, легко видеть, что для каждого графа 6 существует графическая булеза функция >, удовлетворя>ощая условию 6»м6.
В самом деле, 1 0 для О„; если же 6 Ф О„, то пипсними единицами подходящей графической булевой функции > служат все характеристические векторы ребер этого графа. 3. Связь с пересечением матроидов. Пусть 6 — граф. В определенных ситуациях удобно, чтобы множество У6 оказалось набором независимых множеств матроида. Тогда с помощью «жадного» алгоритма легко найти наибольшее независимое множество вершин графа 6.
К сожалению, такие графы редки. Граф, каждая компонента которого является полным графом, назовем >>г-графол«. И9 Утверждение 28.(. Пара ((тС, . С) является матроидом с кадаром ььвзависимых лшожсств . С тогда и только тогда, когда граф С есть М-граф. С Пусть М=($"С, С) — матроид с набором независимых множеств С. Очевидно, что циклами матроида ЛХ служат двухолементные подмножества смея|ных вер- 1 шин. Пусть теперь аЬ, Ьс~и ~ЕС. Тогда (а, Ь) и (Ь, с)— циклы матроида М. Согласно аксиоме С.2, множество (а, с) Д б также является циклом и, следовательно, ас ж ЕС. Доказано, что каждая связная компонента графа С вЂ” пол- 7 ный граф.
Рис. 28.1 Обратное очевидно: если С является ЛХ-графом, то . С вЂ” набор независимых множеств матропда разбиения множества ГС на области связности графа С. З Поскольку граф с одним ребром является М-графом, то очевидно, что любой граф С можно представить в виде объединения С = С~ 0 Сг Б ... Б С„ (2) М-графов С~ с совпадающими мнонсествами вершин. Назовем такое представление графа 6 его матроидяым разлозкением. Минимальное чпсло (ь компонент в матроидных разложениях графа С обозначим через (ь(6) и назовем его матроидным числом. Рассмотрим, например, граф С, изображенный на рис.
28.(. Этот граф можно представить в виде объединения С = С~ ц Сз двух М-графов 61 и Сг, каждый из которых является дизыонктным объединением двух полных графов: С, = 6((, 2, 8, й) И 6(5, 6, 7), Се= С((, 2, 5, 6) 0 6(3, 4, 7). Очевидно, что С не является ЛХ-графом, поэтому (ь(6) = 2. Если (2) — матроидное разложение графа С, то , С = П .
С„, а=1 где . ф— набор независимых множеств матроида М~ = =(ГС, . С„), являющегося матроидом разбиения множе- 120 ства )тС на области связности графа С . Другими словами, нспустые элементы множества УС вЂ” это все частичные трансверсали разбиения множества )тС на области связности графа 6„. Верно и обратное, Пусть дано р разбиений )тк () )тк, () ... () Гк, =УС, й=1,)г, (3) множества )тС. Кслн 6„— объединение ь, полных графов с мпожествамп вершин 1тк, Ик, . ° )тк;~, а С вЂ” объединение всех графов С„то независимыми подмножествами вершин графа С слул.ат частичные трансверсали, общие для всех разбиенпй (3), и только они. Итак, набор всех независимых подмножеств вершин произвольного графа С при р(6)~ р можно трактовать как набор всех частичных трансверсалей, общих для разбиений вида (3) .
В частности, нахождение в графе наибольшего независимого множества вершин есть в точности задача о пересечении нескольких матроидов разбиений. Задача определения числа д(С) для произвольного графа 6, по-видимому, очень сложна. Тем более сложно построение соответствующего матроидного разложения. Определенный интерес имеет характернзация графов, для ж ив-е Рвс. 28.2 которых р(С)= 2. Задача определения числа независимости ас(6) для графов этого класса может формулироваться как задача о наибольшей мощности трансверсали разбиения, независимой относительно матроида некоторого разбиения. Приведем без доказательства характеризацню графов с матролдпым числом, равным 2, в терминах запрещенных поролсденных подграфов.
Теорема 23.2. Для связного графа С, не являющегося полным, следующие два утверждения равносильны: 1) д(С) = 2; 121 2) граф С не содержит простых циклов нечетной длины ( ~ 5, звезды К, з, колеса Ит4 и графа И'4 — е (рис. 28,2) как порозкденных подграфов. Некоторые оценки числа р(6) см. в 2 57. з 29. Паросочетания Рис, 29Л Пе менее важным, чем понятие вершинной независимости, является понятие реберной независимости. Произвольное подмножество попарно несмел",ных ребер графа называется паросочетанием (нлп независимым множеством ребер).
В качестве иллюстрации рассмотрим граф, изображенный на рис. 29.(. В нем паросочетаниямн являются, например, (ег), (е1), (ез, ез), (еь ез, еы ет). Паросочстапне графа С на- е е, е, ез е, е, зываотся максимальпььн, если е, г оно не содержится в паросочетании с ббльшим числом ребер, и наибольшим, если число ребер в нем наибольшее среди всех паросочетаний графа 6.
Число ребор в наибольшем паросочетанпи графа С называется числом паросочетапия и обозначается через а~(6). Ясно, что независимые множества ребер графа С находятся во взаимно однозначном соответствии с незаниснмтвми множествами вершин робсрного графа Е(С), и, слодовательно, а1(6) =аз(Ь(6) ). Тем не менее для нахождения наибольшего паросочетания в произвольном графе существуют аффективные алгоритмы. С понятием паросочетания тесно связано понятие реберного покрытия.
Реберкым покрьмием графа С называется такое подмножество ребер Е' — ЕС, которое покрывает все вершины графа, т. е. такое, что каждая вершина в С нпцндентна по крайней мере одному ребру из Е'. Из этого определения следует, что лишь графы с изолированными вершинами не имеют реберных покрытий. реберное покрытие графа называется лгинимальным, если в нем не содоржится покрытий с меньшим числом ребер, и наименьшим, если число ребер в нем наименьшее среди всех покрытий. Число ребер в наименьшем реберном покрытии графа С называется числом реберпого покрытия и обозначается через р1 (6). 122 Очевидно, что ~~(6)~!6~)2.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
