Аддитивная и мультипликативная операции коммутативны

a+b = b+a, ab=ba

5) Мультипликативная операция дистрибутивна относительно аддитивной справа и слева. a (b + c) = (ab) + (a c), (b + c) a = (b a) + (c a)

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

ТЕЛО::::::::::::::::::::::::::::
__Тело это кольцо, для которого в случае изъятия 0, выполнены условия

1) $ е для мультипликативной операции а е = е а = а

2) $ а^# для мультипликативной операции а а^# = a^# a = e

3) Мультипликативная операция коммутативна ab=ba

__Теорема. Кольцо является телом тогда и только тогда, когда оно содержит не менее двух элементов и оба уравнения ax = b и xa = b, разрешимы для любых элементов a, b Î A, где a ¹ 0.

22. Решетка как универсальная алгебра. Решетка как частично упорядоченное множество. Мажоранта, максимальный элемент, наименьшая верхняя (точная верхняя) грань множества Sup. Миноранта, минимальный элемент, наибольшая нижняя (точная нижняя) грань множества Inf. Связь двух определений решеток.

РЕШЕТ КАК УНИВЕРСАЛ АЛГЕБ::::

__Решетка - алгебра с двумя бинарными операциями +, ⊗ удовлетворяющая следующим тождествам

1) _идемпотентность, a + a = a, a ⊗ a = a

2)_Коммутативностьa + b = b + a, a ⊗ b = b ⊗ a 3)_Ассоциативнос (a + b) + c = a +(b + c), (a ⊗ b) ⊗ c = a ⊗ (b ⊗ c)

4)_Поглощение (a ⊗ a) + b = a, (a + a) ⊗ b = a

РЕШ КАК ЧАСТИЧ УПОР МН_ВО::::

__Решетка — частично упорядоченное множество, в котором каждое двухэлементное подмножество имеет как точную верхнюю (sup), так и точную нижнюю (inf) грани.

МАЖОРАНТА,,…….:::::

__Элемент а из А есть мажоранта множества В, если элемент

a есть последующий или равный элемент для всех b из B.

___Если мажоранта Î B, то она максимумом множества B.

___Если множество мажорант имеет минимум, то он единственен и его называют наименьшей верхней гранью Sup B.

МИНОРАНТА,…..,…..:::::

___Элемент а из А есть миноранта множества В, если элемент

a есть предшествующий или равный элемент для всех b из B.

__Если миноранта Î B, то она минимум множества B.

___Если множество минорант имеет максимум, то он единственен и его называют наибольшей нижней гранью Inf B.

СВЯЗЬ ДВУХ ОПРЕД РЕШЕТКИ::::

_ Решетка - алгебра с двумя бинарными операциями "+", "*" удовлетворяющая определенным тождествам

__Решетка — частично упорядоченное множество, в котором каждое двухэлементное подмножество имеет как точную верхнюю (sup), так и точную нижнюю (inf) грани

__Связь между двумя определениями решетки: a + b = sup { a, b }, a * b = inf { a, b }

23. Отображения. Изоморфизм. Автоморфизм. Гомоморфизм. Эпиморфизм. Эндоморфизм. Мономорфизм. Биморфизм.

ГОМОМОРФИЗМ::::

__ГОМОМОРФИЗМ – отображение множества элементов одной алгебраической системы в другую, сохраняющее все отношения и операции

Даны A=<M1; φ>, B=<M2;ψ> и соответствие G отображает M1® M2.

Соответствие G - гомоморфизм алгебры А в алгебру В если

G (а φ b) = G(а) ψ G(b)

1) Над элементами а и b Î M1 выполняем операцию φ: a φ b = c

2) Результат операции с отображаем в множество M2: Г: с ®γ

3) Выполняет отображение элемента a в множество M2: Г: a ®α

4) Выполняет отображение элемента b в множество M2: Г: b ®β

5) Над элементами α и β Î M2 выполняем операциюψ: α ψ β = γ1

6) Если γ= γ1 то соответсвие гомоморфно, нет в противном случае.

__Мономорфизм – это гомоморфное и инъективное соответствие

__Эпиморфизм – это гомоморфное и сюръективное соответствие

__Эндоморфизм – это гомоморфное соответствие и множество В=А

__Биморфизм – это гомоморфное, биъективное соответствие

__Автоморфизм - это гомоморфное, взаимооднозначное соответствие и множество В=А

__Изоморфизм - это гомоморфное и взаимооднозначное соответствие

ОТОБРАЖЕНИЯ:::::::::::::

