В.А. Емеличев, О.И. Мельников, В.И. Сарванов, Р.И. Тышкевич - Лекции по теории графов (1083735), страница 24

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 24)

Следовательно, граф 6 не содержит паросочетания мощности ~ Х~— -6,+1. а Следе тв и е 30.7. Для любого двудольного графа 6 = (Х, У, Е) верно равенство ~Х~ — бо(Х, У, Е)-!У( — бю(У, Х, Е) (4) В частности, при !Х! = ) У! бо(Х, У, Е) бо(У, Х, Е). Г> Для доказательства достаточно заметить, что каждая часть равенства (4) совпадает с а~(6). З 4 31.

Двудольные графы и семейства подмножеств Обсудим связь между двудольнымп графами и их паросочетапнями, с одной стороны, и семействами подмножеств и ях трансверсалями — с другой. Пусть 6 =(Х, У, Е) — двудольный граф без изолированных вершил. Будем считать, что Х = (1, 2, ..., т), и определим семейство Я» =(Ян Ян ..., Я ) непустых подмножеств множества У условием Я,=1У(») (1 11, ш). С другой стороны, пусть Я =(Яи Ян ..., о' ) — семейство пепустых подмножеств произвольного конечного множества У.

Определим двудольный граф 6» =(Х, У, Е), 128 положив Х = (1, 2, ..., т), )У(е)= Я; (1= 1, т). Очевидно, что Яаз = Я и соответствие С Бо является биекцией между классом всех двудольных графов (Х, У, Е) с фиксированными долями Х = (1, 2, ..., т) я У и классом всех т-членных семейств непустых подмножеств множества У. Если М вЂ” паросочетание двудольного графа С = =(Х, У, Е), то обозначим через Ум множество вершин из доли У, покрываемых ребрами этого паросочетания, а через Т(6) — множество, элементами которого служат все Ум, где М вЂ” произвольное паросочетаняе графа С, и пустое множество. Как подтверждает очевидная проверка, верно следующее Утверждение 31.1.

Если С =(Х, У, Е) — двудольный граф без изолированных вершин и И чь 7 ': — ' У, то 2 ~н Т(6) тогда и только тогда, когда множество 2 является частичной трансверсалью семейства подмножеств Яе. Поскольку все частичные трансверсали произвольного семейства непустых подмножеств и Ы составляют набор независимых множеств матроида трансверсалей, то верно С л е д с т в и е 31.2. Для любого двудольного графа 6 =(Х, У, Е) без изолированных вершин пара (У, Т(6)) — матроид, совпадающий с матроидом транс- версалей семейства Я . Пря этом число паросочетания и1 (6) равно рангу р (У, Т(С) ) . Итак, условие существования в графе С паросочетания фиксированной мощности е совпадает с условием существования соответствующей трансверсали.

Поскольку в рассматриваемой ситуации (),:г = () дг (() = дт (А) вал гол для любого подмножества А ': — Х, то теорема Холла превращается в теорему 30.1, а следствие 22.3 — в следствие 30.4. Как показывают примеры, максимальное паросочетание в графе может оказаться не наибольшим, и это свидетельствует о том, что совокупность всех ларосочетаний произвольного графа, вообще говоря, нельзя принять в качестве набора независимых множеств матроида. Тем не менее задача нахождения в двудольном графе наиболыпего паросочетания связана с матроидами. Ее можно сформулировать как задачу о пересечении двух матрондов разбиения, нли, что то же, как задачу о выборе 9 в л.

кмеличее и юь 129 трансверсали максимальной мощности, общей для двух разбиений некоторого множества. В самом деле, разобьем множество ребер двудольного графа 6 =(Х, У, Е) на классы, отнеся в один класс все ребра, покрывающие одну и ту же вершину из Х. Пусть М» — матроид этого разбиения. Аналогично определим матроид М». Очевидно, что подмножество ребер графа С является паросочетанием тогда и только тогда, когда оно независимо как относительно матроида М», так и относительно М .

Следовательно, наибольшее паросочетание в графе С вЂ” это наибольшее по мощности мяохсество ребер, независимое как относительно матроида М», так и относительно матроида М . Именно на последнем обстоятельстве основан успех процедуры построения наибольшего паросочетания в двудольном графе, приведенной в $ 77. э 32. Паросочетания и покрытия Как отмечалось в з 25, определение числа рь(6) и, тем более, построение наименьшего вершинного покрытия для произвольного графа 6 — сложные алгоритмические задачи. Эффективных алгоритмов для их решения, видимо, не существует.

Очевидно, что для каждого графа 6 число вершин в любом покрытии не мепыпе числа ребер в произвольном паросочетании, в частности, рг (6) ~ а~ (С), Последние два числа могут как совпадать, так и не совпадать. Например, ро(Кз)= 2 Ф аг(Кз) 1. Для двудольпого же гра~фа эти числа всегда равны, т. е. верна следующая Т е о р е м а 32.1, Для любого двудольного графа С число вершин в наименьшем вершинном покрытии равно числу ребер в наибольшем паросочетании: ро(6) = сс~ (6). с Пусть С =(Х, У, Е) — двудольный граф. Вначале предположим, что в 6 нет изолированных вершин. Очевидно, что для любого подмножества А ж Х множество С = У(А) 0 (Х~А) является покрытием графа С. С другой стороны, пусть Р— произвольное минимальное покрытие.

Представим 130 множество В в виде )7 =Х, 9 У„Х, =Х, и положим А = ХчХь Тогда )ч'(А) — Уь Но как замечено выше, множество Х1 О Л(А) само является покрытием. Поскольку покрытие П минимально, то .0 Х1 0 Ж(А). Итак, всякое минимальное покрытие графа С имеет вкд (1), и потому ()о (6) = ш1п ! С ~ = пни (~ Х ~,А ) + ~ 1У (А) )) = с лсх = пч|п (! Х ) — ( А 1 + ) гу (А) !) = = ~Х! — шах(!А! — /Л'(А))) = /Х! — 6„(Х, У, Е)=а,(6). лах Для графов без изолированных вершин теорема доказана. Очевидно, что при добавлении к графу 6 изолированной вершины не меняется ни ро(6), ни а1(6), так что теорема верна и для графов с изолированными вершинами.

