Алгебраические системы. Алгебра множеств и булева алгебра.

В современных информационных системах существует большое разнообразие типов данных и различных действий, которые необходимо с ними производить. При этом каждый раз необходимо быть уверенным, что, выполняя какие-то действия на множестве данных определенного типа, мы не зайдем в тупик и не получим абсурдный результат. Но если свойства наших данных и операций (отношений) над ними укладываются в некую известную структуру, мы можем заранее определить, какие действия можно выполнять в рамках такой структуры, чтобы не попасть в подобную ситуацию. Вот для этого и используется такое понятие как алгебраическая система или просто алгебра. Такая абстрактная система состоит из двух множеств: множества данных, которое называют носителем алгебры, и множества отношений на этих данных. Обозначают ее так: A=áM,Sñ. Любую бинарную операцию a o b, где a,b ÎA, можно рассматривать как однородное бинарное отношение. Такое отношение является функцией. Если " a,b ÎA результат некоторой операции c = a o b, с ÎA, то говорят, что A замкнуто относительно этой операции, что обозначается как A´A®A. В дискретных алгебраических системах обычно подразумевается замкнутость носителя M относительно операций из множества S. Если в системе A=áM,Sñ все отношения из S являются операциями (функциями), то такую систему, называют просто алгеброй, если нет, то моделью или реляционной алгеброй. Рассмотрим множество всех подмножеств множества A (включая само множество и пустое множество Æ), то есть булеан B(A). Результаты всех основных операций над множествами (объединение, пересечение и образование дополнения) будут принадлежать B(A). То есть можно сказать, что B(A) замкнуто относительно этих операций. Поэтому система áА,B(A),Ç,È,\ñ называется алгеброй множеств.

Разновидности алгебр определяются частично характеристиками их носителей, но в большей степени свойствами операций. Обозначают абстрактную операцию белым кружком о. Для рассмотрения свойств понадобятся две операции, ведем еще значок · для второй операции. Итак, пусть a,b,c – элементы множества-носителя, то есть a,b,cÎM. Операции {о, ·} ÎS, M´M®M. В алгебраических системах чаще всего рассматриваются следующие свойства операций.

1. Ассоциативность: (a o b) o c = a o (b o c).

2. Коммутативность: a o b = b o a.

3. Дистрибутивность слева: a · (b o c) = (a · b) o (a · c).

4. Дистрибутивность справа: (a o b) · c = (a · c) o (b · c).

5. Поглощение: (a o b) · a = a.

6. Идемпотентность: a o a = a.

Самым простым видом алгебры является полугруппа – алгебра с одной ассоциативной бинарной операцией. Полугруппами являются формальные (машинные) языки. Носителем полугруппы является допустимое множество символов A (алфавит языка), а бинарной операцией – операция конкатенации (сцепления) символов. Если в полугруппе существует единица, то есть такой элемент e, что " a ÎA e×a = a×e = a, то это моноид. Чтобы получить моноид из такой полугруппы, как формальный язык, достаточно добавить в алфавит этого языка пустой символ.Моноид с обратным элементом, то есть при выполнении условия " a ÎA $ a ^-1 | a×a ^-1= e, называется группой. В группе можно однозначно решить уравнение вида a×x = b: решение имеет вид x=b × a ^-1.В группе имеют место следующие свойства операций.

1. (a o b)^-1 = b^-1 o a^-1.

2. a o b = a o c Þ b=c.

3. b o a = c o a Þ b=c.

4. (a^-1)^-1= a.

Коммутативная группа, то есть группа, в которой операция a o b коммутативна, называется абелевой. В абелевых группах операция обозначается Å или просто +, элемент, обратный к a, обозначается – a, а единица называется нулем. Операция + не обязательно арифметическое сложение. Хотя, например, множество всех целых чисел образует группу относительно сложения. Но множество положительных рациональных чисел образует группу относительно умножения. Алгебраические системы с двумя операциями это уже так называемые линейные системы. Две операции – это умножение и сложение в обобщенном смысле.Для каждой из этих операций можно ввести свой единичный элемент. Один из этих единичных элементов будет называться нулем, другой – единицей. К линейным системам относятся кольцо и поле.

