7.4.5. Массив дуг

Представление графа с помощью массива структур Е : array [l..p] of record b,e: l..p end record, отражающего список пар смежных вершин, называется мас­сивом ребер (или, для орграфов, массивом дуг). Для массива ребер (или дуг) n(p,q) = O(2q).

Пример

Представление с помощью массива ребер (дуг) показано в следующей таблице (для графа G слева, а для орграфа D справа).

. Обходы графов

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

Алгоритм 7.1. Поиск в ширину и в глубину

Вход: граф G(V, Е), представленный списками смежности Г.

Выход: последовательность вершин обхода.

for v ∊ V do

x[v]: =0{ вначале все вершины не отмечены}

end for

select v ∊ V{ начало обхода — произвольная вершина }

v → Т{ помещаем v в структуру данных Т ... }

x[v] : = 1{... и отмечаем вершину v }

repeat u← Т{ извлекаем вершину из структуры данных Т ... }

yield u{ ... и возвращаем ее в качестве очередной пройденной вершины }

for w ∊ Г(u) do

if x[w] =0 then

w → Т{ помещаем w в структуру данных Т ... }

x[w]: = 1{ ... и отмечаем вершину w }

end if

end for

until Т = 

Если Т — это стек (LIFO — Last In First Out), то обход называется поиском в глубину. Если Т — это очередь (FIFO — First In First Out), то обход называется поиском в ширину.

Пример

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

Рис..12. Диаграмма графа к примеру обхода в ширину и в глубину

ТЕОРЕМА Если граф G связен (и конечен), то поиск в ширину и поиск в глубину обойдут все вершины по одному разу

доказательство

[Единственность обхода вершины.] Обходятся только вершины, попавшие в Т. В Т попадают только неотмеченные вершины. При попадании в Т вершина отмечается. Следовательно, любая вершина будет обойдена не более одного раза.

[Завершаемость алгоритма.] Всего в Т может попасть не более р вершин. На каждом шаге одна вершина удаляется из Т. Следовательно, алгоритм завершит работу не более чем через р шагов.

[Обход всех вершин.] От противного. Пусть алгоритм закончил работу, и вер­шина w не обойдена. Значит, w не попала в Т. Следовательно, она не была отмечена. Отсюда следует, что все вершины, смежные с w, не были обойдены и отмечены. Аналогично, любые вершины, смежные с неотмеченными, сами не отмечены (после завершения алгоритма). Но G связен, значит, существует путь (v,w). Следовательно, вершина v не отмечена. Но она была отмечена на первом шаге!

СЛЕДСТВИЕ • Пусть (u ₁ , . . . , u_i , . . . , u_j , . . . , u_р) – обход (то есть последовательность вершин) при поиске в ширину. Тогда i<j d(u ₁, u_i) d(u_i, u_j).

Другими словами, расстояние текущей вершины от начальной является моно­тонной функцией времени поиска в ширину, вершины обходятся в порядке воз­растания расстояния от начальной вершины.

СЛЕДСТВИЕ Пусть (u₁ , . . . , u_i, . . . , u_р) – обход при поиске в глубину. Тогда

i1 d(u ₁, u_i)ip.

Другими словами, время поиска в глубину любой вершины не менее расстояния от начальной вершины и не более общего числа вершин, причем в худшем случае время поиска в глубину может быть максимальным, независимо от расстояния до начальной вершины.

СЛЕДСТВИЕ Пусть (u₁ , . . . , u_i, . . . , u_р) – обход при поиске в ширину, а D(u₁, 1),D(u₁, 2), ... — ярусы графа относительно вершины u₁. Тогда

i1.

Другими словами, время поиска в ширину ограничено снизу количеством вер­шин во всех ярусах, находящихся на расстоянии меньшем, чем расстояние от начальной вершины до текущей, и ограничено сверху количеством вершин в ярусах, начиная с яруса текущей вершины и включая все меньшие ярусы.

