Свойства операций над множествами

Содержание

1. Свойства операций над множествами.................................................

2. Смежность и инцидентность. Степени вершины графа......................

3. Определение транспортной сети.........................................................

1.Свойства операций над множествами

Из определений объединения и пересечения множеств следует, что операции пересечения и объединения обладают следующими свойствами:

1. Коммутативность.

2. Ассоциативность.

3. Дистрибутивность.

4.

5.

6. Законы де Моргана (законы двойственности).

1)

2)

Доказательство данных свойств проводится на основе определения равенства двух множеств.

Заметим, что закон ассоциативности при комбинировании операций объединения и вычитания, вообще говоря, не имеет места.

Пример. A = {1; 2; 3; 4}

B = {3; 4; 5; 6}

A B= {1; 2}

A

Но

2.Смежность и инцидентность. Степени вершины графа

Определение. Если е = {v, w} – ребро графа, то вершиныv, w называются концами ребра е; в этом случае также говорят, что ребро е соединяет вершины v, w.

Определение. Если е = {v, w} – дуга орграфа, то вершинаv называется началом, а вершина w – концом дуги е; в этом случае также говорят, что дуга е исходит из вершины v и заходит в вершину w.

Между элементами множества вершин и множества ребер определено отношение инцидентности. Говорят, что ребро е инцидентно вершинам v, w, если оно соединяет эти вершины и наоборот, каждая из вершин v, w инцидентна ребру е.

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

Определение. Степенью вершиныv графа G называется число d(v) ребер графа, которым инцидентна эта вершина.

Определение. Вершина, локальная степень которой равна 0, называется изолированной; степень которой равна 1 – висячей.

Замечание. В случае неориентированного псевдографа обычно считается, что вклад каждой петли, инцидентной некоторой вершине v, равен 2 (тогда как вклад любого другого ребра, инцидентного вершине v, равен 1).

Определение. Полустепенью исхода (захода) вершиныv орграфа D называется число d⁺(v) (d^-(v)) дуг орграфа D, исходящих из вершины v (заходящих в вершину v).

Замечание. В случае ориентированного псевдографа вклад каждой петли, инцидентной некоторой вершине v, равен 1, как в d⁺(v), так и в d^-(v).

Количество вершин и ребер в графе G обозначим соответственно через n(G) и m(G), а количество вершин и дуг в орграфе D – через n(D) и m(D).

Утверждение. Для любого псевдографа G выполняется равенство

Утверждение. Для любого ориентированного псевдографа D выполняется равенство

Пример.

Найти локальные степени графа (рис. 1) и орграфа (рис. 2).

Решение.

3.Определение транспортной сети

В теории графов транспортная сеть — ориентированный графG = (V,E), в котором каждое ребро имеет неотрицательную пропускную способность и поток f(u,v). Выделяются две вершины: источник s и сток t такие, что любая другая вершина сети лежит на пути из s в t. Транспортная сеть может быть использована для моделирования, например, дорожного трафика.

Целочисленная транспортная сеть — транспортная сеть, все пропускные способности ребер которой — целые числа.

Транспортная сеть (flow network) — ориентированный граф в котором

• каждому ребру приписана неотрицательная пропускная способность . Если , то .
• выделены две вершины: источник (source) s и сток (sink) t, такие, что любая другая вершина сети лежит на пути из s в t.

Поток (flow) — функция со следующими свойствами для любых вершин и :

• Ограничение пропускной способности (capacity constraints). Поток не может превысить пропускную способность:
• Антисимметричность (skew symmetry). Поток из в должен быть противоположным потоку из в :
• Сохранение потока (flow conservation): для всех , кроме источника и стока.

Величиной потока (value of flow) называется сумма потоков из источника . В дальнейшем мы докажем, что она равна сумме потоков в сток .

Задача о максимальном потоке (maximum flow problem): найти поток f такой, что величина потока максимальна.

Разрез (s-t cut) — разбиение множества всех вершин V на два подмножества, A и B, таких что , .

Пропускная способность разреза (A,B) (the capacity of an s-t cut (A,B) ) — сумма пропускных способностей всех рёбер из A в B .

Поток через разрез (A,B) — сумма всех потоков из A в B . Он не превышает пропускную способность разреза, поскольку .

Минимальный разрез - разрез с минимальной пропускной способностью.

Остаточная пропускная способность (residual capacity) ребра Она всегда неотрицательна из-за условия на ограничение пропускной способности.

Остаточная сеть (residual network) Здесь - множество рёбер с неотрицательной остаточной пропускной способностью. В остаточной сети может быть ребро из в , даже если его нет в исходной сети. Это выполняется, когда в исходной сети есть обратное ребро (v,u) и поток по нему положителен.

Увеличивающий (остаточный, дополняющий) путь (augmenting path) — это путь в остаточной сети, где и Можно доказать, что поток максимален тогда и только тогда, когда нет увеличивающего пути в остаточной сети.

Свойства

1.Поток через любой разрез равен сумме потоков из источника.

Доказательство: пускай есть разрез (A,B). Рассмотрим сумму всех потоков из всех вершин, принадлежащих А. Она равна

