- •Содержание:
- •Диаграммы Венна.
- •Операции над множествами.
- •Свойства теоретико-множественных операций.
- •Представление множеств в эвм
- •Реализация операций над подмножествами заданного универсума в эвм.
- •Многоместные отношения. Композиция отношений. Степень и ядро отношений.
- •Свойства отношений.
- •Представление отношений в эвм.
- •Минимальные элементы. Теорема о существовании минимального элемента.
- •Алгоритм топологической сортировки
- •Операции над бинарными отношениями.
- •Тема 4. Замыкание отношений. Транзитивное замыкание, рефлексивное замыкание. Алгоритм Уоршалла вычисления транзитивного замыкания. Замыкание отношений.
- •Транзитивное замыкание отношений
- •Рефлексивное замыкание отношений
- •Алгоритм Уоршалла.
- •Представление функций в эвм.
- •Операции
- •Свойства бинарных операций:
- •Способы задания операций.
- •Тема 6. Алгебраическая система. Гомоморфизмы. Проверка условия гомоморфизма. Изоморфизмы. Изоморфные алгебры. Изоморфизм модели. Примеры изоморфных алгебр. Алгебраическая система
- •Гомоморфизмы. Проверка условия гомоморфизма. Изоморфизмы. Изоморфные алгебры. Изоморфизм модели. Примеры изоморфных алгебр.
- •Основные характеристики нечетких множеств
- •Примеры нечетких множеств
- •Операции над нечеткими множествами
- •Графическое представление операций
- •Тема 8. Алгебраические операции над нечеткими множествами.
- •Тема 9. Основное определение графов. Смежность. Изоморфизм графов. Элементы графов. Подграфы. Валентность. Теорема Эйлера. Основное определение.
- •Смежность.
- •Изоморфизм графов.
- •Элементы графов. Подграфы. Валентность.
- •Теорема Эйлера.
- •Тема 10. Маршруты в графах. Цепи. Циклы. Расстояние между вершинами. Связность. Виды графов: тривиальные и полные графы, двудольные графы, орграфы и сети. Маршруты в графах. Цепи. Циклы.
- •Расстояние между вершинами.
- •Связность.
- •Виды графов: тривиальные и полные графы, двудольные графы, орграфы и сети.
- •Тема 11. Матрица смежности, матрица инцидентности. Операции над графами. Представление графов в эвм. Матрица смежности. Матрица инцедентности.
- •Операции над графами: Объединение графов.
- •Пересечение графов
- •Композиция графов
- •Декартово произведение графов.
- •Операция произведения графов.
- •Представление графов в эвм
- •V k1 k2
- •Теорема Форда - Фалкерсона. Алгоритм нахождения максимального потока.
- •Тема 14. Кратчайшие пути. Алгоритм Флойда. Алгоритм Дейкстры.
- •Кратчайшие пути
- •Рёбра отрицательного веса
- •Представление кратчайших путей в алгоритме
- •Алгоритм Флойда
- •Алгори́тм Де́йкстры
- •Сложность алгоритма
- •Ориентированные, упорядоченные и бинарные деревья
- •Представление в эвм свободных, ориентированных и упорядоченных деревьев.
- •Тема 16. Применение деревьев в программировании. Ассоциативная память. Выровненные деревья. Сбалансированные деревья. Минимальный каркас. Схема алгоритма построения минимального каркаса.
- •Применение деревьев в программировании. Ассоциативная память. Выровненные деревья. Сбалансированные деревья.
- •Минимальный каркас. Схема алгоритма построения минимальных каркасов.
- •Тема 17. Циклы и коциклы. Эйлеровы циклы. Гамильтоновы циклы. Теорема Дирака. Раскраска графов. Хроматическое число. Планарные графы. Укладка графов. Алгоритм раскрашивания.
- •21. Циклы и коциклы. Эйлеровы циклы. Гамильтоновы циклы. Теорема Дирака.
- •Раскраска графов. Хроматическое число. Планарность. Укладка графов. Алгоритмы раскрашивания.
- •F1(X) – нулевая функция.
- •Дизъюнктивная нормальная форма.
- •Конъюнктивная нормальная форма.
- •Тема 19. Неполностью определенные (частные) пф. Минимизация пф и неполностью определенных пф. Понятие минимизации булевых функций.
- •Метод неопределённых коэффициентов.
- •Метод карт Карно
- •Метод Петрика
- •Теорема Поста
- •Тема 22. Законы алгебры логики в офпс и их следствия. Правило выполнения совместных логических действий, правило склеивания, правило поглощения, правило развертывания.
- •Тема 23. Задача анализа и синтеза логических схем
- •Тема 24. Элементы теории алгоритмов. Цели и задачи теории алгоритмов. Формализация понятия алгоритмов: определение Колмогорова, определение Маркова
Элементы графов. Подграфы. Валентность.
После рассмотрения определений, относящихся к графам как к цельным объектам, естественно дать определения различным составным элементам графов.
Определение 9.6. ГрафG'(V', Е')называетсяподграфомграфаG(V, Е)(обозначаетсяG'),еслиV' включено в Vи/илиЕ'включено в Е.
Определение 9.7. ЕслиV'=V,тоG'называетсяостовным подграфом G.
Определение 9.8. ЕслиV' включено в V и Е' включено в Е (причемV' не равноV иE' не равноE),то графG'называетсясобственным подграфом графаG.
Определение 9.9. ПодграфG'(V',Е')называетсяправильнымподграфом графаG(V,Е),еслиG'содержит все возможные ребраG. Правильный подграфG'(V, Е')графаG(V, Е)определяется подмножеством вершинV'.
Определение 9.10. Количество ребер, инцидентных вершинеv, называетсястепенью(иливалентностью вершиныv) и обозначаетсяd(v).
Причем 0d(v)1d(v) = |Г(v)|.
Обозначим минимальнуюстепень вершины графаGчерез(G),амаксимальную —через(G).
Определение 9.11. Если степени всех вершин равныk, то граф называетсярегулярнымстепениk:
Степень регулярности является инвариантом графа и обозначается r(G).Для нерегулярных графовr(G) не определено.
Пример: Ниже приведена диаграмма регулярного графа степени 3
Если степень вершины равна 0, то вершина называется изолированной.Если степень вершины равна 1, то вершина называетсяконцевой,иливисячей.
Для орграфа число дуг, исходящих из вершины v, называетсяполустепенъю исхода,а входящих –полустепенью захода.Обозначаются эти числа, соответственно,d–(v) иd+(v).
Теорема Эйлера.
Теорема Эйлера: Сумма степеней вершин графа равна удвоенному количеству ребер: .
Для ориентированного графа: .
Доказательство: При подсчете суммы степеней вершин каждое ребро учитывается два раза для одного конца ребра и для другого.
Тема 10. Маршруты в графах. Цепи. Циклы. Расстояние между вершинами. Связность. Виды графов: тривиальные и полные графы, двудольные графы, орграфы и сети. Маршруты в графах. Цепи. Циклы.
Определение 10.1.Маршрут – чередующаяся последовательность вершин и ребер, в которой любые два соседних элемента инцидентны.
1=v0e1v1e2v2e3…ekvk
Определение 10.2.Еслиv0 =vk, то маршрут называют цепью.
Определение 10.3.Если все вершины, а значит и ребра, различны, то маршрут называют простой цепью.
В этой цепи вершины v0иvk называют концами цепи. Говорят, что цепь с концамиu,vсоединяет вершиныu,v. Она обозначается <u,v>. Замкнутая цепь называется циклом. Замкнутая простая цепь называется простым циклом. Число циклов в графеGобозначаетсяz(G). Граф без циклов называют ацикличным. Для орграфов цепь называется путем, а цикл – контуром.
Пример:
v1v3v1v4– маршрут,
v1v3v5v2v3v4– цепь,
v1v4v3v2v5– простая цепь,
v1v3v5v2v3v4v1– цикл,
v1v3v4v1– простой цикл.
Длиной маршрута называется количество ребер (с повторениями).
Если маршрут =v0e1v1e2v2e3…ekvk, то длина маршрута равнаk, ||=k,k– число ребер.
Расстояние между вершинами.
Определение 10.4.Расстояние между вершинамиuиvобозначаетсяd(u,v), называется длина кратчайшей цепиu,v. А сама кратчайшая цепьd(u,v) =min|<u,v>| называется геодезической.
Если между вершинами u,vне существует цепи, то <u,v>d(u,v) = + ∞.
Пример:
d(v1,v2) = + ∞.
Диаметром графа GобозначаетсяD(G), называется длина длиннейшей геодезической, или наибольшей из кратчайших путей.
Множество вершин, находящихся на расстоянии nот вершиныv(т.е.D(v,n) = {uUd(u,v) =n}