СЛЕДСТВИЕ Пусть (u₁ , . . . , u_i, . . . , u_р) — обход при поиске в ширину, a (v₁ , . . . , v_j, . . . , v_р) — обход при поиске в глубину, где u_i=v_j. Тогда в среднем i =2j.

Другими словами, поиск в глубину в среднем вдвое быстрее, чем поиск в ширину

Орграфы и бинарные отношения

Целью этого, заключительного раздела данной главы является установление свя­зи теории графов с другими разделами дискретной математики.

Графы и отношения

Любой орграф G(V, E) с петлями, но без кратных дуг, задает бинарное отношение Е на множестве V, и обратно. А именно, пара элементов принадлежит отношению (а, b) ∊ Е  V  V тогда и только тогда, когда в графе G есть дуга (а, b).

Полный граф соответствует универсальному отношению. Граф (неориентирован­ный) соответствует симметричному отношению. Дополнение графов есть допол­нение отношений. Изменение направления всех дуг соответствует обратному от­ношению. Гиперграф соответствует многоместному отношению и т. д.

ОТСТУПЛЕНИЕ -

Таким образом, имеется полная аналогия между оргафами и бинарными отношениями — фактически, это один и тот же класс объектов, только описанный разными средствами. Отношения (в частности, функции), являются базовыми средствами для построения по­давляющего большинства математических моделей, используемых при решении практи­ческих задач. С другой стороны, графы допускают наглядное представление в виде диа­грамм. Это обстоятельство объясняет широкое использование диаграмм различного вида (которые суть представления графов или родственных объектов) при кодировании и осо­бенно при проектировании в программировании.

Достижимость и частичное упорядочение

В качестве примера связи между орграфами и бинарными отношениями рассмо­трим отношения частичного порядка с точки зрения теории графов.

Вершина u в орграфе G(V, E) достижима из вершины v, если существует путь из v в u. Путь из v в u обозначим .

Отношение достижимости можно представить матрицей Т : array [l..p,l..p] of 0..1, где T[i,j] = 1, если вершина v_j достижима из вершины v_i, и T[i,j] = 0, если вершина v_j недостижима из вершины v_i.

Рассмотрим отношение строгого частичного порядка w, которое характеризуется следующими аксиомами:

1. антирефлексивность: v ∊ V ¬(v w v);

2. транзитивность: u,v,w (v w w & w w u  v w u);

3. антисмметричность: u,v ¬(u w v&v w u).

Отношению строгого частичного порядка w V  V можно сопоставить граф G(V, Е), в котором а w b  (а, Ь) ∊ Е.

ТЕОРЕМА Если отношение Е есть строгое частичное упорядочение, то орграф G(V, E) не имеет контуров.

доказательство

От противного. Пусть в G есть контур. Рассмотрим любую дугу (a,b) в этом контуре. Тогда имеем а w b, но b w а по транзитивности, что противоречит строгости упорядочения.

ТЕОРЕМА Если орграф G(V,E) не имеет контуров, то достижимость есть строгое частичное упорядочение.

доказательство

[Антирефлексивность.] Нет циклов, следовательно, нет петель, следовательно, достижимость антире­флексивна.

[Транзитивность..] Если существуют пути из v в w и из w в u, то существует и путь из v в u. Следовательно, достижимость транзитивна.

[Антисиметричность.] Пусть достижимость — это не строгое упорядочение. Тогда u,v uwv&vwu, то есть существует путь из v в u и из u в v. Следовательно, существует контур , что противоречит условию. 

ТЕОРЕМА Если орграф не имеет контуров, то в нем есть вершина, полустепенъ захода которой равна 0.

доказательство

От противного. Пусть такой вершины нет, тогда для любой вершины найдется вершина, из которой есть дуга в данную вершину. Следовательно, имеем контур против направления стрелок. 

ЗАМЕЧАНИЕ

