Кольцо

Определение 1. Непустое множество R называется кольцом, если в нем определены две алгебраические операции: сложение, ставящее в соответствие каждым двум элементам a, b элемент a + b, называемый их суммой, и умножение, ставящее в соответствие каждым двум элементам a, b элемент ab, называемый их произведением, причем эти операции обладают следующими свойствами:

I. (Коммутативность сложения) a + b = b + a;

II. (Ассоциативность сложения) a + (b + c) = (a + b) + c;

III. (Обратимость сложения) Для любых a и b из R уравнение a + x = b имеет (по крайней мере одно) решение, т. е. существует элемент такой, что a + c = b;

IV. (Коммутативность умножения) ab = ba;

Термин "кольцо" применяется также ко множествам с некоммутативным или даже неассоциативным умножением. Формулировки других свойств также меняются.

V. (Ассоциативность умножения) a(bc) = (ab)c;

VI. (Дистрибутивность умножения относительно сложения) (a + b)c = ac + bc.

Примеры колец. При обычных операциях сложения и умножения кольцом является:

1. Множество целых чисел.

2. Множество рациональных чисел.

3. Множество действительных чисел.

4. Множество рациональных чисел.

Поле.

Примеры колец, приведенные в разделе Кольца, показывают, что в отношении обратной операции для умножения (в отличии от сложения) различные кольца обладают совершенно различными свойствами. Так, в кольце целых чисел деление выполняется лишь в исключительных случаях, причем все элементы кольца делятся на +1 и -1. В кольце же рациональных чисел деление всегда возможно (кроме деления на 0). Желая изучить свойства обратной операции для умножения, приходим к важнейшему частному случаю кольца - полю.

Полем называется кольцо P, обладающее следующими свойствами:

VII. (Обратимость умножения) Для любых a и b из P, где a ≠ 0, уравнение ax = b имеет (по крайней мере одно) решение, т. е. существует элемент такой, что aq = b.

VIII. P содержит по крайней мере один элемент, отличный от нуля.

Примеры полей.

Из примеров 1-10 колец (Кольца) только 2, 3 и 4, т. е. рациональные, действительные и комплексные числа, являются полями. В примере 5 свойство VII выполнено, так как вообще нет элемента a ≠ 0, но не выполнено свойство VIII. В остальных примерах не выполняется свойство VII. Приведем еще следующие примеры полей.

1. Множество комплексных чисел a + bi с любыми рациональными a, b.

2. Множество действительных чисел вида с любыми рациональными a и b.

3. Множество всех рациональных функций с действительными коэффициентами от одного или нескольких переменных.

4. Множество из двух элементов, которые обозначим через 0 и 1, при следующем определении операций:

0 + 0 = 1 + 1 = 0, 0 + 1 = 1 + 0 = 1,

0 · 0 = 0 · 1 = 1 · 0 = 0, 1 · 1 = 1.

Все теоремы из раздела Кольца, выведенные для колец, остаются верными, в частности, для полей. Кроме того, из свойства VII вытекают теоремы, аналогичные тем, которые были приведены в разделе Кольца из свойства III.

17. Изоморфизм. Гомоморфизм.

ИЗОМОРФИЗМ и ГОМОМОРФИЗМ (греч. isos — одинаковый, homoios — подобный и morphe — форма) — понятия, характеризующие соответствие между структурами объектов. Две системы, рассматриваемые отвлеченно от природы составляющих их элементов, являются изоморфными друг другу, если каждому элементу первой системы соответствует лишь один элемент второй и каждой связи в одной системе соответствует связь в другой и обратно. Такое взаимооднозначное соответствие называется ИЗОМОРФИЗМ. Полный ИЗОМОРФИЗМ может быть лишь между абстрактными, идеализированными объектами, напр., соответствие между геометрической фигурой и ее аналитическим выражением в виде формулы. ИЗОМОРФИЗМ связан не со всеми, а лишь с некоторыми фиксированными в познавательном акте свойствами и отношениями сравниваемых объектов, которые в других своих отношениях могут отличаться. ГОМОМОРФИЗМ отличается от ИЗОМОРФИЗМА тем, что соответствие объектов (систем) однозначно лишь в одну сторону. Поэтому ГОМОФОРМНЫЙ образ есть неполное, приближенное отображение структуры оригинала. Таково, напр., отношение между картиной и местностью, между грамзаписью и ее оригиналом — звуковыми колебаниями воздушной среды. Понятия ИЗОМОРФИЗМ и ГОМОМОРФИЗМ широко применяются в математической логике и кибернетике (Филос. словарь).

