Кузнецов О.П., Адельсон-Вельский Г.М. - Дискретная математика для инженеров (1048837), страница 25
Текст из файла (страница 25)
Докажем, что, добавив любое удаленное ребро (оо оз), мы получим некоторый цикл нечетной длины. Пусть г(оп оз) =1, г(о„о,) =1. Числа 1 и 1 имеют одинаковую четность. Рассмотрим кратчайшие цепи Е~(оо, ..., о~) и Ез(ом ..., пз), соединяющие вершину оз с вершинами о~ и оь Будем идти от вершины о, к вз по цепи Е,, пока первый раз не попадем в вершину па~Ем в крайнем случае ох=из.
Тогда цикл, состоящий из отрезков Е;(ом ..., о,), Е;(ом ..., п~) путей Е~ и Ез и ребра (о~, оз), является простым циклом нечетной длины. Действительно, все вершины — этого цикла различны (а значит, различны и ребра), так как цепи Е~ и Е, — кратчайшие, длина цепи Е~ равна 1 — й, а длина цепи Ез равна 1 — й.
Следовательно, длина цикла Я равна (1 — й)+(1 — й)+1, т. е. нечетна, и 6о — максимальная двудольная часть графа 6,. Из таких частсй, построенных для каждой компоненты, максимальные двудольные части графа 6 можно составить 2' способами, где 1 — число связных компонент графа 6. О максимальном паросочетаиии в двудольном графе. Пусть 6 — двудольный граф, ((о,', о',.'))(1=1, 2...) — паросочетание в нем, т. е.
семейство ребер (о,', о",)„в котором все вершины и;епГ и о~с=У" различны между собой. Если, кроме вершин п~, в множестве Г' имеется еще какая- либо вершина о", можно построить часть 5(п") графа 6 следующим образом. Каждая вершина множества 5(о") принадлежит одному из множеств )т((> ((=(), 1 ...), определяемых условиями т(ь>=(оь); для четного 1=212 р((+» — )/(г~+» ( ' ~ ( ',") ~ б "~-)т(г(> )' , )т(» ()1,(г> () 1),т(г(-».
для нечетного 1=21+ 1: )т((ь» = Р'д =(;~ (и', в") ЯП, о'ЕЬ""-»)-. )т(о>( ) )т(г>( ) ( )р(г! — г> где П вЂ” рассматриваемое паросочетание. Будем говорить, что вершина в~5(п") имеет индекс 1, если о~(т(о. Множество ребер части 5 (он) состоит из всех ребер (а', пь) ен ен(г, инцидентных вершинам оь четных индексов. Легко видеть, что другой конец такого ребра принадлежит части 5(п"). Построение части 5(гь) изображено на рис. 4.14. ь Г ун Ь(( (тсг> -1 ь. У(г> ) Рыс.
ь И Таким образом, каждое ребро (в(, ог) ен5(оь)ПП соединяет вершину о, нечетного индекса с вершиной ог следую. щего, а ребро (о(, ог), соединяющее вершину ог четного индекса с вершиной в( следующего, не принадлежит паросочетанию П. Это можно доказать по индукции. Пусть о'~5(пь) — вершина нечетного индекса, не являющаяся концом никакого ребра из паросочетания П. В зту вершину ведет череду>ощаяся цепь 1.(е(, ег,...,ег(+() с началом о", четные ребра которой принадлежат паросочетанию П, а нечетные — не принадлежат. Тогда паросочетание П можно расширить: выбросить из него 1 ребер ег, е„, ..., е„и добавить 1'+1 ребер е(, ег, ..., егг+(.
Если же паросочетание П максимально, то все вершины 5(о") нечетного индекса — это концы о~енУ' некоторых ребер (о,', и')енП, а множество вершин четного индекса состоит из других копцов о," этих ребер и вершины о". Так как все ребра, инцидептные вершинам о четного индекса из 3(г"), принадлежат этой части графа 6, то в этом случае число вершин иен5(о")()У', имеющих в 3(о") нечетный индекс и соседних в графе 6 вершинам о~Я(о")ПУ", на единицу меньше числа последних. Таким образом доказана теорема Холла.
Теорема 4.7, Если максимальное паросочетание П в конечном двудольном графе 6 не инцидентно всем вершинам из множества У", то существует подмножество последнего, для которого множество соседних вершин (лежащнх в множестве У') имеет на единицу меньшую мощность. П В задаче о различных представителях множеств в каждой вершине о" ен У" соответствует подмножество П(о") элементов множества У', связанных в двудольном графе 6 ребрами с вершиной о". Для любого подмножества У"~У" множество соседних вершин — это объединение всех подмножеств П(и") для оиенУ".
Если число элементов о'я ы () П(о") меньше числа различных множеств 6(о"), б"~ г" входящих в это объединение, задачу о различных представителях, очевидно, нельзя решить. Теорема Холла показывает, что в противном случае, когда для любого подмножества У"с:У" выполнено условие (У)К( () П(о") ),задао"ш 7" ча о максимальных представителях решается, 4.4. ОРИЕНТИРОВАННЫЕ ГРАФЫ Пути н циклы в ориентированном графе. Пусть У вЂ” множество вершин ориентированного графа 6, Š— множество его ребер.
Каждое ребро еенЕ имеет начало о'ыУ и конец и"~У; говорят также, что ребро е выходит из вершины о' и входит (или заходит) в вершину о". Таким образом, заданы два отображения Ф1 и ~рм где ~, (е) — начало ребра е, ~р,(е) — конец ребра е. Можно дать несколько определений пути в ориентированном графе 6.
Путь из вершин и ребер — это последовательность Е(о„еь оь ..., е„, о„), где сч 1=~р,(е~), о;=~р,(е ). Вершина оь называется началом пути Ь, вершина о„— !24 концом 1, число п ребер — его длиной. Путь, состоящий из одной вершины, имеет нулевую ллину. Каждому пути 1 ненулевой длины взаимно однозначно соответствует последовательность Х(еь ..., е,) ребер пути 1..
Она называется путем из ребер. Это понятие пути — аналог понятия маршрута в неорнентнрованном графе. Наконец, лля графов, не содержащих кратных ребер (т.е. ребер с одинаковым началом н одинаковым концом), каждому пути 1 из вершин н ребер однозначно соответствует последовательность 1.(пм оь ...,о„) вершин пути 1. Она называется путем из вершин. Ввиду взаимной однозначности объектов, порождаемых этими тремя определениями пути, всякий раз можно пользоваться тем из них, которое окажется удобнее. Путь 7(ом оь оо ..., а„, о,) паз>явается ориентированным циклом (или просто циклом, котла ясно, что рассматриваются только ориентированные циклы), если оп состоит более чем нз одного элемента н его начало совпадает с его концом.
Начало цикла обычно не фиксируется; иначе говоря, все пути вида оп е,+ь о,+ь...,п,=о„еь...,еь оь получающиеся лруг нз друга циклическим сдвигом,— это один и тот >ке цикл. Как и для неориентированного графа, цикл называется прас>ым, если каждая принадлежащая ему вершина инцидентна ровно двум его ребрам. Если граф содержит циклы, то он содержит и простые циклы; отрезок цикла между повторениями одной н той же вершины также является циклом, поэтому любой цикл можно «укоротить» до простого. Граф, не содержащий циклов, называется ациклическим. Пусть 1.'(о,'„о,',...,о,',) и 1 "(о",, о'1',...,п",) — пути, причем конец 1' совпадает с началом Л": о,' =о". Тогда после» 0' довательность 1.(о',..., о„',, о,',..., о",)' — также путь, называемый композицией путей 1' и 1 . Он обозначается 1.= =1~.1з нли Л=ь,Ц. Длина композиции равна сумме длин ее компонент.
Начальные и конечные вершины графа. Ранги вершин. Вершина графа называется начальной, если в нее не вхо. лнт ни одно ребро, н конечной — если из пее не выходит ни одно ребро. Во всяком конечном ацпклпческом графе О есть хотя бы одна начальная и хотя бы олна конечная вершина. Действительно, все пути 6 конечны и имеют длину, не превосходящую числа его вершин, так как в путях ациклнческого графа вершины не могут повторяться. Поэтому 125 существует максимальный путь (быть может, не единственный), который нельзя удлинить ни в начале, нн в конце.
Его начало будет начальной вершиной 6, а конец — конечной вершиной Максимальным рангом Я(о) вершины и ориентированного графа 6 называется максимальная из длин путей этого графа с концом в о. )г(о) =О, если и только если о — начальная вершина 6. Если через о проходит цикл, то о может быть концом сколь угодно длинного'пути (повторяющегося цикла); в этом случае Я(о) =+со. Как видно из предыдущего, в ациклическом графе все ранги конечны. Покажем, что в ациклическом графе для любой неначальной вершины о 1((о) = (пах )((о')+1. (и',и) е о Пусть о — неначальная вершина, Е(ои, о),...,ол ), о)— путь максимальной длины с концом в ней.
Тогда Š— это композиция пути Е)(оь,...,ои () и ребра (ои ), о). Так как длина Т.' не превышает максимального ранга ои ), то Я (о) ( шах Р (о')+1. (и',и) с а Пусть теперь (о', о) — ребро и Е'(пь,..., о') — путь максимальной длины с концом о'. Композиция Е' и ребра (о', о) — это путь Т.
с концом о, Его длина не превосходит Я(о) и на единицу больше длины Е', которая равна 1((о'). Поэтому)((о) )Р(о') +1 и, следовательно (так как (о', о)— произвольное ребро с концом в о), т((о) ~ шах 1((п') +1. (и',и)(=о Из этих двух неравенств следует требуемое равенство. Минимальным рангом г(о) вершины о ориентированного графа 6 называется минимум длин путей А(оь...,,о) с началом в какой-либо начальной вершине о, графа 6 н с концом в рассматриваемой вершние о, Если ни одного такого пути не существует, т(о) =+со. В конечном ориентированном ациклическом графе 6 минимальные ранги всех неначальных вершин удовлетворяют условии) г(о) = пнп г(о') +1. Доказательство аналогично предыду(и .и)(вп щему.
Отношение достижимости. Базисный граф. Вершина о" ориентированного графа 6 называется достижимой из вершины о'ен6, если существует путь А=(о', „о") с началом о' и концом о". Легко видеть, что отношение достижимости рефлексивно и транзитивно. С его помощьюопределяется разбиение множества вершин 6 на классы эквивалентности; вершины о', пиен6 принадлежат одному классу, ес- 126 ли о" достижима из о', а и' — из о". Пусть Т,,(о', ..., о") и Т.а(о", ..., о') — соответствующие пути, связывающие эти вершины. Тогда композиция этих путей А, ° Т.а — это цикл, проходящий через вершины о' и о".
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
