Свойства операций над множествами (стр. 1 из 2)
Содержание
1. Свойства операций над множествами.................................................
2. Смежность и инцидентность. Степени вершины графа......................
3. Определение транспортной сети.........................................................
1.Свойства операций над множествами
Из определений объединения и пересечения множеств следует, что операции пересечения и объединения обладают следующими свойствами:
1. Коммутативность.
2. Ассоциативность.
3. Дистрибутивность.
4. 
5.
6. Законы де Моргана (законы двойственности).
1) 
2) 
Доказательство данных свойств проводится на основе определения равенства двух множеств.
Заметим, что закон ассоциативности при комбинировании операций объединения и вычитания, вообще говоря, не имеет места.
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).
Решение.
| d +(u) = 1; | d - (u) = 1; |
| d +(v) = 2; | d - (v) = 0; |
| d +(z) = 0; | d - (z)= 3; |
| d+(m)= 1; | d - (m)= 0. |
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.Поток через любой разрез равен сумме потоков из источника.