1.6.2. Элементы теории множеств

Множеством называется любое объединение определенных

вполне различимых объектов; их может и не быть вообще. Можно

говорить о множестве точек на отрезке [0,1], множестве студентов в

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

образуют любые объекты, объединенные по любому признаку.

Объекты, составляющие множество, называются элементами множества.

Множество, не имеющее ни одного элемента, называется пустым,

оно обозначается 0. Множество, состоящее из конечного числа

элементов, называется конечным, в противном случае — бесконечным.

Задать множество можно перечислением его элементов.

Например, множество образованное из п элементов а,, а2, ..., ап,

обозначается А = {а,, а2, ..., ап}; пишется а е А (говорится «элемент а при-

55

надлежит множеству А»), если а является элементом множества А, в

противном случае a g A.

Задать множество можно также, указав общее свойство для всех

его и только его элементов. Например, множество точек

равноудаленных от концов отрезка.

Два множества считаются равными, если состоят из одних и тех

же элементов; записывается этот факт А = В.

Множество А, называется подмножеством А (записывается А,сА),

если все элементы множества А1 являются элементами А.

Для множеств определены следующие операции: объединение,

пересечение, дополнение.

Объединением множеств А и В (записывается AuB) называется

множество, состоящее из элементов как одного, так и второго

множества. Например, А и В — множества точек, принадлежащих

некоторым двум кругам, имеющим общие точки, тогда объединением

AuB будет фигура, состоящая из общих точек.

Пересечением множеств А и В (записывается АпВ) называется

множество, состоящее из элементов, принадлежащих как одному, так

и второму множеству одновременно.

Дополнением множества А до В называется множество, состоящее

из элементов множества В, не принадлежащих А. Дополнение

обозначается А = В-А (рис. 1.7).

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

56

1.6.3. Элементы теории графов

Основные понятия

Граф задается парой множеств: множества Е, называемого

множеством вершин, и множества U, называемого множеством ребер.

Ребро u g U есть пара (е., е.), где е., е. g Е , указывающая, между

какими двумя вершинами проведено ребро. Говорят, что ребро ug U

инцидентно вершинам е., е.. Если порядок ребер не имеет значения,

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

просто ребром, если же порядок имеет значение, то ребро и = (е., е.)

называется ориентированным ребром или дугой. Вершина е. —

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

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

Граф G(E,U) называется конечным, если множество Е вершин

конечно.

Граф G(E,U), у которого любые две вершины соединены ребром,

называется полным. Если хотя бы две вершины соединены

несколькими ребрами, то такой граф называется мулътиграфом. Две

вершины е., e.G E называются смежными, если они соединены ребром.

Число ребер, инцидентных данной вершине е., называется локальной

степенью этой вершины р(е.). Число ребер г графа G(E,U)

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