Эта теорема позволяет найти минимальный элемент в конечном частично упорядоченном множестве, который требуется в алгоритме топологической сортировки (алгоритм 1.7). А именно, минимальный элемент — это источник, то есть вершина, которой в матрице смежности соответствует нулевой столбец.

. Транзитивное замыкание

Если Е — бинарное отношение на V, то транзитивным замыканием Е⁺ на V будет отношение достижимости на орграфе G(V, E).

ТЕОРЕМА Пусть М — матрица смежности орграфа G(V, Е). Тогда M^k[i,j] = 1 в том и только в том случае, если существует путь длиной k из вершины v_i, в вершину v_j.

доказательство

Индукция по k. База: k = 1, М¹ = М — пути длины 1. Пусть M^k-1 содержит пути длины k - 1. Тогда

то есть путь длины k из вершины i в вершину j существует тогда и только тогда, когда существуют вершина l, такая что существует путь длины k - 1 из i в l и дуга (l,j), то есть 

Если Т — матрица достижимости, то очевидно, что .

Трудоемкость прямого вычисления по этой формуле составит О(р⁴). Матрица достижимости Т может быть вычислена по матрице смежности М алгоритмом Уоршалла (алгоритм 1.11) за О(р³).

Комментарии

Эта глава является вввдной главой второй части, поэтому здесь уместно привести беглый обзор учебной литературы по теории графов.

Классическими учебниками по теории графов являются книги [2] и [23]. Первая является библографической редкостью, а последняя монография переиздавалась в нашей стране и является образцовой по глубине и широте охвата материала и одновременно по ясности и лаконичности изложения. Терминология и обозна­чения книги [23] взяты за основу в данном учебнике. Книга [23], хотя и имеет сравнительно небольшой объем, содержит большое число прекрасных упраж­нений'и различные сведения справочного характера. В меньшей степени в ней представлены программистские аспекты теории графов.

Существуют и другие доступные учебники по теории графов: [6, 21]. Послед­няя книга вполне доступна даже неподготовленному читателю, имеет небольшой объем, но в то же время вполне достаточна для первоначального знакомства. Раз­делы, посвященные теории графов, как правило, присутствуют во всех учебниках по дискретной математике, хотя такие разделы, по естественным причинам, не отличаются полнотой охвата материала.

Особого упоминания заслуживают книги [11] и [5]. Содержание этих книг аб­солютно точно соответствует их названиям и является необходимым для про­граммиста дополнением к классическим монографиям типа [23]. Эти источники, особенно [11], в значительной мере повлияли па отбор материала для данного учебника.

Единственный в этой главе алгоритм 7.1 носит настолько общеизвестный ха­рактер, что трудно указать его источник. Идея этого алгоритма лежит в осно­ве огромного числа конкретных алгоритмов на графах. Как правило, эта идея предполагается заранее известной читателю, и изложение сразу погружается в технические детали применения общей концепции поиска в ширину и в глуби­ну для решения конкретной задачи. В то же время свойства алгоритма поиска, приведенные в виде следствий к теореме, обосновывающей алгоритм 7.1, хотя и являются вполне тривиальными, не всегда осознаются практическими програм­мистами при решении задач. Именно поэтому представляется важным предпо­слать обсуждению конкретных алгоритмов на графах изложение общей идеи в предельно простой и рафинированной форме.

Упражнения

7.1. Построить пример графов G₁ и G₂, для которых p₁ = р₂, q₁ = q₂, ₁ = ₂, ₁ = ₂, но G₁ G-2 (кроме примера подраздела 7.1.6).

7.2. Доказать, что в нетривиальном графе существуют вершины одинаковой степени.

7.3. Задача Рамсея. Доказать, что среди любых 6 человек есть либо 3 попарно знакомых, либо 3 попарно незнакомых.

7.4. Рассмотрим матрицу смежности ребер Q : array [1..q, l..q] of 0..1, где

