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

Содержание

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).

Решение.

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) называется сумма потоков из источника . В дальнейшем мы докажем, что она равна сумме потоков в сток .

Задача о максимальном поток

Внимание, отключите Adblock

Вы посетили наш сайт со включенным блокировщиком рекламы!
Ссылка для скачивания станет доступной сразу после отключения Adblock!

Скачать