Книги по разным темам Pages:     | 1 |   ...   | 10 | 11 | 12 |

Если при некотором потоке, вершину w не удается пометить, то поток будет максимальным. Действительно, если через V обозначить множество помеченных вершин, а через W - множество непомеченных, причем x V, w W, то множество дуг R вида (x, y), где x V, y W будет разрезом. При этом все такие дуги (x, y) будут насыщенными, в противном случае y была бы помечена. Значит - максимальный поток. Рассмотрим одно приложение данных результатов.

Паросочетанием в неориентированном графе G(V, E) называется произвольное множество ребер M E, такое, что никакие два ребра из М не имеют общей вершины. Особый интерес представляет нахождение паросочетаний для двудольных графов, поскольку этот вопрос возникает в задачах теории связи. Покажем, как задача нахождения наибольшего паросочетания в двудольном графе сводится к построению максимального потока в некоторой сети. Пусть H = (V1, V2, E) - произвольный двудольный граф. Это означает, что V1 V2 = и каждое ребро e E имеет вид (x, y), x V1, y V2.

I Построим сеть S(H) следующим образом:

1. Добавим вершины s (источник) и t (сток).

2. Добавим дуги от s к каждой вершине x V1 и дуги от каждой вершины y V2 к t.

3. Ориентируем ребра e E, e=(x,y) от x к y.

4. Припишем всем дугам пропускную способность 1.

Согласно изложенному выше, для сети S(H) существует максимальный поток.

Теорема 2. Существует взаимно однозначное соответствие между паросочетаниями в H и потоками в S(H), при котором паросочетанию М мощности k соответствует поток величины k, причем соответствие устанавливается так:

Паросочетание M = {(x1, y1), Е, (xk, yk)} Поток (s, xi) = (xi, yi) = (yi, t) = мощности k величины k (e) = 0 (1) для остальных дуг Паросочетание M= {(x, y)}, Поток величины k x V1, y Vмощности k (x, y) = 1 (2) Пусть M = {(x1, y1), Е, (xk, yk)} - паросочетание мощности k. Тогда вершины x1, Е, xk и вершины y1, Е, yk попарно различны. Отсюда следует, что функция, определенная (1), является потоком из s в t. Далее, разным паросочетаниям М соответствуют разные потоки. С другой стороны, если - поток в сети S(H), то количество потока, прибывающего (а значит, убывающего) в каждую вершину x V1 не превосходит единицы, т.к. единственная дуга, входящая в x - это дуга (s, x) с пропускной способностью, равной 1. Отсюда следует, что в множестве М, определенном (2) нет ребер вида (x, y1), (x, y2), y1 y2. Аналогично в М нет ребер вида (x1, y), (x2, y), x1 x2. Следовательно, М - паросочетание в H. Легко заметить, что отображения, определенные (1) и (2), являются обратными друг к другу.

Таким образом, для построения максимального паросочетания можно использовать алгоритм построения максимального потока.

Упражнения.

1. Доказать, что если число ребер графа с вершинами (n > 2) больше, чем n -, то он связен.

2. Доказать, что если степень каждой вершины G не меньше двух, то G содержит цикл.

3. Выяснить, при каких m, n графы Кm,n (полный двудольный граф с m и n вершинами в долях), Кn (полный граф на n вершинах), Вn (граф единичного куба) являются эйлеровыми.

4. Доказать, что графы Кn, Кn,n, Вn являются гамильтоновыми.

5. Индукцией по n доказать, что каждое дерево с n 2 вершинами является двудольным графом.

6. Найти число остовных деревьев графа де Брейна с n = 3.

7. Найти максимальный поток в графе a1 b 3 7 2 s 2 a2 7 b2 4 t 9 5 a3 1 b ЛИТЕРАТУРА [1] Холл. М. Комбинаторика. М., Мир, 1970.

[2] Райзер Г.Дж. Комбинаторная математика, М., Мир, 1966.

[3] Рыбников К.А. Введение в комбинаторный анализ. М., МГУ, 1985.

[4] Айгнер М. Комбинаторная теория. М., Мир, 1982.

[5] Липский В. Комбинаторика для программистов, М., Мир, 1988.

[6] Оре О. Теория графов. М., Наука, 1968.

[7] Харари Ф. Теория графов. М., Мир, 1973.

[8] Форд Л.Р., Фалкерсон Д.Р. Потоки в сетях, М., Мир, 1963.

[9] Уилсон Р. Введение в теорию графов, М., 1977.

[10] Кофман А. Введение в прикладную комбинаторику. М., 1975.

[11] Комбинаторный анализ. Задачи и упражнения. Под ред. Рыбникова К.А., М., [12] Гаврилов Г.П., Сапоженко А.А. Задачи и упражнения по курсу дискретной математики, М., Наука, 1992.

Pages:     | 1 |   ...   | 10 | 11 | 12 |    Книги по разным темам