Является ли матрица смежности ребер Q представлением в ЭВМ графа G(V,E)?

7.5. Описать в терминах теории графов отношение эквивалентности на конечном множестве.

Связность

Данная глава является центральной во второй части. Здесь обсуждается важное для приложений понятие связности, доказывается наиболее глубокая теорема -теорема Менгера и рассматриваются самые распространенные алгоритмы поиска кратчайших путей.

Компоненты связности

В русском языке есть как слово «компонент» мужского рода, так и слово «компо­нента» женского рода, оба варианта допустимы. Современная языковая практика склоняется к использованию мужского рода, и мы ей следуем в остальной части книги. Однако исторически сложилось так, что «компонента связности» имеет женский род, и в этом случае мы подчиняемся традиции.

. Объединение графов и компоненты связности

Напомним, что если граф G состоит из одной компоненты связности (то есть fe(G) = 1), то он называется связным. В связном графе любые две вершины со­единены (простой) цепью.

ТЕОРЕМА Граф связен тогда и только тогда, когда его нельзя представить в виде объединения двух графов.

доказательство

Необходимость. От противного. Пусть k(G) = 1 и граф G состоит из двух ком­понент, то есть

где Vi П V₂ = 0, ei П Е₂ = 0, Vi ^ 0, V₂ ^ 0. Возьмем v_l е Vi, v₂ & V₂. Тогда 3{t>i,v₂) vi € Vikv₂ € V₂. В этой цепи Эе = (a,b) а £ У_г &Ь € V₂. Но тогда е g ei, e g Е₂, следовательно, е g E. Достаточность. От противного. Пусть fc(G) > 1. Тогда 3 w, v -d (и, v). Следователь­но, вершины и, v принадлежат разным компонентам связности. Положим gi - компонента связности для и, a G₂ — все остальное. Имеем G = gi U G₂.

ЗАМЕЧАНИЕ

Таким образом, несвязный граф можно всегда представить как объединение связных ком­понент. Эти компоненты можно рассматривать независимо. Поэтому во многих случаях можно без ограничения общности предполагать, что рассматриваемый граф связен.

Точки сочленения

Вершина графа называется точкой сочленения, если ее удаление увеличивает чи­сло компонент связности.

ЛЕММА В любом нетривиальном графе есть (по крайней мере) две вершины, которые не являются точками сочленения

доказательство

Например, это концы диаметра.

Оценка числа ребер через число вершин и число компонент связности

Инварианты p(G), q(G) и k(G) не являются независимыми.

ТЕОРЕМА Пусть р — число вершин, q — число ребер, k — число компонент связ­ности графа. Тогда

доказательство

1. р — k ^ q. Индукция по р. База: р = 1, g = 0, k = 1. Пусть оценка верна для всех графов с числом вершин меньше р. Рассмотрим граф G, p(G] = р. Удалим в G вершину v, которая не является точкой сочленения: G' : = G — v. Тогда если v — изолированная вершина, то р' — р - 1, k' = k - 1, q' = q. Имеем р — k = р' — k' ^ q' = q. Если v — не изолированная вершина, то р' = р — 1, k' = k, q' < q. Имеем: р-k^l+p'-k'^l + q'^q.

2 - q ^ (p— k)(p— fc+l)/2. Метод выделения «критических» графов. Число ребер q графа с р вершинами и k компонентами связности не превосходит числа ребер в графе с р вершинами и k компонентами связности, в котором все компонен­ты связности суть полные графы. Следовательно, достаточно рассматривать только графы, в которых все компоненты связности полные. Среди всех гра­фов с р вершинами и k полными компонентами связности наибольшее число ребер имеет граф

fc-i

K_p._k+1 U