Кольцо – это алгебраическая система, которая является абелевой группой хотя бы по одной операции. Как уже говорилось, эту операцию условно определяют как «сложение» - Å. Для второй операции требуется только ассоциативность. То есть кольцо – это полугруппа по умножению Ä. Умножение в кольце обладает свойством дистрибутивности слева и справа относительно сложения. Если умножение обладает еще и свойством коммутативности, то это уже коммутативное кольцо. А если это коммутативное кольцо еще и с единицей (то есть моноид по умножению), то его прямо так и называют – кольцо с единицей. Примером коммутативного кольца с единицей является машинная арифметика целых чисел (тип integer).

Если алгебраическая система является абелевой группой относительно обеих операций Å, Ä, и умножение дистрибутивно относительно сложения, то получаем поле. Наиболее известный пример – поле действительных чисел: áR,+,×ñ. Заметим, что множество рациональных чисел с теми же операциями тоже является полем и, следовательно, подалгеброй для áR,+,×ñ. Можете проверить, что двоичная арифметика с одноразрядным сложением по модулю два и конъюнкцией в качестве операции умножения тоже является полем. Для многих компьютерных приложений наиболее важной алгеброй с двумя операциями является булева алгебра. Носителем такой алгебры является множество, которое называют решеткой. Решетка – это множество с двумя операциями: сложением и умножением. Сложение здесь обозначают È, умножение Ç. Единичный элемент для операции сложения - нуль, единичный элемент для операции умножения - единица. Свойства операций сложения и умножения в решетке: идемпотентность, коммутативность, ассоциативность, поглощение. Решетка является абелевой группой. Если для пары операций в решетке выполняется дистрибутивность, то решетка называется дистрибутивной. Ограниченная решетка имеет верхнюю и нижнюю грани, причем нижняя грань - это нуль, а верхняя – единица. Далее, если в ограниченной решетке " a существует элемент a ^/ |, a È a ^/=1 & a Ç a ^/=0, который называется дополнением, то такая решетка называется ограниченной решеткой с дополнением. Из самого определения решетки через свойства операций мы имеем первые четыре свойства булевой алгебры. Из дистрибутивности решетки следует пятое свойство булевой алгебры – дистрибутивность. Из свойства ограниченности и свойства дополнения следуют законы нуля и единицы. То есть получается, что булева алгебра – это дистрибутивная ограниченная решетка с дополнением. Из взаимосвязи законов логики и свойств операций над множествами нетрудно понять, что ранее введенная алгебра множеств – это тоже булева алгебра. Единице здесь соответствует множество A, нулю – пустое множество.

 

 

12.Определение графа. Ориентированные и неориентированные графы. Мультиграфы, полные и регулярные графы. Способы представления графов в ЭВМ. Методы анализа (обхода) графов.

Формальное определение графа. Графом G назовем пару множеств G={V,E}, где V – множество вершин (vertex), E – множество связей между этими вершинами – ребер (edge).

Можно сказать, что граф представляет собой однородное отношение на множестве V´V. Поэтому ребра обозначают упорядоченной парой вершин e_ij=(v _i, v _j).

Если E=Æ, то такой граф называют нуль-графом. Если |V|=1, то граф называют тривиальным.

Смежность и инцидентность. Говорят чтовершина v инцидентна ребру e, если она является его концевой точкой. Соответственно, в этом случае говорят, что ребро e инцидентно вершине v. То есть понятие инцидентности для пары «вершина – ребро» симметрично.

Две вершины графа смежны, если они инцидентны одному и тому же ребру.

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

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

Ориентированный граф – граф, в котором все ребра имеют ориентацию. Будем обозначать этот граф G_d. В ориентированном графе (v _i, v _j)¹(v _j, v _i). Если граф не содержит ориентированных ребер, его называют неориентированным. Если в графе есть и ориентированные, и неориентированные ребра, то его называют смешанным.

