Дискретно-непрерывная математика (стр. 8 )

Теорема 4. Из теоремы Менгера следует теорема Холла.

Доказательство. Пусть G = G (V1, V2) — двудольный граф; нам надо доказать, что если | А | ≤| φ (А) | для любого подмножества А из V1, то существует совершенное паросочетание из V1 в V2. Сделаем это, применяя вершинную форму теоремы Менгера (теорема 2) к графу, полученному при­соединением к G вершины v, смежной каждой вершине из V1, и вершины w, смежной каждой вершине из V2 (рис.5).

Рис. 5.

Так как совершенное паросочетание из V1 в V2 существует тогда и только тогда, когда число вершинно непересекаю­щихся простых цепей из v в w равно числу вершин в V1 (скажем, k), то достаточно показать, что каждое vw - отделяющее множество содержит по меньшей мере k вершин.

Пусть S есть vw-отделяющее множество, состоящее из подмножества А множества V1 и подмножества В множества V2. Поскольку А В есть vw-отделяющее множество, не существует ребер, соединяющих вершину из V1 — А с вершиной из V2 — В, и, значит, φ(V1 — А) В. Следо­вательно, | V1 — А | ≤|φ(V1 — А) | ≤ | В |, и поэтому

| S | = | А | + | В | ≥ | V1 | = k, что и требовалось.

УПРАЖНЕНИЯ

(1) Убедитесь в том, что и реберная форма, и вершинная форма теоремы Менгера верны для графа Петерсена (при всяком возможном выборе вершин v и w).

(2) Дайте подробное доказательство теоремы 2 и проверьте ее для кубического графа, изображенного на рис. 6.

Рис. 6.

(3) Покажите, каким образом вершинная и реберная формы тео­ремы Меигера могут быть выведены одна из другой.

(4) Граф G называется k-связным, если k — наибольшее из чисел, таких, что каждая пара несмежных вершин соединена не ме­нее чем k вершинно непересекающимися простыми цепями. Покажите, что (i) граф Wn (n ≥4) 3-связен; (ii) Km,n k-связен, где k = min (m, n); (iii) если G k-связеи, то степень каждой его вершины не меньше k; (iv) G двусвязен тогда и только тогда, когда каждая пара его вершин содержится в не­котором цикле; (v) G(≠/K2) k-связен тогда и только тогда, когда k равно наименьшему числу вершин, удаление которых делает G несвязным.

(5) Покажите, как распространить теорему Менгера на бесконеч­ные графы.

1.7. Потоки в сетях

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

Изготовитель электрических массажных щеток хотел бы послать на данный рынок несколько ящиков своей продук­ции. Предположим, что эти ящики можно послать по нес­кольким различным каналам, показанным на рис. 1 (где v представляет изготовителя, w — рынок, а числа на диа­грамме обозначают максимальные грузы, которые могут быть посланы по соответствующим каналам).

Рис 1.

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

Рис.1 может описывать и другие ситуации. Напри­мер, если каждая дуга этого орграфа представляет улицу с односторонним движением, а сопоставленное каждой улице число обозначает максимальный возможный поток транс­порта (число машин в час) по этой улице, то хотелось бы най­ти наибольшее возможное число машин, которые могут про­ехать из v в w за один час. Эту диаграмму можно рассматри­вать и как схему электрической цепи, и тогда задача состоит в нахождении максимального тока, который можно пропус­тить по этой цепи при условии, что заданы предельные токи отдельных проводов.

Отправляясь от этих примеров, определим теперь сеть N как орграф, каждой дуге а которого приписано неотрицатель­ное действительное число ψ(а), называемое ее пропускной способностью. Другое определение сети, эквивалентное первому, звучит так: сеть представляет собой пару (D, ψ), где D — орграф, а ψ — функция, отображающая множест­во дуг орграфа D в множество неотрицательных действи­тельных чисел. Полустепень исхода (х) вершины х опреде­ляется тогда как сумма пропускных способностей дуг вида (x, z), и аналогичным образом определяется полустепень

захода (х). Например, в сети, изображенной на рис. 1, (v) = 8 и (x) = 10. Ясно, что аналог орлеммы о рукопо­жатиях принимает следующий вид: сумма полустепеней ис­хода всех вершин в сети равна сумме их полустепеней захо­да. В дальнейшем будем предполагать (если не оговорено противное), что орграф D содержит ровно один источник v и один сток w; общий случай, когда имеется несколько источ­ников и стоков (в разобранном выше первом примере это соответствует более чем одному изготовителю и более чем одному рынку), легко свести к этому частному.

Для данной сети N = (D, ψ) определим поток через N как функцию φ, сопоставляющую каждой дуге а из D неот­рицательное действительное число φ(а) (называемое потоком через а) таким образом, что (i)

φ(а)≤ψ(а) для любой дуги а; (ii) по отношению к сети (D, φ) полустепень исхода и полу­степень захода любой вершины (отличной от v и w) равны между собой. Говоря неформально, это означает, что поток через любую дугу не превосходит ее пропускной способнос­ти и что «полный поток», входящий в любую вершину (от­личную от v и w), равен «полному потоку», выходящему из нее. На рис. 2 показан возможный поток для сети, изображенной на рис. 1; другим потоком является нулевой поток, при котором поток через каждую дугу равен нулю (любой другой поток называется ненулевым).

Рис. 2.

Для удобства назовем дугу а, для которой φ(а)=ψ(а), насы­щенной (на рис.2 насыщенными являются дуги (v, z), (х, z), (у, z), (x, w) и (z, w)); остальные дуги называются нена­сыщенными.

Из орлеммы о рукопожатиях следует, что сумма потоков через дуги, инцидентные v, равна сумме потоков через дуги, инцидентные w; эта сумма называется величиной потока. Помня о примерах, рассмотренных в начале параграфа, мы будем в первую очередь интересоваться потоками, имею­щими наибольшую возможную величину,— так называе­мыми максимальными потоками. Читатель без труда может проверить, что поток, изображенный на рис. 2, является максимальным потоком через сеть, изображенную на рис. 1, и что его величина равна шести. Заметим, что в общем случае сеть может иметь несколько различных максималь­ных потоков, однако их величины должны совпадать.

Изучение максимальных потоков через сеть N = (D, ψ) тесно связано с понятием разреза, т. е. такого мно­жества А дуг орграфа D, которое обладает тем свойством, что любая простая орцепь из v в w проходит через дугу, при­надлежащую А. Другими словами, разрезом в сети является не что иное, как vw-разделяющее множество соответствую­щего орграфа D. Пропускной способностью разреза назы­вается сумма пропускных способностей принадлежащих ему дуг. Мы будем рассматривать главным образом такие разре­зы, которые обладают наименьшей возможной пропускной способностью, — так называемые минимальные разрезы. На рис. 1 примером минимального разреза является мно­жество дуг (v, z), (х, z) (у, z) и (x, w); пропускная способность этого разреза равна шести.

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

Теорема 1 (теорема о максимальном потоке и мини­мальном разрезе). Во всякой сети величина любого макси­мального потока равна пропускной способности любого мини­мального разреза.