- •Содержание:
- •Диаграммы Венна.
- •Операции над множествами.
- •Свойства теоретико-множественных операций.
- •Представление множеств в эвм
- •Реализация операций над подмножествами заданного универсума в эвм.
- •Многоместные отношения. Композиция отношений. Степень и ядро отношений.
- •Свойства отношений.
- •Представление отношений в эвм.
- •Минимальные элементы. Теорема о существовании минимального элемента.
- •Алгоритм топологической сортировки
- •Операции над бинарными отношениями.
- •Тема 4. Замыкание отношений. Транзитивное замыкание, рефлексивное замыкание. Алгоритм Уоршалла вычисления транзитивного замыкания. Замыкание отношений.
- •Транзитивное замыкание отношений
- •Рефлексивное замыкание отношений
- •Алгоритм Уоршалла.
- •Представление функций в эвм.
- •Операции
- •Свойства бинарных операций:
- •Способы задания операций.
- •Тема 6. Алгебраическая система. Гомоморфизмы. Проверка условия гомоморфизма. Изоморфизмы. Изоморфные алгебры. Изоморфизм модели. Примеры изоморфных алгебр. Алгебраическая система
- •Гомоморфизмы. Проверка условия гомоморфизма. Изоморфизмы. Изоморфные алгебры. Изоморфизм модели. Примеры изоморфных алгебр.
- •Основные характеристики нечетких множеств
- •Примеры нечетких множеств
- •Операции над нечеткими множествами
- •Графическое представление операций
- •Тема 8. Алгебраические операции над нечеткими множествами.
- •Тема 9. Основное определение графов. Смежность. Изоморфизм графов. Элементы графов. Подграфы. Валентность. Теорема Эйлера. Основное определение.
- •Смежность.
- •Изоморфизм графов.
- •Элементы графов. Подграфы. Валентность.
- •Теорема Эйлера.
- •Тема 10. Маршруты в графах. Цепи. Циклы. Расстояние между вершинами. Связность. Виды графов: тривиальные и полные графы, двудольные графы, орграфы и сети. Маршруты в графах. Цепи. Циклы.
- •Расстояние между вершинами.
- •Связность.
- •Виды графов: тривиальные и полные графы, двудольные графы, орграфы и сети.
- •Тема 11. Матрица смежности, матрица инцидентности. Операции над графами. Представление графов в эвм. Матрица смежности. Матрица инцедентности.
- •Операции над графами: Объединение графов.
- •Пересечение графов
- •Композиция графов
- •Декартово произведение графов.
- •Операция произведения графов.
- •Представление графов в эвм
- •V k1 k2
- •Теорема Форда - Фалкерсона. Алгоритм нахождения максимального потока.
- •Тема 14. Кратчайшие пути. Алгоритм Флойда. Алгоритм Дейкстры.
- •Кратчайшие пути
- •Рёбра отрицательного веса
- •Представление кратчайших путей в алгоритме
- •Алгоритм Флойда
- •Алгори́тм Де́йкстры
- •Сложность алгоритма
- •Ориентированные, упорядоченные и бинарные деревья
- •Представление в эвм свободных, ориентированных и упорядоченных деревьев.
- •Тема 16. Применение деревьев в программировании. Ассоциативная память. Выровненные деревья. Сбалансированные деревья. Минимальный каркас. Схема алгоритма построения минимального каркаса.
- •Применение деревьев в программировании. Ассоциативная память. Выровненные деревья. Сбалансированные деревья.
- •Минимальный каркас. Схема алгоритма построения минимальных каркасов.
- •Тема 17. Циклы и коциклы. Эйлеровы циклы. Гамильтоновы циклы. Теорема Дирака. Раскраска графов. Хроматическое число. Планарные графы. Укладка графов. Алгоритм раскрашивания.
- •21. Циклы и коциклы. Эйлеровы циклы. Гамильтоновы циклы. Теорема Дирака.
- •Раскраска графов. Хроматическое число. Планарность. Укладка графов. Алгоритмы раскрашивания.
- •F1(X) – нулевая функция.
- •Дизъюнктивная нормальная форма.
- •Конъюнктивная нормальная форма.
- •Тема 19. Неполностью определенные (частные) пф. Минимизация пф и неполностью определенных пф. Понятие минимизации булевых функций.
- •Метод неопределённых коэффициентов.
- •Метод карт Карно
- •Метод Петрика
- •Теорема Поста
- •Тема 22. Законы алгебры логики в офпс и их следствия. Правило выполнения совместных логических действий, правило склеивания, правило поглощения, правило развертывания.
- •Тема 23. Задача анализа и синтеза логических схем
- •Тема 24. Элементы теории алгоритмов. Цели и задачи теории алгоритмов. Формализация понятия алгоритмов: определение Колмогорова, определение Маркова
Представление графов в эвм
Наиболее распространены следующие 4 метода представления графов в ЭВМ:
Матрица смежности,
Матрица инцидентности,
Списки смежности вершин,
Списки смежности дуг.
Вы уже имеете представление о представлении графа матрицами смежности и инцидентности (Тема 11, пункт 1). Поясним суть списков смежности вершин.
Списки смежности вершин – представление графа с помощью списочной структуры, отражающей смежность вершин и состоящей из массива указателей на списки смежных вершин, где элемент списка представлен структурой.
Представление графа с помощью массива структур представляется в виде записей: .
Тема 12. Компоненты связности и объединение графов. Оценка числа ребер через число вершин и число компонентов связности. Вершинная и реберная связность. Мосты и блоки.
Объединение графов и компоненты связности. Оценка числа рёбер через число вершин и число компонентов связности. Вершинная и рёберная связность: мосты и блоки, меры связности.
Напомним, что если граф Gсостоит из одной компоненты связности, (то естьk(G) = 1), то он называетсясвязным.
В связном графе любые две вершины соединены (простой) цепью.
Теорема:Граф связен тогда и только тогда, когда его нельзя представить в виде объединения двух графов.
Рассмотрим граф:
V k1 k2
Замечание: Несвязный граф можно всегда представить как объединение связных компонент. Эти компоненты можно рассматривать независимо.
Вершина графа называется точкой сочленения,если ее удаление увеличивает число компонент связности.
В любом нетривиальном графе есть, по крайней мере, две вершины, которые не являются точками сочленения.
Теорема: Пусть р – число вершин,q– число ребер,k– число компонент связности графа. Тогда (p-k) ≤q≤ (p-k)(p-k+1) / 2.
Следствие:Еслиq> (p-1)(p-2) / 2 , то граф связен.
Мостомназывается ребро, удаление которого увеличивает число компонент связности.
Рассмотрим рисунок:
w c d
a
b e f
u,v– точки сочленения, х – ребро-мост,awb,buw,awub,cdv,evf– блоки.
Блокомназывается связный граф, не имеющий точек сочленения.
Если в графе есть мост, то есть и точка сочленения. Концы всякого моста кроме висячих вершин являются точкой сочленения, но не всякая точка сочленения является концом моста.
Вершинной связностьюграфаG(обозначаетсяx(G)) называется наименьшее число вершин, удаление которых приводит к несвязному или тривиальному графу.
Пример:
æ(G) = 0, еслиGнесвязен;
æ(G) =1, еслиGимеет точку сочленения;
Граф Gназываетсяk-связным,если æ(G) =k.
Реберной связностьюграфаG(обозначаетсяA(G)) называется наименьшее число ребер, удаление которых приводит к несвязному или тривиальному графу.
Пример:
λ(G) = 0, еслиGнесвязен;
λ(G) = 1, если G имеет мост;
λ(Кр) = р-1, значит, граф Кр – полный.
Тема 13. Потоки в сетях. Определение потока. Разрезы. Пример сети с потоками. Теорема Форда и Фалкерсона. Алгоритм нахождения максимального потока.
Потоки в сетях. Примеры практических задач, определение потока, разрезы.
Рассмотрим некоторые примеры практических задач.
Пример:
1) Пусть имеется сеть трубопроводов, соединяющих пункт А (скажем, нефтепромысел) с пунктом В (скажем, нефтеперерабатывающим заводом). Трубопроводы могут соединяться и разветвляться в промежуточных пунктах. Количество нефти, которое может быть перекачено по каждому отрезку трубопровода в единицу времени, также не безгранично и определяется такими факторами, как диаметр трубы, мощность нагнетающего насоса и т. д. (обычно это называют «пропускной способностью» или «максимальным расходом» трубопровода). Сколько нефти можно прокачать через такую сеть в единицу времени?
2) Пусть имеется система машин для производства готовых изделий из сырья, и последовательность технологических операций может быть различной (то есть операции могут выполняться на разном оборудовании или в разной последовательности), но все допустимые варианты заранее строго определены. Максимальная производительность каждой единицы оборудования, естественно, также заранее известна и постоянна. Какова максимально возможная производительность всей системы в целом и как нужно организовать производство для достижения максимальной производительности?
Определения:
Пусть G(V,Е) – сеть, сетью называется граф, имеющий вершины.Sиt– соответственно источник и сток сети. Дуги сети нагружены неотрицательными вещественными числами ЕR+ . Еслиuиv– вершины, то числос(u,v) – называется пропускной способностью дуги (u,v).
При решении будем полагать, что C(2,1)=C(1,2).
Максимальное количество Xijвещества, которое может пропустить в единицу времени ребро между вершиной (i,j) называют его пропускной способностью.
В общем случае Xij≠Xji. Пропускные способности рёбер сети можно задать квадратной матрицейn-го порядка, гдеn– число вершин сети. В теории потоков предполагается, чтоXii=0. И поэтому главная диагональ матрицы состоит из нулей.
-
||Cij|| =
1 2 3 4 5 6
0 6 1 0 0 0
6 0 2 0 3 0
1 2 0 3 0 0
0 0 3 0 1 2
0 3 0 1 0 5
0 0 0 2 5 0
Сформируем начальный поток 0, состоящий из суммы потоков по
следующим путям, и найдем пропускные способности путей:
1 = (1, 3, 4, 6), (1 ) = 1;
2 = (1, 2, 3, 4, 6), (2 ) = 2;
3 = (1, 2, 5, 6), (3 ) = 3.
Т.e. пропускная способность потока0 равна:
0 = (1 )+(2 )+(3 ) = 6
Величина потока каждого ребра выглядят так :
(e13) = 1;
(e12) = 4;
(e23) = 1;
(e34) = 2;
(e46) = 2;
(e25) = 3;
(e56) = 3.
Составим теперь матрицу построенного потока ( M2 ) c эле- ментами (eij):
1 2 3 4 5 6
0 4 1 0 0 0
-4 0 1 0 3 0
-1 -1 0 2 0 0
0 0 -2 0 0 2
0 -3 0 0 0 3
0 0 0 -2 -3 0
Далее строим матрицу М3 = М1 - М2 = { C(eij) - (eij) }:
1 2 3 4 5 6
0 2 0 0 0 0
10 0 1 0 0 0
2 3 0 1 0 0
0 0 5 0 1 0
0 6 0 1 0 2
0 0 0 4 8 0
В соответствии с данным алгоритмом составляем максимальный поток:
1)Построим начальный поток.
2)Составляем по ненасыщенному пути А={1,2,3,4,5,6},где 1Iи
6S,в сответствии с п.2 алгоритма построения по теореме Форда-Фалкерсона,сток попал в количество ребер по ненасыщенному пути.
3)Выделим путь из истока в сток состоящий из ненасыщенных ребер 4=(1,2,3,4,5,6).
Потом высчитываем Сij-Xij:C12-X12=6-4=2,C23-X23=2-1=1,
C34-X34=3-2=1,∆45=1,∆56=2.
Min(Cij-Xij)=1,увеличиваем на единицу построенный поток и возвращаемся к п.2(4)=1.
П.2 строим множество по ненасыщенным ребрам А={1,2}
Построим разрез minпропускной способности. Этот разрез будет иметь вид (A\B)=1+2+3=6.
Построим разрез транспортной сети. Он будет пересекать дуги, начало которых принадлежит множеству А,а конец мно-жеству В.
Считаем пропускную способность разреза:
R(A\B)=1+2+3=6.
Таким образом, согласно теореме Форда- Фалкерсона построен
Максимальный поток, равный минимальной пропускной способности pазреза сети.