1.5 Произведение множеств

Прямым (декартовым) произведением двух множеств А и В называется множество всех упорядоченных пар, в которой I элемент из множества А, II элемент – из множества В, т.е. А×В = {(а, в)/а Є А ̂в Є В}

Пример: А={2;5;7;9} и В ={2;4;7},

Тогда А×В = {(2,2) ; (2,4) ; (2,7) ; (5,2) ; (5,4) ; (5,7) ; (7,2) ; (7,4) ; (7,7) ; (9,2) ; (9,4 ); (9,7)}

А∩В={2,7}; А∪В={2,4,5,7,9}; А/В={5,9}; В/А={4}; А Ө В={4,5,9}

Элементы множества А×В называются точками; В паре (х, у) абсцисса – х и ордината – у точки, соответствующей этой паре.

Множество точек плоскости является прямым произведением вида R×R=R², где R–множество действительных чисел.

R² называется декартовым квадратом на R.

Элементы теории графов. Виды и способы задания графов

Во многих прикладных задачах изучаются системы связей между различными объектами. Объекты называются вершинами и обозначаются точками, а связи – дугами. Такие системы образуют графы. Например: граф изображает сеть улиц а городе; сеть дорог, трубопроводов, блок – схемы программирования и многие другие модели.

Определение. Графом называется совокупность двух множеств – непустого множества V вершин и множество Е двухэлементных подмножеств множества V (множество ребер Е).

Обозначаются G(V,E) = <V;E>,V≠O

Множество двух элементных подмножеств определяет симметричное бинарное отношение на множестве Е = V×V, E = E^-1; поэтому ребро можно считать не только как множество , но и как пару число вершин обозначают Р, число ребер – q; если дугами являются пары вершин то дуга считается исходящей из v₁ и заходящей в v₂; граф G изображают диаграммой.

2

1 V = - множество вершин

3 Е = -

Множество дуг

4

Если имеется несколько дуг, исходящих из вершины v₁ в вершину v₂ , такие дуги называются кратными, граф называется кратным.

Если все элементы множества Е – упорядоченные пары, то граф G называется ориентированным (орграф), элементы V называются узлами, а множество Е дугами, т.е. если (а, b) E, (b, a) ∉ E

Если элементом Е может быть пара одинаковых (не различных) элементов V, то такой элемент называется петлей, а граф называется графом с петлями (псевдографом). Если Е содержит несколько одинаковых элементов, то эти элементы называются кратными ребрами, a G - мультиграфом.

Если (а, b) E /\ (b, a) E, то G называется неориентированным (неографом). В этом случае дуга называется ребром и обозначается в виде отрезка, соединяющего вершины, а вершины а и b называются концами ребра и информацию об этих дугах пишут: =

или - ребро графа

Маршруты, цепи, циклы. Длина маршрута.

Маршрутом в графе G называется чередующаяся последовательность вершин и ребер: v₀, l1, v₁, l2,…,l_k, v_k, в которой любые два соседних элемента инцидентны. Это определение подходит и для псевдо и мультиграфов. В орграфе достаточно указать только последовательность вершин (узлов) или только последовательность ребер (дуг) если v₀=v_k,то маршрут называется замкнутым, если нет, то открытым.

Если все ребра различны, то маршрут называется цепью, если все вершины различны, то маршрут называется простой цепью В цепи v₀ и v_k называются концами цепи; цепь соединяющая вершины u и v обозначают < u, v>; замкнутая цепь называется циклом; простая замкнутая цепь прстым циклом. Граф без циклов называется ациклическим.

Для орграфов цепь называется путем, а цикл – контуром.

Пример 1.

v₁ v₂

1º v₁, v₃, v₁, v₄ – маршрут, но не цепь.

2º v₁, v₃, v₅, v₂, v₃, v₄ – цепь, но не простая ( т.к. не все

v₃ вершины различны, а различны рёбра)

3º v₁, v₄, v₃, v₂, v₅ – простая цепь, но не цикл ( т.к. не

v₄ v₅ замкнута)

4º v₁, v₃, v₅, v₂, v₃, v₄, v₁ – но не простой ( т.к. цепь не простая хотя, замкнутая)

5º v₁, v₃, v₄, v₁ – простой цикл ( все ребра и все вершины различны)

Длиной маршрута называется количество ребер в нем (с повторениями).

Пример 2.

Дан граф G, в нем:

1 2 (1,2), (1,2,4,7), (3,4,5,6) – простые цепи

(3,4,5,6) – цепь простая, но не ЦИК

3 4 5 6

(1,2,4,7,8,4) – не простая цепь ( есть одинаковые

вершины)

7 8 (1,2,4,7,8,4,1) – цикл, но не простой.

Пусть G – граф, возможно ориентированный. Маршрут называется путём, если все его дуги различны. Путь называется контуром, если v₀=v_k. Вершина v называется достижимой из вершины u, если <u, v> путь. Расстоянием между вершинами называется длина кратчайшей цепи <u, v>

Пример 3.

2 4 5

1 3

Контур (1,2,3)

Вершина 5 достижима из любой вершины; из вершины 5 недостижима ни одна из остальных вершин