Изоморфизм. Гомоморфизм.

Пусть множества X и Y представляют собой группы. Если между элементами этих групп установлено взаимо-однозначное соответствие, при котором для любых элементов a,b X и соответствующих элементов a’,b’ Y существует элемент c X при условии что a•b=c и существует элемент c’ Y при условии что a’•b’=c’, то такие группы называют изоморфными. Они могут отличаться друг от друга природой элементов и названием операций, но все свойства изоморфных групп одинаковы.

В гомоморфных группах соответствие между ними является односторонним. Говорят, что группа X голоморфно отображена в группу Y, если каждому элементу X соответствует строго определенный элемент группы Y, причем для a,b X имеется a•b=c и a’,b’ Y имеется a’•b’=c’. В общем случае при гомоморфизме в данный элемент Y могут переходить различные элементы группы X, а также может не быть вообще ни одного элемента.

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

Графом называется совокупность двух множеств: множества вершин и множества рёбер, находящихся между собой в некотором соотношении и обозна­чающиеся G(X,U), где множество Х – множество вершин, а U – множество рёбер. Множество рёбер можно разделить на три непересекающихся подмножества:

U₁∩U₂∩U₃=Æ,

Граф называется смешанным, если он содержит и рёбра и дуги. Если две вершины графа имеют общее ребро, то они называются смежными и любая вер­шина инцидентна этому ребру.

Два ребра называются смежными, если они имеют общую вершину. Ребро инцидентно каждой своей вершине.

19. Способы задания графа.

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

Пример:

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

Часть графа называется подграфом, если она образуется из графа, удале­нием части вершин и инцидентных им рёбер. Часть графа, образованная удале­нием нескольких ребёр из графа, называется суграфом.

Пример:

Граф G называется дополнением исходного графа до полного, если множе­ство его рёбер состоит из рёбер полного графа, не входящих в исходный граф.

Если граф G описан совокупностью вершин Х, а граф Н – совокупностью вершин V и между ними есть взаимооднозначное соответствие (Х~V) отношения эквивалентности, то эти графы изоморфны.

20. Отношения порядка и отношение эквивалентности на графе.

Отношения эквивалентности и порядка.

Рис. 3.31.

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

Введем оператор G, который указывает на связь вершины i с другими вершинами графа Г0. Будем различать две группы G-операторов: прямого Gn(i) действия и обратного G–n(i). Оператор G1(i) указывает на те вершины, в которые можно попасть непосредственно из вершины i; обратный оператор G–1(i) указывает на совокупность вершин, из которых можно попасть в вершину i. Степени G-операторов определяются обычным образом:

G0(i) = {i}, G2(i) = {G1(G1(i))}, G–2(i) = {G–1(G–1(i))},...

Непосредственно по рис. 3.30 находим результат действия G-оператора на вершины 1 и 2:

G0(1) = {1}; G–1(1) = {5, 14}; G1(1) = {6, 13};

G–2(1) = {3, 4, 13}; G2(1) = {7, 12, 14};

G0(2) = {2}; G2(2) = {11, 13, 15}; G–2(2) = {3, 15}

G3(1) = {8, 16, 10, 1}; G4(1) = {6, 13, 11, 8, 12, 9};

и т.д. Для всякой вершины i орграфа Г0 можно определить прямое G+(i) и обратное G–(i) транзитивные замыкания.

Они определяются через объединение всех степеней G-оператора, соответственно, положительных и отрицательных:

G+(i) = G0(i) È G1(i) È G2(i) È G3(i) È...

G–(i) = G0(i) È G–1(i) È G–2(i) È G–3(i) È...

Смысл прямого транзитивного замыкания G+(i) состоит в том, что оно указывает множество вершин орграфа Г0, в которые можно попасть из вершины i. Обратное транзитивное замыкание G–(i) указывает на те вершины Г0, из которых можно попасть в вершину i. В обоих случаях длина пути по числу дуг не ограничивается. Пересечение прямого и обратного замыканий определяет подграф сильно связанных вершин или класс эквивалентности вершины i:

C(i) = G+(i) Ç G–(i).

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

Для нашего конкретного орграфа Г0 имеем:

G+(1) = {1, 6, 7, 8, 9, 10, 11, 12, 13, 14, 16};

G–(1) = {1, 2, 3, 4, 5, 13, 14, 15}.