г = ~У.Р(е{), где п — количество вершин в графе.

2 ы

Рассмотрим граф, изображенный на рис. 1.8.

Рис. 1.8. Ориентированный граф

57

Множество вершин графа состоит из пяти элементов: Е = {1, 2,

3, 4, 5}, а множество ребер U = {(1, 2), (1, 4), (1, 5), (2, 3),

(3, 4), (5, 3)}. Ребро (5, 3) — является ориентированным ребром или

дугой. Число ребер в графе определяется по значению локальных

степеней для каждой вершины:

р(1) = 3; р(2) = 2; р(3) = 3; р(4) = 2; р(5) = 2; р = (3 + 2 + 3 +

+ 2 + 2) / 2 = 6.

Важным в теории графов является понятие части графа G(E,U),

который обозначается G'(E',U') с G(E,U).

Множества вершин и ребер части графа являются

подмножествами вершин и ребер исходного графа Е'сЕ U' с U.

Многие задачи на графах состоят в определении частей графа с

заданными свойствами.

Часть графа G'(E',U') с G(E,U) называется подграфом графа

G(E,U), если Е' с Е , а подмножество U'cU образовано только

ребрами, инцидентными вершинам множества Е'.

Полным графом называется граф G(E,U), у которого каждая

вершина ее Е соединена ребрами с остальными вершинами (рис. 1.9).

Рис. 1.9. Полный граф

58

Связанность грофоВ

Маршрутом графа G называется последовательность ребер S =

= (и., и7, ... и ), в которой каждые два соседних ребра имеют общую

вершину, т.е. u,= (e,, e2); и2 = (е2, е3); ... un= (en, еп+1). Не исключено,

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

маршруте.

Две вершины е. и е. называются связанными, если существует мар-

шрут из е. в е..

Компонентой связности графа называется подмножество его

вершин с инцидентными им ребрами, такое, что любая вершина

связана с любой другой вершиной маршрута. Например, из графа на

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

показанные сплошной линией.

Рис. 1.10. Компоненты связанности графа

Простой цепью, или простым путем, называется маршрут, в

котором ни одно ребро ire повторяется дважды. Элементарной цепью или

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

вершина не повторяется дважды. Циклом в графе называется маршрут, у

которого начальная вершина совпадает с конечной. Например,

следующий граф имеет цикл S = (1, 2, 3, 5, 4, 1) (рис. 1.11).

59

Рис. 1.11. Цикл в графе

Цикл, проходящий по всем ребрам графа только один раз,

называется эйлеровым циклом. В теории графов доказывается теорема,

определяющая, содержит ли граф эйлеров цикл. Оказывается,

конечный граф содержит эйлеров цикл тогда и только тогда, когда он

связан, и все его локальные степени вершин четные. Важной

прикладной задачей теории графов является задача поиска в графе цикла,

проходящего через каждую вершину только один раз. Такие циклы

называются гамильтоновыми циклами.

Весьма важным является связанный граф, не имеющий циклов,

он называется деревом. В дереве любые две вершины связаны

единственным путем. Вершина называется концевой, если ей инцидентно

не более одного ребра; одна из концевых вершин может быть выбрана

в качестве корня.

ЗоЭоние графа

Граф может задаваться в виде рисунка, аналитически, в виде

матрицы. Выше приводилось задание графа в виде рисунка.

Аналитическое задание состоит в задании элементов множества вершин

Е = {ер е2, ... еп} и множества ребер U = {up u2, ... um}.

Для выполнения различного рода формальных преобразований

над фафами удобно использовать их матричные задания. Матрица А

размерностью пхп называется матрицей смежности графа G(E,U),

если ее элементы образованы по правилу: элемент матрицы а.= т,

если вершины ей е. соединены т ребрами, и а..= 0, если эти верши-

60

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

столбцов, равное количеству вершин графа.

Матрица А размерностью n x m называется матрицей

инцидентности графа G(E,U), если ее элементы образованы по правилу: элемент

матрицы Ь.. = 1, если вершина е. инцидентна ребру и. и Ь.. = 0 в

противном случае. Так как каждое ребро инцидентно двум вершинам, то

в каждой строке этой матрицы ровно два ненулевых элемента.

Построим матрицы смежности и инцидентности для графа,

изображенного на рис. 1.12.

Рис. 1.12. Пример графа

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

1

2

3

4

5

1

0

1

0

1

0

2

1

0

1

1

0

3

0

1

0

0

1

4

1

1

0

0

1

5

0

5

1

1

0

Матрица инцидентности будет состоять из пяти строк и шести

столбцов.

1

2

3

4

5

а

1

1

0

0

0

b

1

0

0

1

0

с

0

1

1

0

0

d

0

0

1

0

1

е

0

1

0

1

0

f

0

0

0

1

1

61

2. Технические средство реализации

информационный процессов

2.1. Представление информации

В технических устройствах

В основу любого устройства, предназначенного для

преобразования или хранения информации, должен быть положен принцип ее

представления, то есть ее физический носитель. Известны,

например, механические устройства, в которых информация

представляется углами поворота или перемещения объектов относительно друг

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

всегда являлась важной задачей для дальнейшего прогресса

промышленности и науки, предлагались устройства, принцип представления

информации в которых зависел от уровня развития техники:

механические устройства с ручным, а затем с паровым приводом,

электромеханические, электрические устройства и, наконец, электронные

устройства. Последние получили широкое распространение и за

30-40 лет вытеснили устройства других типов. Исключение

составляют случаи, когда преобразование информации требует наличия

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

механизмы памяти больших объемов, исполнительные механизмы и

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

электронных устройств обусловлено многими факторами, главными из

которых являются удобство преобразования и передачи

электрических сигналов, малая инерционность электронных устройств и,

следовательно, их высокое быстродействие.

Вычислительные устройства, использующие непрерывную

форму представления информации, называются аналоговыми

вычислительными машинами (АВМ). Вычислительные устройства,

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

вычислительными машинами (ЦВМ).

В настоящее время устройства, использующие непрерывный спо-

62

соб представления информации, вытесняются более

прогрессивными цифровыми устройствами, даже из таких традиционно

«аналоговых» областей, как телевидение и телефония. Что касается

непосредственно вычислительных систем, то их развитие, начавшееся

преимущественно с АВМ, постепенно перешло к ЦВМ и к середине

70-х гг. прошлого столетия ЦВМ полностью вытеснили АВМ.

В дальнейшем мы будем рассматривать только вычислительные

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

остановимся несколько подробнее на принципе построения и

полезных свойствах АВМ.

АВМ имели блочную структуру, т.е. представляли собой систему

связанных между собой базовых элементов. Связи между базовыми

элементами, их состав и количество изменялись для каждой задачи,

решаемой на АВМ. В качестве базового элемента использовался

операционный усилитель, схема которого показана на рис. 2.1.

Он состоит из усилителя, входных элементов (Е1, ..., Ея) и

элемента обратной связи (Еос). В качестве элементов используются

радиоэлектронные компоненты: резисторы, конденсаторы,

индуктивности. В зависимости от типов элементов, базовый элемент может

производить сложение, интегрирование, дифференцирование и

некоторые другие операции над входными напряжениями (UbxI, ...,

ивхя), результат операции снимается в виде выходного напряжения

(ивых). Основными достоинствами АВМ являлись простота

аппаратной реализации и высокая скорость получения решения. Основным

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

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

среды, изменяли свои параметры, что и влияло на точность решения.

63

ЦВМ имеют гораздо более высокую сложность аппаратной и

программной реализации. Информация в них имеет определенные

границы представления, т.е. точность представления информации

конечна. Для расширения границ представления необходимо

увеличивать аппаратную часть или увеличивать время обработки.

Основными достоинствами ЦВМ, а в дальнейшем — компьютерных систем

(КС) являются:

• гарантированная точность результата, зависящая только от

границ представления данных;

• универсальность — способность обрабатывать данные любыми

методами, представляемыми последовательностью простых

арифметических и логических операций;

• возможность реализации большого числа известных численных

математических методов решения задач.