Элементы теории множеств и графов

Через «» обозначается отношение принадлежности, то есть «хА» означает, что х принадлежит множеству А. Если х не является элементом А, то пишется «хА».

Множества А и В считаются равными, если они состоят из одних и тех же элементов: А = В. В противном случае А ? В.

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

Множества могут содержать подмножества, например, если В - подмножество А, то оно записывается через отношение включения «ВА», то есть каждый элемент А является элементом В (но не наоборот, см. рис. 1).

Рис. 1

Если ВА и А ? В, то В является собственным подмножеством А, т.е. ВА.

Множество, не содержащее элементов, называется пустым, например, В = .

Семейство всех подмножеств множества А обозначается как Р(А).

Множества, элементами которого являются множества, обычно называют классом.

Задание множества можно осуществлять следующим образом:

1) перечислением А := {a₁, a₂, … , a_n};

2) характеристическим предикатом (правилом):

А := {x | P(x)} ,

например, элементами А являются все значения х такие, что sin(x) 0.

3) порождающей процедурой:

А := {x | x := f},

например,

А := {n | for n = 1 to 9 do yield}.

Мощность множества А обозначается как .

Мощностью множества А называется класс всех множеств, эквивалентных А. Эквивалентность (~), в отличие от равенства - это возможность установить взаимно однозначное соответствие между элементами множеств А и В: А ~ В.

Используются следующие основные градации мощности:

а) n-конечные множества - это мощность множеств из набора любых n элементов; множество конечно;

б) если элементов бесконечное количество, но их можно перечислить (например, множество чисел), мощность такого количества обозначают через ч₀. Оно называется счетным.

в) если множество эквивалентно множеству всех натуральных чисел, его мощность обозначается через С и оно называется континуальным (мощность континуума). Множество не счетно.

Мощности произвольных множеств называются кардинальными числами.

Очевидно, что С «больше» ч₀, а ч₀ «больше» n.

Возникает ряд вопросов: может ли мощность быть больше С? Например, какова мощность множества комплексных чисел? Как оценить эту мощность?

Введем в рассмотрение так называемое прямое (декартово) произведение множеств А и В:

М = А Ч В := {(a, b) | a A, b B}.

Это множество упорядоченных пар элементов множеств А и В.

Если множество действительных чисел R имеет мощность С, множество мнимых чисел I также имеет мощность С. Тогда кажется, что . Однако можно показать, что .

Для ответа на подобные вопросы приведем свойства мощности:

n₁ + n₂ = n₁ + n₂,ч₀ + C = C,ч₀ ч₀ = ч₀,

n + ч₀ = ч₀,C + C = C,ч₀C = C,

ч₀ + ч₀ = ч₀,n₁n₂ = n₁n₂,CC = C.

Бинарным отношением между множествами А и В называется любое подмножество R A Ч В. Например, если А = В - множества четных действительных чисел от 0 до 8, тогда А Ч В - это множество пар четных чисел: 00, 02, 04, … 88.

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

1) Объединение (сумма, дизъюнкция)

Х = А В := {x | x A v x B}

«v» = «или» (см. рис. 2, а)

Рис. 2

2) Пересечение (произведение, конъюнкция)

Х = А В := {x | x A & x B}

«&» = «и» (см. рис. 2, б).

3) Разность (см. рис. 2, в)

Х = А \ В := {x | x A & x B}.

4) Симметрическая разность (см. рис. 2, г)

Х = (А \ В) (В \ А) = А Д В := {x | x A & x B, x В & x А }.

5) Дополнение

.

Элементы всех множеств можно считать элементами некоторого универсального множества U - универсума, который играет роль единицы. Тогда разность U \ A называется дополнением множества А и часто обозначается (-А) или (¬А).

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

1) Идемпотентность:А А = А, А А = А.

2) Коммутативность:А В = В А,А В = В А.

3) Ассоциативность:А (В С) = (А В) С,