Действительно, пусть есть две компоненты связности gi и G₂, такие что 1 < pi = p(Gi) ^ Р2 = р(съ). Если перенести одну вершину из компонен­ты связности gi в компоненту связности G₂, то число ребер изменится на Д<? = Р2 - (pi — 1) = Р-2 ~ Pi + 1 > 0. Следовательно, число ребер возросло. Таким образом, достаточно рассмотреть случай

k-l

Но при этом

k-l

q(K_p__k+1 U U Ki) = (р - k + 1)(р - k + 1 - 1)/2 + 0 = (р - k)(p -k + l)/2. П

СЛЕДСТВИЕ Если q > (р - 1)(р - 2)/2, то граф связен.

доказательство

Рассмотрим неравенство (р-1)(р-2)/2 < g < (p-fc)(p-fc + l)/2 при различных значениях fc.

/с = 1 (р - 1)(р - 2)/2 < (р - 1)р/2 выполняется,

fc = 2 (р- 1)(р-2)/2 < (р-2)(р- 1)/2 не выполняется,

/с = 3 (р- 1)(р-2)/2 < (р-3)(р-2)/2 не выполняется

и т. д. П

Вершинная и реберная связность

При взгляде на диаграммы связных графов (сравните, например, рис. 7.9 и 8.1) возникает естественное впечатление, что связный граф может быть «более» или «менее» связен. В этом разделе рассматриваются некоторые количественные ме­ры связности.

Мосты и блоки

Мостом называется ребро, удаление которого увеличивает число компонент связ­ности. Блоком называется связный граф, не имеющий точек сочленения.

Пример

В графе, диаграмма которого представлена на рис. 8.1:

вершины и, v — точки сочленения, и других точек сочленения нет;

ребро х — мост, и других мостов нет;

правильные подграфы {а, Ь, и}, {a,u,w}, {a,b,u,w}, {c,d,v}, {e,f,v} — блоки, и других блоков нет.

А е /

Рис. 8.1. Точки сочленения, мосты и блоки

Если в графе, отличном от К₂, есть мост, то есть и точка сочленения. Концы всякого моста (кроме висячих вершин) являются точками сочленения, но не всякая точка сочленения является концом моста.

ТЕОРЕМА Пусть G(V, Е) — связный граф и v е V. Тогда следующие утверждения эквивалентны:

v — точка сочленения;

3u, wGVu^w&V (u,w)_G v 6 (u,w);

3U,W UC\W = 0&UUW = У\{г>}&Уие UVweW V(u,w)_G we (u,w)_G.

доказательство

1=>3: Рассмотрим G — v. Этот граф не связен, k(G — v) > 1, следовательно, G — v имеет (по крайней мере) две компоненты связности, то есть

V \ {v} = U U W,

где U — множество вершин одной из компонент связности, a W •- все остальные вершины.

Пусть и £ U, w € W. Тогда -d (и, u>)_G__v. Но k(G) — 1, следовательно, 3 (u,w)_G , и значит, V(u,w)_G v 6 (u,w)_G. 3=>2: Тривиально.

•2=4-1: Рассмотрим G - v. Имеем: -^3(u,w)_G__v. Следовательно, k(G - v) > 1, откуда v — точка сочленения.

ТЕОРЕМА Пусть G(V,E) — связный граф и х е Е. Тогда следующие утвержде­ния эквивалентны:

l.a;— мост;

2. х не принадлежит ни одному простому циклу

