1 Основные понятия теории множеств

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

Объекты любой природы (числа, люди, вещи и т. д.), составляющие множество, называют его элементами. Например, студент Иванов является элементом множества студентов IV курса,

март – элементом множества месяцев в году и т.д.

Для того чтобы некоторую совокупность элементов можно было назвать множеством, необходимо, чтобы выполнялись следующие условия:

- должно существовать правило, позволяющее определить, принадлежит ли указанный элемент данной совокупности;

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

Тот факт, что элемент a принадлежит множеству А записывается так: a A, в противном случае пишем a A. Для однозначного описания некоторого множества мы будем пользоваться следующими способами:

– перечислением всех его элементов. Например, множество A, состоящее из объектов:a, b, c, d записывают так: A = {a, b, c, d}. Данный способ применим только для конечных множеств, число элементов которых невелико;

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

Например, множество K натуральных чисел, меньших 5 можно записать: K= {1, 2, 3, 4} или

K={х | х N и х < 5}.

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

Пустым множеством называют единственное множество, не содержащее ни одного элемента (обозначается символом ). Например, это множество транзисторов, изготовленных в 1930 году.2

Множества A и B считают равными, если они состоят из одних и тех же элементов (записывают A = B). Например, равны следующие множества: А={>, $, @, !} и B={!, >, @, $}.

Множество B называют подмножеством множества A тогда и только тогда, когда каждый элемент B принадлежит множеству A (записывается: В А). Например, А – множество студентов вуза, В – подмножество первокурсников этого вуза.

Свойство подмножеств: если В А и А В, то А=В.

Достаточно часто для наглядного изображения множеств и операций над ними используют так называемые круги Эйлера (диаграммы Венна). На следующем рисунке

показаны множества А и B такие, что В А.

Часто бывает, что рассматриваются только подмножества одного и того же множества.

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

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

Граф – система, которая интуитивно может быть рассмотрена

как множество кружков и множество соединяющих их линий

(геометрический способ задания графа – см. рисунок 1). Кружки

называются вершинами графа, линии со стрелками – дугами, без

стрелок – ребрами. Граф, в котором направление линий не выделя-

ется (все линии являются ребрами), называется неориентирован-

ным; граф, в котором направление линий принципиально (линии

являются дугами) называется ориентированным.

Теория графов может рассматриваться как раздел дискретной

математики (точнее – теории множеств), и формальное определе-

Начало теории графов датируют 1736 г., когда Л. Эйлер решил популярную вто время «задачу о кенигсбергских мостах». Термин «граф» впервые был введенспустя 200 лет (в 1936 г.) Д. Кенигом. 2

ние графа таково: задано конечное множество X, состоящее из n

элементов (X = {1, 2, ..., n}), называемых вершинами графа, и

подмножество V декартова произведения X ¥ X, то есть V Õ X

называемое множеством дуг, тогда ориентированным графом G

называется совокупность (X, V) (неориентированным графом назы-

вается совокупность множества X и множества неупорядоченных

пар элементов, каждый из которых принадлежит множеству X).

Дугу между вершинами i и j, i, j Œ X, будем обозначать (i, j). Число

дуг графа будем обозначать m (V = (v1, v2, ..., vт)).

Язык графов оказывается удобным для описания многих фи-

зических, технических, экономических, биологических, социаль-

ных и других систем.

Приведем ряд примеров приложений теории графов.

1. «Транспортные» задачи, в которых вершинами графа явля-

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

и/или другие транспортные (например, авиационные) маршруты.

Другой пример – сети снабжения (энергоснабжения, газоснабже-

ния, снабжения товарами и т.д.), в которых вершинами являются

пункты производства и потребления, а ребрами – возможные

маршруты перемещения (линии электропередач, газопроводы,

дороги и т.д.). Соответствующий класс задач оптимизации потоков

грузов, размещения пунктов производства и потребления и т.д.,

иногда называется задачами обеспечения или задачами о размеще-

нии. Их подклассом являются задачи о грузоперевозках [7, 12].

2. «Технологические задачи», в которых вершины отражают

производственные элементы (заводы, цеха, станки и т.д.), а дуги – 3

потоки сырья, материалов и продукции между ними, заключаются

в определении оптимальной загрузки производственных элементов

и обеспечивающих эту загрузку потоков [7, 12].

3. Обменные схемы, являющиеся моделями таких явлений как

бартер, взаимозачеты и т.д. Вершины графа при этом описывают

участников обменной схемы (цепочки), а дуги – потоки матери-

альных и финансовых ресурсов между ними. Задача заключается в

определении цепочки обменов, оптимальной с точки зрения, на-

пример, организатора обмена и согласованной с интересами участ-

ников цепочки и существующими ограничениями [6, 9, 17].

4. Управление проектами

. С точки зрения теории графов про-

ект – совокупность операций и зависимостей между ними (сетевой

график – см. ниже). Хрестоматийным примером является проект

строительства некоторого объекта. Совокупность моделей и мето-

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

ванных на решение задач управления проектами, получила назва-

ние календарно-сетевого планирования и управления (КСПУ)

[7, 10]. В рамках КСПУ решаются задачи определения последова-

тельности выполнения операций и распределения ресурсов между

ними, оптимальных с точки зрения тех или иных критериев (вре-

мени выполнения проекта, затрат, риска и др.).

5. Модели коллективов и групп, используемые в социологии,

основываются на представлении людей или их групп в виде вер-

шин, а отношений между ними (например, отношений знакомства,

доверия, симпатии и т.д.) – в виде ребер или дуг. В рамках подоб-

ного описания решаются задачи исследования структуры социаль-

ных групп, их сравнения, определения агрегированных показате-

лей, отражающих степень напряженности, согласованности

взаимодействия и др.

6. Модели организационных структур, в которых вершинами

являются элементы организационной системы, а ребрами или

дугами – связи (информационные, управляющие, технологические

и др.) между ними