Дискретная математика: графы и автоматы. Альпин Ю.А - 58 стр.

UptoLike

ВУЗ: 

КФУ | Казань

Составители: 

Рубрика: 

58 Глава 3. Задача о максимальном потоке в сети
E
X
= {k → l : k ∈ X, l ∈
¯
X} является (i, j)-разделяющим, при-
чём его пропускная способность равна |E
X
|. Отсюда и из следствия 1
вытекает утверждение, известное как теорема Менгера:
Следствие 2. Максимальное число непересекающихся по дугам
простых (i, j)-путей равно минимальному числу элементов (i, j)-
разделяющего множества дуг.
3. Граничный ранг (0, 1)-матрицы и теорема Холла. Сопоставим
(0, 1)-матрице A = (a
ij
) размеров m × n двудольный граф с верши-
нами s
1
, . . . , s
m
; t
1
, . . . , t
n
, положив, что s
i
→ t
j
, если a
ij
= 1. Доба-
вим источник s и сток t, и положим, что s → s
i
, t
j
→ t для всех i, j.
Пропускные способности дуг считаем равными 1. Полученную сеть
назовём A-сетью.
В A-сети элементу a
ij
= 1 соответствует простой (s, t)-путь
s → s
i
→ t
j
→ t, причём это соответствие между единицами мат-
рицы A и простыми (s, t)-путями в A-сети взаимно однозначно. Как
легко видеть, элементы a
ij
= 1 и a
uv
= 1 стоят на разных линиях (то
есть, i 6= u, j 6= v) в точности тогда, когда соответствующие им пути
не имеют общих дуг. Следовательно, граничный ранг матрицы A ра-
вен максимальному количеству непересекающихся по дугам простых
(s, t)-путей. Применяя предложение 2, получаем
Предложение 3. Граничный ранг матрицы A равен минималь-
ной пропускной способности разреза A-сети (или, что то же, ве-
личине максимального потока в A-сети).
Как следствие получим простое доказательство теоремы Холла в
её нетривиальной части.
Следствие 3. Если любые k юношей (k = 1, . . . , m) знакомы
в совокупности не менее, чем с k девушками, то задача о свадьбах
разрешима.
Д о к а з а т е л ь с т в о. Пусть задача о свадьбах задаёт-
ся матрицей A. Как известно, граничный ранг матрицы A можно
трактовать как максимально возможное количество бракосочетаний.
Согласно предложению 3 для доказательства следствия достаточно
проверить, что минимальная пропускная способность A-сети равна
равна числу m юношей. Рассмотрим любой разрез (X,
¯
X). Пусть в
X входят k вершин, соответствующих юношам, и l вершин, соответ-
ствующих девушкам. Тогда в множество E
X
входят: а) m − k дуг,
ведущих из источника к вершинам-юношам из
¯
X, б) l дуг, ведущих
от вершин-девушек из X к источнику, в) по условию следствия, не
58                                Глава 3. Задача о максимальном потоке в сети


EX = {k → l : k ∈ X, l ∈ X̄} является (i, j)-разделяющим, при-
чём его пропускная способность равна |EX |. Отсюда и из следствия 1
вытекает утверждение, известное как теорема Менгера:
    Следствие 2. Максимальное число непересекающихся по дугам
простых (i, j)-путей равно минимальному числу элементов (i, j)-
разделяющего множества дуг.

     3. Граничный ранг (0, 1)-матрицы и теорема Холла. Сопоставим
(0, 1)-матрице A = (aij ) размеров m × n двудольный граф с верши-
нами s1 , . . . , sm ; t1 , . . . , tn , положив, что si → tj , если aij = 1. Доба-
вим источник s и сток t, и положим, что s → si , tj → t для всех i, j.
Пропускные способности дуг считаем равными 1. Полученную сеть
назовём A-сетью.
     В A-сети элементу aij = 1 соответствует простой (s, t)-путь
s → si → tj → t, причём это соответствие между единицами мат-
рицы A и простыми (s, t)-путями в A-сети взаимно однозначно. Как
легко видеть, элементы aij = 1 и auv = 1 стоят на разных линиях (то
есть, i 6= u, j 6= v) в точности тогда, когда соответствующие им пути
не имеют общих дуг. Следовательно, граничный ранг матрицы A ра-
вен максимальному количеству непересекающихся по дугам простых
(s, t)-путей. Применяя предложение 2, получаем
   Предложение 3. Граничный ранг матрицы A равен минималь-
ной пропускной способности разреза A-сети (или, что то же, ве-
личине максимального потока в A-сети).
    Как следствие получим простое доказательство теоремы Холла в
её нетривиальной части.
    Следствие 3. Если любые k юношей (k = 1, . . . , m) знакомы
в совокупности не менее, чем с k девушками, то задача о свадьбах
разрешима.
    Д о к а з а т е л ь с т в о. Пусть задача о свадьбах задаёт-
ся матрицей A. Как известно, граничный ранг матрицы A можно
трактовать как максимально возможное количество бракосочетаний.
Согласно предложению 3 для доказательства следствия достаточно
проверить, что минимальная пропускная способность A-сети равна
равна числу m юношей. Рассмотрим любой разрез (X, X̄). Пусть в
X входят k вершин, соответствующих юношам, и l вершин, соответ-
ствующих девушкам. Тогда в множество EX входят: а) m − k дуг,
ведущих из источника к вершинам-юношам из X̄, б) l дуг, ведущих
от вершин-девушек из X к источнику, в) по условию следствия, не

Страницы