Студопедия
Случайная страница | ТОМ-1 | ТОМ-2 | ТОМ-3
АрхитектураБиологияГеографияДругоеИностранные языки
ИнформатикаИсторияКультураЛитератураМатематика
МедицинаМеханикаОбразованиеОхрана трудаПедагогика
ПолитикаПравоПрограммированиеПсихологияРелигия
СоциологияСпортСтроительствоФизикаФилософия
ФинансыХимияЭкологияЭкономикаЭлектроника

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

A ∩ -A ≠ Ø A È -A ≠ U | Задача о гамильтоновом цикле состоит в выяснении, имеет ли заданный граф G гамильтонов цикл относится к NP-классу. | Критический путь и способ его нахождения. | Обоснование алгоритма Флойда. | Принцип построения когнитивной карты. | СДНФ приводим к минимальной ДНФ | Выводимости теоремы и ее отрицания. | Ориентированный мультиграф, называемый графом переходов или диаграммой переходов |


Читайте также:
  1. Глава 7 НЕРАВНЫЙ БОЙ
  2. КАКО ПОДОБАЕТ ОБРЯД С-ПРАВНЫЙ ЧИНИТЬ

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

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

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

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

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

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

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

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

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

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

Даны 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=|| aij || - размера n×n (n-число вершин)

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

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

 

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

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


Дата добавления: 2015-11-16; просмотров: 58 | Нарушение авторских прав


<== предыдущая страница | следующая страница ==>
Agrave;симметрия относительно вертикальной линии| Для ориентированного графа

mybiblioteka.su - 2015-2024 год. (0.009 сек.)