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

1.6. Теоремa Менгерa

Здесь мы обсудим одну теорему, тесно связанную с теоремой Холла, которая имеет практические применения. Эта теорема, принадлежащая Менгеру, каса­ется числа простых цепей, соединяющих две данные вершины v и w графа G. К примеру, нас может интересовать, каково максимальное число простых цепей из v в w, никакие две из которых не имеют общего ребра, — такие простые цепи называются реберно непересекающимися. Или может воз­никнуть другой вопрос: каково максимальное число прос­тых цепей из v в w, никакие две из которых не имеют общей вершины (кроме, разумеется, v и w), — такие цепи называ­ются вершинно непересекающимися. (Так, в графе, изоб­раженном на рис. 1, имеется четыре реберно непересека­ющиеся и две вершинно непересекающиеся простые цепи из v в w.)

Рис. 1.

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

Для исследования этих задач нам понадобится еще не­сколько определений; всюду здесь будем считать, что G — связный граф, a v и w — две различные его вершины.

Назовем vw-разделяющим множеством в G множество Е ребер графа G, обладающее тем свойством, что любая простая цепь из v в w содержит ребро из Е; заметим, что всякое vw-разделяющее множество является и разделяющим множе­ством в G. Аналогично,

vw-отделяющим множеством в G на­зовем множество S его вершин (не содержащее v и w), об­ладающее тем свойством, что любая простая цепь из v в w проходит через вершину из S. Например, на рис. 1 мно­жества E1 = {{р, s}, {q, s}, {t, у}, {t, z}} и Е2 = {{и, w}, {x, w}, {y, w), {z, w}} являются vw - разделяющими, а мно­жества V1= {s, t} и

V2 = {p, q, y, z} являются vw - отделяющими.

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

vw-разделяющее множество Е содержит k ре­бер, то число реберно непересекающихся простых цепей не превосходит k, поскольку в противном случае некоторое реб­ро из Е принадлежало бы более чем одной простой цепи. Если к тому же Е является vw-разделяющим множеством на­именьшей возможной мощности, то число реберно непересе­кающихся простых цепей оказывается в точности равным k и, следовательно, каждая такая цепь содержит ровно одно ребро из Е. Этот результат известен как реберная форма теоремы Менгера, хотя в действительности он был впервые доказан Фордом и Фалкерсоном в 1955 г.

Теорема 1. Максимальное число реберно непересе­кающихся простых цепей, соединяющих две различные вер­шины v u w связного графа G, равно минимальному числу k ребер в vw-разделяющем множестве.

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

Доказательство. Как мы установили выше, максималь­ное число реберно непересекающихся простых цепей, сое­диняющих v и w, не превосходит минимального числа ребер в vw-разделяющем множестве. Чтобы доказать, что эти числа равны, воспользуемся индукцией по числу ребер в G. Предположим, что G содержит т ребер и что теорема верна для всех графов, у которых число ребер меньше чем т. Рассмотрим два возможных случая.

(i) Допустим, что существует vw-разделяющее множество Е минимальной мощности k, обладающее тем свойством, что не все его ребра инцидентны v и не все инцидентны w. Например, в графе, изображенном на рис. 1, таким vw-разделяющим множеством является множество E1 = {{р, s}, {q, s}, {t, y}, {t, z}}. После удаления из G ребер, при­надлежащих Е, остаются два непересекающихся подграфа V и W, содержащие соответственно v и w. Определим теперь два новых графа G1 и G2: G1 получается из G стягиванием каждого ребра из V (т. е. сжиманием V до v), a G2 получает­ся аналогичным стягиванием каждого ребра из W. (Графы G1 и G2, полученные из графа, изображенного на рис. 1, показаны на рис. 2; пунктирными линиями обозначены ребра множества E1)

Рис.2.

Поскольку число ребер в G1 и в G2 меньше, чем в G, и поскольку ясно, что Е является vw-разделяющим множеством минимальной мощности для обоих графов G1 и G2, то по предположению индукции в G1 сущест­вует k реберно непересекающихся простых цепей из v в w, и то же самое верно для графа G2. Комбинируя очевидным образом эти простые цепи, мы получим k искомых реберно непересекающихся простых цепей в G.

(ii) Теперь допустим, что каждое vw-разделяющее мно­жество минимальной мощности k состоит либо из таких ребер, каждое из которых инцидентно v, либо только из ребер, ин­цидентных вершине w. Таким vw-разделяющим множеством на рис. 1 является, например, множество Е2. Без потери общности можно считать, что каждое ребро графа G содер­жится в некотором vw-разделяющем множестве мощности k, так как в противном случае удаление соответствующего ребра не повлияет на величину k и позволит воспользо­ваться индуктивным предположением, чтобы получить k реберно непересекающихся простых цепей. Следовательно, любая простая цепь С из v в w должна состоять либо из единственного ребра, либо из двух ребер, и поэтому может содержать не больше одного ребра из любого vw-разделяющего множества мощности k. Удаляя из G ребра, принадле­жащие С, мы получим граф, содержащий по крайней мере

k — 1 реберно непересекающихся простых цепей (по ин­дуктивному предположению). Вместе с С эти простые цепи и дают искомые k простых цепей в G.

Обратимся теперь к другой задаче, упомянутой в начале этого параграфа: к нахождению числа вершинно непересе­кающихся простых цепей из v в w. (Сам Менгер решал именно эту задачу, хотя обычно его имя связывают с обеими тео­ремами 1 и 2.) На первый взгляд кажется удивитель­ным, что не только решение этой задачи имеет вид, подоб­ный теореме 1, но и само доказательство теоремы 1 претерпевает лишь незначительные изменения, состоящие главным образом в замене таких терминов, как «реберно непересекающийся» и «инцидентный», на термины «вершинно непересекающийся» и «смежный». Сформулируем теперь вер­шинную форму теоремы Менгера, а доказательство предо­ставим читателю.

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

Мы уже говорили выше, что проведенные рассмотрения можно модифицировать для случая орграфов и получить число вершинно непересекающихся и непересекающихся по дугам простых орцепей. В этом случае vw-разделяющим мно­жеством называется множество А дуг орграфа, обладающеетем свойством, что всякая простая орцепь из v в w содер­жит ребро из А. Соответствующая теорема опять-таки очень похожа на теорему 1, и ее доказательство почти дословно совпадает с доказательством теоремы 1. Сформулируем эту теорему и назовем ее теоремой о целочисленности (при­чина такого названия выяснится в следующем параграфе).

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

Проиллюстрируем эту теорему на примере орграфа, изо­браженного на рис. 3.

Рис.3.

Непосредственно проверяется, что у него 6 непересекающихся по дугам простых орцепей из v в w; соответствующее vw-разделяющее множество обозначено пунктирными линиями.

Как мог заметить читатель, с ростом числа дуг, соединя­ющих пары смежных вершин, диаграммы становятся доволь­но громоздкими. Это неудобство можно преодолеть следующим образом: нарисуем только одну дугу и напишем на ней, сколько таких дуг на самом деле (рис.4).

Рис. 4.

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