В первой из сумм для любой пары вершин (u,v) есть два слагаемых f(u,v) и f(v,u), равных по модулю и противоположных по знаку. Следовательно, эта сумма равна нулю. Вторая сумма есть поток через разрез (A,B). Следовательно, сумма всех потоков из всех вершин, принадлежащих А, равна потоку через разрез. С другой стороны, сумма потоков из любой вершины, кроме s и t, равна нулю, а . Следовательно, сумма всех потоков из всех вершин, принадлежащих А, равна сумме потоков из s. Следовательно, поток через разрез (A,B) равен сумме потоков из s, что и требовалось доказать.

2.Сумма потоков из источника равна сумме потоков в сток.

Доказательство: рассмотрим разрез . Поток через этот разрез равен сумме потоков в сток. С другой стороны, по только что доказанному, поток через этот (как и любой другой) разрез равен сумме потоков из источника. Теорема доказана.

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

Доказательство: Пускай такой путь P существует. Пусть c - минимальная из пропускных способностей рёбер, принадлежащих P. Пускай поток равен c на всех рёбрах из P, и нулю на всех остальных рёбрах. Тогда суммарный поток из источника равен c, то есть положителен. Теперь допустим, что такого пути нет, то есть t недостижимо из s по рёбрам с положительной пропускной способностью. Пусть A - множество вершин, достижимых из s по таким рёбрам, B - недостижимых. Тогда, поскольку , , то (A,B) является разрезом. Кроме того, не существует ребра (a,b) с положительной пропускной способностью, такого что , , иначе b было бы достижимо из s. Следовательно, пропускная способность разреза (A,B) равна нулю, а значит и поток через него всегда равен нулю. Следовательно, сумма потоков из источника всегда равна нулю.

4.Поток максимален тогда и только тогда, когда нет увеличивающего пути в остаточной сети.

Доказательство: пускай такой путь P есть. Пусть c - минимальная из пропускных способностей рёбер, принадлежащих P, в остаточной сети. Для всех пар увеличим f(u,v) на c и уменьшим f(v,u) на c. Мы увеличили суммарный поток из источника на s, следовательно, он был не максимален. Теперь, наоборот, допустим, что такого пути нет. Докажем от противного, что поток f в исходной сети обеспечивает максимальный суммарный поток из s. Пусть это не так, тогда есть поток f', обеспечивающий больший суммарный поток из s. Легко убедиться, что f'-f - поток в остаточной сети, обеспечивающий в ней положительный суммарный поток из s. Следовательно, в остаточной сети есть путь из источника в сток, то есть увеличивающий путь. Мы получили противоречие.

5.Теорема Форда-Фалкерсона. Величина максимального потока равна пропускной способности минимального разреза.

Доказательство: сумма потоков из s всегда равна потоку через любой, в том числе минимальный, разрез, следовательно, не превышает пропускной способности минимального разреза. Следовательно, максимальный поток не больше пропускной способности минимального разреза. Осталось доказать, что он и не меньше её. Пускай поток максимален. Тогда в остаточной сети сток не достижим из источника. Пусть A - множество вершин, достижимых из источника в остаточной сети, B - недостижимых. Тогда, поскольку , , то (A,B) является разрезом. Кроме того, в остаточной сети не существует ребра (a,b) с положительной пропускной способностью, такого что , , иначе бы b было достижимо из s. Следовательно, в исходной сети поток по любому такому ребру равен его пропускной способности, и, значит, поток через разрез (A,B) равен его пропускной способности. Но поток через любой разрез равен суммарному потоку из источника, который в данном случае равен максимальному потоку. С другой стороны, пропускная способность любого разреза не меньше пропускной способности минимального разреза. Комбинируя эти три утверждения, получаем, что максимальный поток не меньше пропускной способности минимального разреза. Теорема доказана.

Пример.

Транспортная сеть с указанием потока и пропускной способности.

Здесь изображена транспортная сеть с источником , стоком и четырьмя дополнительными узлами. Поток и пропускная способность обозначены соответственно . Поток из источника к стоку равен 5, что легко видно, так как поток из равен 5, что есть также в .

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

Например, ребро . Этот поток не максимален. Есть увеличивающие пути , и . Остаточная пропускная способность первого пути

.

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

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

Самый частый пример использования транспортных сетей — нахождение максимального потока, который означает максимальный суммарный поток от s к t. Для нахождения максимального потока в сети может быть использован алгоритм Форда — Фалкерсона, алгоритм Эдмондса — Карпа и другие.

Алгоритм Форда — Фалкерсона решает задачу нахождения максимального потока в транспортной сети.

Идея алгоритма заключается в следующем. Изначально величине потока присваивается значение 0: f(u,v) = 0 для всех . Затем величина потока итеративно увеличивается посредством поиска увеличивающего пути (путь от источника s к стоку t, вдоль которого можно послать больший поток). Процесс повторяется, пока можно найти увеличивающий путь.

Алгоритм Эдмондса — Карпа решает задачу нахождения максимального потока в транспортной сети. Алгоритм представляет собой частный случай метода Форда — Фалкерсона и работает за время O(VE²).

Алгоритм Эдмондса — Карпа — это вариант алгоритма Форда — Фалкерсона, при котором на каждом шаге выбирают кратчайший дополняющий путь из s в t в остаточной сети (полагая, что каждое ребро имеет единичную длину). Кратчайший путь находится поиском в ширину.

В задаче о потоке минимальной стоимости, каждому ребру (u,v) сопоставляется цена k(u,v), цена пересылки потока f(u,v) через ребро . Задача — послать заданное количество потока от s к t с наименьшей ценой.