Степенью или валентностью вершины v называют число ребер, инцидентных этой вершине. Степень вершины обозначают r(v). Если граф ориентированный, то число входящих в него дуг называют полустепенью захода r⁺(v), а число исходящих – полустепенью исхода r^-(v). Тогда степень вершины r(v)= r⁺(v)+ r^-(v).

Введем обозначения для числа вершин и числа ребер в графе: p =| V |, q =| E |. Величины p и q являются основными числовыми характеристиками графа или, по-научному говоря, его основными инвариантами.

Теорема Эйлера о степенях вершин. Сумма степеней всех вершин графа равна удвоенному числу его ребер:

Доказательство: когда мы суммируем степени двух смежных (соединенных ребром) вершин, мы учитываем это ребро и в первой, и во второй сумме. Если граф ориентированный, то мы учитывает ребро один раз как исходящее, второй раз – как входящее. То есть в сумме всех степеней вершин каждое ребро учитывается дважды. Отсюда и вытекает данное соотношение.

Из этой теоремы есть следствие: в любом графе число вершин нечетной степени четно.

Для доказательства разделим сумму всех степеней вершин на две части: сумму четных степеней и сумму нечетных степеней.

Общая сумма, как следует из исходного соотношения, четна. Следовательно, обе суммы в правой части должны быть либо одновременно четны, либо одновременно нечетны. Поскольку в первой сумме все входящие в нее слагаемые четны, она тоже будет четной. То есть вторая сумма тоже должна быть четной. А поскольку в ней все слагаемые нечетны, это возможно только в одном случае – когда четно само количество слагаемых, то есть количество вершин нечетной степени.

Введем еще два вида графов, связанных с понятием степени вершины.

Граф, у которого все степени вершин одинаковы и равны n, называется регулярным степени n. Будем обозначать такой граф R_p,n. Величина n называется степенью регулярности графа.

Граф, у которого все вершины соединены ребрами, называется полным и обозначается K_p. Полный граф является регулярным графом степени n-1.

Плоским или планарным называется граф, который можно разложить на плоскости без пересечения ребер.

Граф K5.

Граф R6,3.

Рис.3.2. Примеры неплоских графов.

Примерами неплоских графов могут служить графы K₅ и R_6,3 (рис.3.2).

 

Представление графов в ЭВМ.

Поскольку граф является однородным бинарным отношением на множестве V², то его естественней всего представить в виде бинарной матрицы размерности | V |´| V |= p ´ p, так же, как мы уже представляли отношения. Матрицу можно обозначить, например, A _E, чтобы подчеркнуть ее непосредственную связь с множеством E. В этой матрице a _ij=1, если существует ребро e _ij=(v _i, v _j) и a _ij=0 если такового нет. Такую матрицу называют матрицей смежности или, иначе, матрицей непосредственной достижимости. Для ориентированного графа a _ij¹ a _ji, для неориентированного графа матрица будет симметричной относительно диагонали.

По диагонали в матрице смежности принято ставить 0 или какой-нибудь «пустой» символ. Хотя можно сказать, что вершина «смежна сама с собой», но под смежностью подразумевается именно наличие ребра. Единица на диагонали может возникнуть, если граф имеет петлю. Но такой граф, как уже говорилось, обычно называют псевдографом.

Представление графа матрицей смежности удобно, когда каждую пару вершин соединяет только одно ребро. А что же делать с мультиграфами, такими, как мы видели, например, в задаче о семи мостах? Можно, конечно, ввести весовые коэффициенты в соответствии с числом ребер, но это уже будет не бинарная матрица, что для некоторых задач весьма существенно. В таком случае можно использовать матрицу инциденций. Размерность такой матрицы | V |´| E |= p ´ q, то есть индексами по столбцу будут, как и раньше, номера вершин, а индексами по строке будут номера ребер. Обозначим эту матрицу B _E. Тогда b _ij=1, если ребро j инцидентно вершине i, и b _ij=0 в противном случае. Для представления графа матрицей инциденций ребра придется предварительно занумеровать.

