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

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

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

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

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

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

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

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

Отображение – «закон», по кот. каждому эл-ту обл. опред. став. в соотв. эл-т обл. знач.

Пусть даны два множ. 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^/ ₂,...), и наоборот.

Гомоморфизм — отображ. множ. эл-тов одной алгебр. системы в другую, сохр. все отношения и операции.

Даны 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 то соответсвие гомоморфно, нет в противном случае.

Мономорфизм — гомоморфное и инъективное соотв.

Эпиморфизм — гомоморфное и сюръективное соотв.

Эндоморфизм — гомоморфное соотв. и множ. В=А

Биморфизм — гомоморфное, биъективное соотв.

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

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

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