2.3 Декартово произведение множеств. Соответствия и отношения на множествах

Кортежем длины n называют совокупность элементов a₁, a₂, … , a_n , которая в отличии от множества {a₁, a₂, … , a_n} характеризуется порядком входящих в эту совокупность элементов, то есть каждый элемент занимает определенное место.

При n=2 кортеж называется упорядоченной парой, при n=3 – упорядоченной тройкой, при n=4 – упорядоченной четверкой и т. д.

Декартовым (прямым) произведением множеств A₁, A₂, … ,A_n называется множество A₁×A₂×…×A_n, состоящее из всех кортежей длины n на множествах A₁, A₂, … , A_n.

Если A₁=A₂=…=A_n=А, то декартово произведение множеств A₁, A₂, … , A_n называют декартовой степенью множества А и обозначают через Аⁿ.

При n=2 А² называют декартовым квадратом, а при n=3 А³ называют декартовым кубом. По определению полагают, что А¹=А, А⁰={λ}, где {λ} – одноэлементное множество, состоящее из пустого кортежа λ.

Декартово произведение множеств обладает следующими свойствами:

1) А×В ≠ В×А;

2) А×(В×С) ≠ (А×В)×С;

3) А^m×Аⁿ ≠ А^m+n;

4) A×Ø = Ø×A = Ø;

5) А×(В  С) = (А×В)  (А×С);

6) А×(В  С) = (А×В)  (А×С).

Бинарным соответствием из А в В называется всякое подмножество Р декартова произведения А×В, то есть Р А×В. При этом множество А называется множеством отправления соответствия Р, а В – множеством прибытия соответствия Р.

Элементы множества отправления, для которых соответствие установлено, называется областью определения соответствия. Элементы множества прибытия, поставленные в соответствие элементам множества отправления, называются областью значений соответствия.

Соответствие Р может быть представлено графически в виде схемы, на которой элементы множеств А и В изображаются точками, а упорядоченные пары в виде стрелок, направленных от элементов множества отправления к элементам множества прибытия (рис. 2.4).

Рис. 2.4 Графическое представление соответствия

Бинарным отношением на множестве А называется всякое подмножество R декартова квадрата А², то есть R А².

Если x, y R, где R – бинарное отношение на множестве А, то говорят, что элемент находится в отношении R к элементу y и записывают это через xRy.

2.4 Основные понятия теории графов

Граф – это множество элементов V, называемых вершинами, и набор Е неупорядоченных и упорядоченных пар вершин. Граф обозначается через G(V, E).

Неупорядоченная пара вершин (u, v) называется ребром, упорядоченная пара u, v – дугой. Принято говорить, что ребро (u, v) соединяет вершины u и v, а дуга u, v начинается в вершине u и заканчивается в вершине v.

Граф, содержащий только ребра, называется неориентированным, а граф, содержащий только дуги, – ориентированным. Граф, в состав которого входят как ребра, так и дуги называется смешанным.

Если пара вершин соединяется двумя или более ребрами (дугами одного направления), то такие ребра (дуги) называются кратными. Если ребро (дуга) начинается и заканчивается в одной и той же вершине, то такое ребро (дуга) называется петлей.

Иногда под графом понимают граф без петель и кратных ребер; тогда граф, в котором допускаются кратные ребра (дуги), называется мультиграфом, а граф, в котором могут присутствовать кратные ребра (дуги) и петли – псевдографом.

Вершины, соединенные ребром или дугой, называются смежными. Ребра, имеющие общую вершину, также называются смежными. Ребро (дуга) и любая из его вершин называются инцидентными. Вершина, не являющаяся инцидентной ни одному ребру (дуге) графа, называется изолированной. Если граф состоит только из изолированных вершин, то его называют ноль-графом.

Часто графы изображают в виде схем (рис. 2.5), на которых вершины показывают точками, ребра – линиями между точками, а дуги – линиями со стрелками, направленными от начальной вершины к конечной.

Рис. 2.5 Представление графов в виде схем: а) – неориентированный граф; б) – ориентированный граф

Можно выделить следующие способы задания графа:

1. Путем перечисления всех вершин v₁, v₂, … v_n и ребер (дуг) e₁, e₂, … e_m графа G(V, E).

2. С помощью матрицы смежности.

Матрицей смежности, соответствующей графу G(V, E), называется матрица A=[a_ij], у которой элемент a_ij равен числу ребер (дуг), соединяющих вершины v_i и v_j (идущих из v_i в v_j), и a_ij=0, если соответствующие вершины не являются смежными.

Например, для графов, представленных на рис. 2.5а и 2.5б, соответствующие матрицы будет иметь следующий вид:

3. С помощью матрицы инцидентности.

Матрицей инцидентности графа G(V, E) называется матрица B=[b_ij], в которой элемент b_ij =1, если вершина v_i инцидентна ребру e_j, и b_ij =0, если вершина v_i и ребро e_j не инцидентны.

4. С помощью списка смежности.

Список смежности графа G(V, E) представляет собой указание для каждой вершины этого графа множества смежных с ней вершин.

Подграфом G'(V', E') графа G(V, E) называется граф с множеством вершин V' V и множеством ребер (дуг) Е' E, каждое из которых инцидентно только вершинам из V'. Если подграф G'(V', E') графа G(V, E) содержит все его вершины (V'=V), то его называют остовным.

Последовательности ребер (v₀, v₁), (v₁, v₂), … , (v_i, v_i+1), … , (v_r-1, v_r) или дуг v₀, v₁ , v₁, v₂ , … , v_i, v_i+1 , … , v_r-1, v_r называются маршрутами, соединяющими вершины v₀ и v_r. Маршрут замкнут, если v₀=v_r. Маршрут называется цепью, если все его ребра (дуги) различны, и простой цепью, если все его вершины различны. Замкнутая (простая) цепь называется (простым) циклом.

Граф называется связным, если любая пара его вершин соединена маршрутом. Связный граф, не имеющий циклов, называется деревом.