3 и, w 6 V V (и, w)_G x e (u,

доказательство

Упражнение 8.2

Меры связности

Вершинной связностью графа G (обозначается x(G)) называется наименьшее число вершин, удаление которых приводит к несвязному или тривиальному графу.

Пример

x(G) = 0, если G несвязен;

x(G) = 1, если G имеет точку сочленения;

х(К_р] = р — 1, если Кр — полный граф.

Граф G называется k-связным, если x(G) = /с.

Реберной связностью графа G (обозначается A(G)) называется наименьшее число ребер, удаление которых приводит к несвязному или тривиальному графу. Пример

A(G) — 0, если G несвязен;

полный граф. 5(G).

A(G) = 1, если G имеет мост;

= р - 1, если К_р

ТЕОРЕМА x(G) ^ A(G)

доказательство

х ^ А: Если А = 0, то х = 0. Если А = 1, то есть мост, а значит либо есть точка сочленения, либо G = К₂. В любом случае х = 1. Пусть теперь А > 2. Тогда удалив А - 1 ребро, получим граф G', имеющий мост (и, v). Для каждого из удаляемых А — 1 ребер удалим инцидентную вершину, отличную от и и v. Если после такого удаления вершин граф несвязен, то х ^ А — 1 < А. Если связен, то удалим один из концов моста — и или v. Имеем х ^ А.

А ^ 6 : Если 6 = 0, то А = 0. Пусть вершина v имеет наименьшую степень: d(v) = 6. Удалим все ребра, инцидентные v. Тогда А ^ 6.

Теорема Менгера

Интуитивно очевидно, что граф тем более связен, чем больше существует раз­личных цепей, соединяющих одну вершину с другой, и тем менее связен, чем

меньше нужно удалить промежуточных вершин, чтобы отделить одну вершину от другой. В этом разделе устанавливается теорема Менгера, которая придает этим неформальным наблюдениям точный и строгий смысл.

Непересекающиеся цепи и разделяющие множества

Пусть G(V, Е) — связный граф, и и v — две его несмежные вершины. Две цепи (и, v} называются вершинно -непересекающимися, если у них нет общих вершин, отличных от и и v. Две цепи (и, v} называются реберно-непересекающимися, если у них нет общих ребер. Если две цепи вершинно не пересекаются, то они и реберно не пересекаются. Множество вершинно-непересекающихся цепей (и, v) обозначим через P(u,v)..

Р(ц, v) : = {(и, v) \ (и, v)_l 6 Р & (и, v)₂ е Р =» (и, у)_г П (и, v)₂ = {и, v}} .

Множество S вершин (и/или ребер) графа G разделяет две вершины unv, если и и v принадлежат разным компонентам связности графа G - S. Разделяющее множество ребер называется разрезом. Разделяющее множество вершин для вер­шин и и v обозначим S(u,v).

ЗАМЕЧАНИЕ -

Если и т v принадлежат разным компонентам связности графа G, то \Р(и, v)\ = 0 и \S(u,v)\ = 0. Поэтому без ограничения общности можно считать, что G — связный граф.

Теорема Менгера в «вершинной форме»

ТЕОРЕМА (Менгера) Пусть и и v — несмежные вершины в графе G. Наимень­шее число вершин в множестве, разделяющем и и v, равно наибольшему числу вершинно-непересекающихся простых (и, v}-цепей:

max \P(u, v)\ = min \S(u, v)\.

замечание

Пусть G — связный граф, и вершины и и v несмежны. Легко видеть, что |Р| < |5|. Действи­тельно, любая (и, г>)-цепь проходит через 5. Если бы |Р| > \S\, то в S была бы вершина, принадлежащая более чем одной цепи из Р, что противоречит выбору Р. Таким образом, VP V5 |Р| ^ |5|. Следовательно, max|P| ^ min|5|. Утверждение теоремы состоит в том, что в любом графе существуют такие Р и S, что достигается равенство |Р| = |5|.

доказательство

Пусть G — связный граф, и и v — несмежные вершины. Совместная индукция по р и д. База: наименьший граф, удовлетворяющий условиям теоремы, состоит из трех вершин u,w,v и двух ребер (u,w) и (w,v). В нем P(u,v) = (u,w,v) •и S(u,v) = {w}. Таким образом, \P(u,v)\ = \S(u,v)\ = 1. Пусть утверждение теоремы верно для всех графов с числом вершин меньше р и/или числом ребер меньше q. Рассмотрим граф G с р вершинами и q ребрами. Пусть u,v&V,u,v-не смежны и S — некоторое наименьшее множество вершин, разделяющее и и v, га: = |S|. Рассмотрим три случая.

1. Пусть в 5 есть вершины, несмежные с и и несмежные с v. Тогда граф G — S со­стоит из двух нетривиальных графов gi и G%. Образуем два новых графа G_u и G_v, стягивая нетривиальные графы gi и G₂ к вершинам и и'г>, соответственно: G_u : = G/d, G_v : = G/G₂ (рис. 8.2).

S S S

Рис. 8.2. Доказательство теоремы Менгера, случай 1

S по-прежнему является наименьшим разделяющим множеством для и и v как в G_u, так и в G_v. Так как gi и G₂ нетривиальны, то G_u и С„ имеют мень­ше вершин и/или ребер, чем G. Следовательно, по индукционному предполо­жению в G_u и в G_v имеется п вершинно-непересекающихся простых цепей. Комбинируя отрезки этих цепей от 5 до г) и от и до 5, получаем п вершинно-непересекающихся простых цепей в G.