< Поскольку для любого графа 6 верны равенства ао(6)+ ~о(6) !61 (теорема 25.5) и со1(6)+ ~~(6)=!6) (теорема 29.1), то из теоремы 32,1 вытекает С л е д с т в и е 32.2 (Д. Кениг, 1916) . Для любого двудольного графа С верны равенства чхо(6)+ ог~ (6) = ~6), ио(6) = 91(6). Как показано в 3 77, для построения наибольшего паросочетания и наименьшего вершинного покрытия в двудольном графе существуют эффективные алгоритмы.

Следовательно, и сложнейшая в общей ситуации задача нахождения наибольшего независимого множества вклассе двудольных графов решается эффективно. Как следствие из теоремы 32.1 получим один важньп1 факт из теории бинарных матриц, доказанный Д. Кенигом в 1931 году. Под линией матрицы будем понимать ее строку или столбец. Два элемента матрицы назовем независилоыми, если онн не лежат па одной линии. Т е о р е м а К е н и г а.

Л1ансимальное число попарно незавиеилоых единиц бинарной матрицы равно минимальному числу ее линий, содержаи1их все единицы матрицы. > С одной стороны, произвольная бинарная матрица А может истолковываться как приведенная матрица смежности некоторого двудольного графа 6 =(Х, У, Ь). Тогда независимость двух единиц матрицы означает, что яч 131 соответствующая пм пара ребер графа С несмежна. Поэтому максимальное число независимых единиц матрицы А равно числу паросочетапия ал(С).

С другой стороны, калкдой строке матрицы А соответствует вершина пз Х, каждому столбцу — вершина из у, а единицам ливии — ребра, инцидентные соответствуюгцим вершинам. При этом множеству линий матрицы А, содержащих все ее единицы, соответствует множество вершин графа С, являющееся покрытием. Следовательно, минимальное число элементов в покрытиях графа С равно минимальному количеству линий матрицы А, содержащих все ее единицы.

По согласно теореме 32.1 число вершин в напмепыпем покрытии графа С также равно а~(С). 0 УПРАЖНЕНИЯ 1. Найдите наибольшее независимое множество вершин в графе Петерсена. 2. Докажито, что если С вЂ” дерево, то а,(6) ~ и/2. 3, Докажито, что если пе(6) = ал(С'), то граф С является ЛХ-графом. 4 Г)риведите пример графа, в котором паименыпее доминирующее ллполшство не является независимым. 5. Пусть 6 — графл без изолированных вершин. Докалките, что С сод~ ржит такое дсмипиругощее множество Р, что УСллР— тоже доминирующее.

б. Пусть е(6) — мощность паимопьшего доминирующего множества в графе С Покажите, что осли в С нет изолированных верпшп, то е(6) -" лл/2. В случао, когда и — произвольное четное число, приведите глример связного графа порядка и, для которого з(С) = и/2. 7. Приведито пример свяапого и-вершинного графа С, у которого число 91(6) максимально среди всех графов порядка и.

8. Верно ли, что ллобое паросочетание графа содержится в наибольшем паросочетапииз 9. Покажите, что дерево Т имеет совершенное паросочетание тогда и только тогда, когда рл(и) = 1 для всех вершин из Т, где рл(и) — число компонент нечетного порядка графа Т вЂ” и, 10. Пусть М и М вЂ” иепересокающиеся паросочетапия графа С, причелл (М) ) (лт).

Покажито, что в графе С существулот непересекающиося паросочотапия М' н М', удовлетворялощие условиюг )М'! = )ЛХ) — 1, )Д') = )Ж(+1, АГОМ'= МОМ. 11. Докангнте, что бинарную матрицу, в каждой строке и в каждом столбце которой ровно й единиц, можно представить в виде суммы й бинарных матриц, в каждой строке и в каждом столбце которых ровно одна единица. Глава т' Связность Связный граф был определен как граф, у которого любые дзе вершины соединены цепью. Так, оба графа К„и С„связны, однако интуитивно ясно, что при п ) 3 граф К„ «сильнее» связен, чем С„. В этой главе вводятся и исследуются понятия, характеризующие степень связности графа.

$33. Вершинная связность и реберная связность Прел«де чем ввести понятия вершинной и реберной связности, рассмотрим одну математическую модель, возникающую, в частности, при проектировании н анализе сетей ЭВМ. Имеется сеть, состоящая из центров хранения и переработки информации. Некоторые пары центров соединены каналами. Обмен информацией между любыми двумя центрами осуществляется либо непосредственно по соединяющему их каналу, если он есть, либо через другие каналы и центры.

Характеристики

Список файлов лекций