Следовательно, первый класс сильно связанных вершин образован тремя вершинами:

C1(1) = G+(1) Ç G–(1) = {1, 13, 14}.

Вершина 2 попадает во второй класс эквивалентности, где помимо представителя присутствует еще одна вершина — 15-ая:

G+(2) = {2, 11, 15}; G–(2) = {2, 3, 15}; C2(2) = {2, 15}.

Всего подобная процедура позволяет найти восемь непересекающихся классов эквивалентности. Перечислим их без указания вершин-представителей:

C1 = {1, 13, 14}; C2 = {2, 15}; C3 = {3}; C4 = {4, 5}; C5 = {6, 7, 9, 16}; C6 = {10, 12}; C7 = {8}; C8 = {11}.

21. Операции над графами.

1. Объединение графов:

G(X,U)=G₁(X₁, U₁)U G₂(X₂, U₂)

Множеством вершин графа G является объединение множеств вершин исходных графов: X=X₁UX₂.

Отображение для каждой вершины результирующего графа получают путём объединения отображений вершин в исходных графах:

Г_xi= Г_1хiU Г_2хi

Пример:

G=G₁UG₂

Х={х₁, х₂, х₃, х₄, х₅, х₆}U{ х₁, х₂, х₃, х₄}={х₁, х₂, х₃, х₄, х₅, х₆}

Г_x1={ х₂, х₄, х₆}

Г_x2={х₁,х₃,х₄,х₆}U{х₁,х₃}={х₁,х₃,х₄,х₆}

Г_x3={х₂,х₄}U{х₂,х₄}={х₂,х₄}

Г_x4={х₂,х₃,х₅,х₆}U{х₁,х₃}={х₁,х₂,х₃,х₅, х₆}

Г_x5={х₄,х₆}U{Æ}={х₄,х₆}

Г_x6={х₁,х₂,х₄,х₅}

Результирующий граф будет иметь вид:

1. Пересечение графов:

G(X,U)=G₁(X₁, U₁)∩G₂(X₂, U₂)

Результирующим графом является граф G, множеством вершин которого является результат пересечения множеств вершин исходных графов X=X₁∩X₂.

· Отображение для каждой вершины результирующего графа получают путём пересечения отображений вершин исходных графов:

Г_xi= Г_1хi∩Г_2хi

Пример:

G=G₁∩G₂

Х={х₁, х₂, х₃, х₄, х₅, х₆}∩{ х₁, х₂, х₃, х₄}={х₁, х₂, х₃, х₄}

Г_x1={х₂,х₆}∩{х₂,х₄}={х₂}

Г_x2={х₁,х₃,х₄,х₆}∩{х₁,х₃}= {х₁,х₆}

Г_x3={х₂,х₄}∩{х₂,х₄}={х₂,х₄}

Г_x4={х₂,х₃,х₅,х₆}∩{х₁,х₃}={х₃}

Результирующий граф будет иметь вид:

1. Разность графов:

G(X,U)=G₁(X₁, U₁)\G₂(X₂, U₂)

Множеством вершин графа G является множество вершин, в которое не входят вершины, общие для множеств вершин исходных графов: X=X₁\X₂.

Отображение для каждой вершины результирующего графа получают путём пересечения множества вершин этого графа и отображение той же вершины в графе G₁: Г_xi= Х∩ Г_1хi

Пример:

G=G₁UG₂

Х={х₁, х₂, х₃, х₄, х₅, х₆}U{ х₁, х₂, х₃, х₄}={х₅, х₆}

Г_x5={х₆}

Г_x6={х₅}

Результирующий граф будет иметь вид:

22. Типы графов.

23. Полный граф. Мультиграф. Связный граф. Гиперграф.

Полный граф — простой граф, в котором каждая пара различных вершин смежна. Полный граф с n вершинами имеет n(n − 1) / 2 рёбер и обозначается Kn. Является регулярным графом степени n − 1.

Графы с K1 по K4 являются планарными. Полные графы с большим количеством вершин не являются планарными, так как содержат подграф K5 и, следовательно, не удовлетворяют критерию Понтрягина-Куратовского.

Мультиграф — граф, в котором существует пара вершин, которая соединена более чем одним ребром (ненаправленным), либо более чем двумя дугами противоположных направлений.

Гипергра́ф — обобщённый вид графа, в котором каждым ребром могут соединяться не только две вершины, но и любые подмножества вершин.

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

Гиперграфы применяются, в частности, при моделировании электрических схем.

24. Разбиение графа.