В матрице B _E сумма элементов по i –й строке есть степень i-й вершины. То же самое справедливо для матрицы A _E, если граф неориентированный. Но если граф ориентированный, то сумма элементов матрицы A _E по i-й строке - это только полустепень исхода r ^-(v _i). Полустепень же захода r ⁺(v _i) есть сумма элементов по i-му столбцу. То есть полная степень вершины r (v _i) в случае ориентированного графа есть сумма элементов по строке плюс сумма элементов по столбцу.

Таким образом, для подсчета инвариантов и других численных характеристик бинарные матрицы очень удобны. Однако это не самое экономное и иногда не самое удобное представление. Для задач обхода, например, удобнее так называемый список смежности или, иначе, список ссылок. В списке смежности каждому номеру вершины сопоставляется список номеров смежных с ней вершин (или ссылок на эти вершины). Каждому ребру соответствует один элемент этого списка. Так можно представлять и мультиграфы, в этом случае одно и то же число в списке повторится несколько раз. Если же мы имеем дело с ориентированным мультиграфом, то список ссылок – единственно возможный способ представления без введения каких-то дополнительных условных обозначений.

Максимальный объем памяти, занимаемой таким списком, не превосходит 2 q.

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

Рис.3.3. Ориентированный мультиграф.

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

 

 

1. Представление матрицей смежности.

2. Представление графа списком дуг: (1,6),(2,1),(3,2),(3,4),(3,5),(4,6),(5,3),(6,1),(6,5).

3. Представление матрицей инциденций. Номера дугам присвоены в соответствии с их положением в списке 2. Чтобы отразить ориентацию, инцидентной вершине в данном случае будем считать только исходящую дугу.

4. Представление графа списком смежности: 1) 6; 2) 1; 3) 2,4,5; 4) 6; 5) 3; 6) 1,5.

Методы обхода (просмотра) вершин графов.

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

В качестве примера возьмем граф на 10 вершинах, заданный следующим списком смежности: 1) 3,4,9; 2) 4,5,7; 3) 1,7; 4) 1,2,6,10; 5) 2,6; 6) 4,5,7,8; 7) 2,3,6,8; 8) 6,7,10; 9) 1,10; 10) 4,8,9.

Начинаем обход графа всегда с первой по номеру вершины. В процессе прохода будем составлять список S просмотренных вершин.

Поиск в глубину.

Шаг 0. Включаем в список просмотренных вершин первую вершину, поскольку мы в ней находимся: S={1}.

Шаг 1. Берем из списка смежности последней просмотренной вершины первую, в которой еще не были, и включаем ее в список. Если все вершины включены в список, конец. Если не все вершины просмотрены, а в списке смежности последней просмотренной вершины не просмотренных нет, переходим к шагу 2.

Шаг 2. Возвращаемся назад через те вершины, по которым пришли в последнюю, пока в списке смежности очередной вершины не нашлась еще не просмотренная. Если нашлась, включаем ее в список S и переходим к шагу 1.

Для нашего примера поиск в глубину будет выглядеть так.

Выполняем шаг 1, пока это возможно: S={1, 3, 7, 2, 5, 6, 4, 10, 9}.

Из вершины 9 перейти никуда нельзя, поскольку все вершины из ее списка смежности уже просмотрены. Поэтому переходим к шагу 2, то есть возвращаемся в вершину 10. Из вершины 10 переходим в не просмотренную вершину 8. Имеем S={1, 3, 7, 2, 5, 6, 4, 10, 9, 8}. Процесс просмотра завершен.

Поиск в ширину.

Шаг 0. Включаем в список просмотренных первую вершину, поскольку мы в ней находимся: S={1}.

Шаг 1. Берем все не просмотренные вершины, смежные с последней включенной, и добавляем их в список: S={1, 3, 4, 9}.

Шаг 2. Для каждой вершины, включенной на предыдущем шаге, включаем в список все не включенные вершины из ее списка смежности.

Повторяем шаг 2, пока все вершины не будут включены в список.

Для нашего примера после первого выполнения шага 2 имеем: S={1, 3, 4, 9, 7, 2, 6, 10}. Поскольку остались не просмотренными вершины 5 и 8, повторяем шаг 2. В результате имеем: S={1, 3, 4, 9, 7, 2, 6, 10, 8, 5}.

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