2. Пусть все вершины S смежны с и или с v (для определенности пусть с и), и среди вершин S есть вершина w, смежная одновременно с и и с v (рис. 8.3).

Рис. 8.3. Доказательство теоремы Менгера, случай 2

Рассмотрим граф G': = G-w. В нем S \ {w} - разделяющее множество для и и v, причем наименьшее. По индукционному предположению в G' имеется |5\{и>}| = п— 1 вершинно-непересекающихся простых цепей. Добавим к ним цепь (u,w,v). Она простая и вершинно не пересекается с остальными. Таким образом, имеем п вершинно-непересекающихся простых цепей в G

3. Пусть теперь все вершины 5 смежны с и или с v (для определенности пусть с ы), и среди вершин 5 нет вершин, смежных одновременно с вершиной и и с вершиной v. Рассмотрим кратчайшую (и, г>}-цепь (u,wi,w₂,... ,v}, wi e S, w₂ ф v (рис. 8.4).

Рассмотрим граф G': = G/{wi,w₂}, полученный из G склейкой вершин w\ и w₂ в вершину w\. Имеем w₂ $ S, в противном случае цепь (u,W2,...,v} была бы еще более короткой. Следовательно, в графе G' множество S по- прежнему является наименьшим, разделяющим и и v, и граф G' имеет (по крайней мере) на одно ребро меньше. По индукционному предположению в G' существуют п вершинно-непересекающихся простых цепей. Но цепи, которые не пересекаются в G', не пересекаются и в G. Таким образом, имеем п вершино- непересекающихся простых цепей в G.

Варианты теоремы Менгера

Теорема Менгера представляет собой весьма общий факт, который в разных фор­мулировках встречается в различных областях математики. Комбинируя вер­шинно- и реберно-непересекающиеся цепи, разделяя не отдельные вершины, а множества вершин, используя инварианты х и А, можно получить множество результатов «типа теоремы Менгера». Например:

ТЕОРЕМА Для любых двух несмежных вершин и и v графа G наибольшее число реберно-непересекающихся (и, v)-цепей равно наименьшему числу ребер в (u,v)-разрезе.

ТЕОРЕМА Чтобы граф G был k-связным, необходимо и достаточно, чтобы лю­бые две несмежные вершины были соединены не менее чем k вершинно-непересе­кающимися простыми цепями.

Другими словами, в любом графе G любые две несмежные вершины соединены не менее чем x(G) вершинно-непересекающимися простыми цепями.

Теорема Холла

Теорема Холла, устанавливаемая в этом разделе, имеет множество различных применений и интерпретаций, с рассмотрения которых мы и начинаем ее изло­жение.

. Задача о свадьбах

Пусть имеется конечное множество юношей, каждый из которых знаком с неко­торым подмножеством множества девушек. В каком случае всех юношей можно женить так, чтобы каждый женился на знакомой девушке?