А (В С) = (А В) С.

4) Дистрибутивность:А (В С) = (А В) (А С),

А (В С) = (А В) (А С).

5) Поглощение:(А В) А = А,(А В) А = А.

6) Свойства нуля:А = ,А = А.

7) Свойства единицы:А U = A,А U = U.

8) Инволютивность:.

9) Законы де Моргана:,.

10).

11).

12) Рефлексивность:А А.

13) Транзитивность: если А В и В С, то А С.

Алгебраическая операция определена на А, если можно указать закон, по которому любой паре (a, b) из АА ставится в соответствие третий элемент, принадлежащий этому же множеству.

c = a + b - сложение,с = ab - умножение, c = ab - в общем случае.

Основные свойства операций: коммутативность и ассоциативность.

Операция - это всегда отношение, но не наоборот.

Множество К называется кольцом, если в нем определены операции сложения и умножения, обе ассоциативны и дистрибутивны, причем сложение коммутативно и обладает обратной операцией.

Множество К называется линейным или векторным пространством, если для элементов (векторов) из К определены операции сложения и умножения на число Р и выполняются аксиомы:

1) Каждой паре векторов (х, у) отвечает вектор (х + у) и называется суммой, причем х + у = у + х (коммутативность) и х + (у + z) = (х + у) + z (ассоциативность).

Существует единственный нулевой вектор О такой, что х + О = х, х.

Существует вектор (-х) такой, что х + (-х) = О.

2) Каждой паре (, х), где - число, а х - вектор, отвечает вектор х, причем:

( х) = ( ) х,1х = х.

3) (х + у) = х + у,( + )х = х + х.

Множества и функции на них - это два типа объектов, на которых в конечном счете строится любая математическая теория.

Если аргументы функции f пробегают множество М и она принимает значения из того же множества, то f - это алгебраическая операция на М.

Итак, алгебра - это множество М вместе с набором операций на нем. Обозначается алгебра как двойка (М, ), где :={₁, ₂, …, _n} - набор (множество) операций, сигнатура алгебры, а М - носитель алгебры.

Группой называется множество, если:

1) выполняется условие наличия одной ассоциативной операции;

2) в группе есть элемент «е», удовлетворяющий условию a^.e = e^.a = a, он называется «единицей»;

3) для каждого элемента а существует единственный элемент (а^-1) такой, что

a^.a^-1 = e,(a^-1)^.a = e.

Если, кроме того, для a, b G имеет место коммутативность a^.b = b^.a, то группа называется коммутативной или абелевой.

При изложении материала о множествахе были использованы модели в виде графов. Наряду с теоретико-множественным описанием моделей систем представление в виде графов является одним из наиболее распространенных.

Граф Г - геометрическая фигура, построенная на множестве вершин V = {v₁, v₂, … v_m} и ребер R = {r₁, r₂, … r_n}:

Г = (V, R).

Если ребра ориентированы, то их называют дугами, а граф - ориентированным (орграфом). При этом вершины называются узлами.

а) б)

Рис. 2

Примеры использования графов для моделирования:

1. Неориентированные графы описывают (моделируют) дороги между населенными пунктами А, B, C и D (см. рис. 1, а).

Орграф описывает однонаправленные каналы передачи информации (см. рис. 1, б).

Дуга r_i, связанная с злом v_j, называется инцидентной этому узлу, причем, если заходит - положительно инцидентная, если выходит - отрицательно инцидентная.

Два узла v_k и v_i смежны, если им инцидентна одна дуга. Аналогично, две дуги смежны, если они инцидентны одному узлу, причем, если одна выходит, а другая заходит - последовательно смежны, в противном случае - параллельно смежны.

Дуга, выходящая из узла и в нее же заходящая, называется петлей.

Узел, из которого дуги только выходят, называется истоком, а в который только заходят - стоком. Узлы сток и исток - висячие узлы.