Отображение – полностью определенное функциональное

__(((((Отображением A в B (F:A→B) называется полностью определенное и функциональное соответствие

___Отображением A на B (F:A→B) называется полностью определенное, сюръективное и функциональное соответствие

__))))))))))))))))))))))))))

Пусть даны два множества S и S^/, причем в первом S определены отношения F_k (x ₁, x ₂,...), k = 1, 2,..., n, а во втором S^/ –отношения F^/_k (x^/ ₁, x^/ ₂,...), k = 1, 2,..., n. Множества S и S^/ с указанными отношениями называются изоморфными, если между ними существует такое взаимно однозначное соответствие x^/ =Г1(x), x = Г2(x^/), где x Î S, а x^/ Î S^/, что из наличия F_k (x ₁, x ₂,...) вытекает наличие F^/_k (x^/ ₁, x^/ ₂,...), и наоборот.

Отображение Г1 - изоморфное отображение или изоморфизмом системы S на систему S^/, а обратное ему отображение

Г2 – изоморфизмом системы S^/, на систему S.

Факт изоморфности систем S и S^/ обозначается S@S ^/.

24. Граф. Вершина, ребро, дуга. Кратные ребра (дуги). Петли. Смежные вершины, смежные дуги. Степень вершины. Инцидентные ребро(дуга) и вершина. Виды графов: плоские, неориентированные, ориентированные, смешанные, взвешенные, псевдограф, мультиграф, полный, пустой, двудольный, регулярный, деревья. Изоморфизм графов.

__ Граф (от греческого grajw — пишу) — множество V вершин и набор E неупорядоченных и упорядоченных пар вершин; обычно граф обозначают как G (V, E)

__Неупорядоченная пара вершин называется ребром, упорядоченная пара вершин— дуга.

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

Вершина — точка, в кот. сходятся ребра (дуги) графа.

Петля – ребро(дуга) соединяющее

одну вершину

Кратные ребра (дуги) – соединяют одну и ту жепару вершин (с учетом

направлений для дуг)

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

__Ребра, имеющие общую вершину называются смежными.

__Ребро (или дуга) и любая из его вершин называются инцидентными.

__Принято говорить, что ребро (u, v) соединяет вершины u и v, а дуга (u, v) начинается в вершине u и кончается в вершине v.

__Степень вершины – кол-во инцидентных с ней дуг.

ПЛОСКИЕ ГРАФЫ:::::::

__Доказано, что в 3-мерном пространстве любой граф можно представить в виде укладки таким образом, что линии, соответствующие ребрам (дугам) не будут пересекаться во внутренних точках. Для 2-мерного пространства это, вообще говоря, неверно.

· __ Плоские графы допускают представление в виде укладки в 2-мерном пространстве, с непересекающимися ребрами (дугами).

РИСУНОК(Л-4(29))

· Неориентированный граф содержит только ребра.

РИС(Л-4(30))

· Ориентированный граф содержит только дуги.

РИС(Л-4(30))

· Смешанный граф содержит ребра и дуги

РИС(Л-4(30))

· Взвешенный граф – это граф, в котором ребра (дуги) характеризуются весами

РИС(Л-4(30))

· Псевдограф содержит петли

РИС(Л-4(31))

· Мультиграф содержит кратные ребра

а - полный граф: любые две вершины соединены ребром (дугой)

б — пустой граф: не содержит ребер (дуг)

· Двудольный граф – множество вершин можно разбить на два

· подмножества, таких, что ребра соединяют вершины только из разных подмножеств.(л4(32))

· __Регулярный граф – это граф у которого степени всех вершин равны.

· дерево: граф не содержащий циклов

ИЗОМОРФИЗМ ГРАФОВ::::

__Два графа G (V, E) и H (W, I) называются изоморфными, если существует взаимно-однозначное соответствие между множествами вершин V, W и множествами ребер E, I, сохраняющее отношение инцидентности.

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

МАТРИЦА СМЕЖНОСТИ:

__Матрица смежности A=|| a_ij || - размера n×n (n-число вершин)

__ a_ij равен числу ребер, соединяющих вершины vi и vj (для неориентированного графа). Матрица симметричная.

___a_ij равен числу дуг идущих из вершины vi в вершину vj (для ориентированного графа)

МАТРИЦА ИДЕНПОТЕНТНОСТИ::::

__Матрица инциденций B =|| b _ij ||, размера n×m (n - вершины, m – ребра(дуги),

Дата добавления: 2015-11-16