Две системы S₁ и S₂ с заданными на них отношениями R₁ и R₂ изоморфны, если:

1) их структурные элементы попарно взаимно однозначно соответствуют друг другу;

2) подмножество элементов А₁ системы S₁ связано отношением R₁, тогда соответствующее подмножество (см. п. 1) А₂ системы S₂ связано отношением R

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

Связи в системе можно изображать двояко:

1) элементы - это вершины, а связи - дуги (вершинный граф),

2) элементы - дуги, а связи - узлы (реберный или сигнальный граф).

Структуры графов можно представить как графически, так и структурными матрицами. Известны три вида структурных матриц, изоморфных графической модели графа: матрицы смежности, инцидентности (инциденций) и структуры связей.

Матрица смежности - квадратная матрица А = {a_ij}, , где m - число узлов, т.е. А_mxm, для которой

Число единиц в матрице А равно числу дуг n.

Эта матрица обладает интересным свойством: если возвести матрицу А в k-ю степень, то каждый элемент матрицы А^k будет равен числу путей из узла v_i в узел v_j длиной в k дуг.

Путь в графе - это последовательность последовательно смежных дуг, ориентированных в одном направлении.

Пример.

Как видно (см. рис. 3), через две (k = 2) смежные дуги можно попасть: из вершины 1 в вершину 4, из 2 в 1, из 2 в 3, из 3 в 4, из 4 в 1 и из 4.

Таким образом, можно алгоритмически определить, существует ли путь из v_i в v_j длиной в k дуг. Очевидно, что если число узлов m, максимальная степень k, в которую нужно возвести А для определения самого длинного пути, равна (m - 1).

Матрица инцидентности - в общем случае прямоугольная матрица В = {b_ij}, , , где m - число вершин, n - число ребер. Для орграфов:

Для неориентированных:

Для примера 1 матрица инцидентности имеет вид:

Матрица структуры связей С = {c_ij} устанавливает отношения между дугами:

С = В^ТВ,

С - симметрическая матрица размером n x n, т.е. С_nxn, для которой

Рис. 4

Таким образом, матрица структуры связей содержит информацию о взаимной ориентации пар дуг графа.

Кроме этого, могут использоваться структурные матрицы, кодирующие отдельные свойства графов:

- наличие контуров (контур = замкнутый путь),

- наличие путей,

- отношения касания.

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

Сильносвязанным называется граф, в котором любой узел достижим из любого другого узла.

Достижимость - это существование пути из узла v_i в узел v_j. Например, на рис. 3 путь из узла 1 в узел 4 имеет вид:

узел 1 W₁ узел 2 W₂ узел 3 W₄ узел 4.

Может оказаться, что не все узлы достижимы из остальных узлов. В этом случае может быть выделен подграф Г₁, т.е. совокупность, подмножество узлов, для которого условие сильной связности выполняется. Например, граф Г (см. рис. 5) не сильносвязный, т.к. в узел 1 из узлов 2, 3 и 4 нет путей. Сильносвязной компонентой Г₁ для графа Г состоит из узлов 2, 3 и 4 с соответствующими дугами W₂ - W₅.

Физический смысл сильной связности - наличие обратных связей (ОС) между всеми узлами или, другими словами, взаимозависимость (взаимовлияние) всех переменных в графе.

Важность понятия «сильная связность» вытекает из того, что практически все целенаправленные системы строятся на основе принципа обратной связи, когда информация о выходных величинах (координатах) некоторого объекта используется для формирования управляющего сигнала U этим объектом.

Структура простейшей системы управления описывается графом (см. рис. 6), где W₁ можно интерпретировать как модель объекта управления, а W₂ - модель управляющего устройства. Узлы 1 - управление U, 2 и 4 можно интерпретировать как выходную величину объекта у, 3 (е) -ошибка регулирования, узел 5 - задание х (желаемое значение величины у).