Теорема Понтрягина-Куратовского





Граф планарен тогда и только тогда, когда он не содержит подграфов, стягиваемых в

K5 или K3,3.

 

19 Алгоритмы отыскания кратчайших путей в графе. Минимальны остов.

Алгори́тм Де́йкстры

Каждой вершине из V сопоставим метку — минимальное известное расстояние от этой вершины до a. Алгоритм работает пошагово — на каждом шаге он «посещает» одну вершину и пытается уменьшать метки. Работа алгоритма завершается, когда все вершины посещены.

Инициализация. Метка самой вершины a полагается равной 0, метки остальных вершин — бесконечности. Это отражает то, что расстояния от a до других вершин пока неизвестны. Все вершины графа помечаются как непосещенные.

 

Шаг алгоритма. Если все вершины посещены, алгоритм завершается. В противном случае из ещё не посещенных вершин выбирается вершина u, имеющая минимальную метку. Мы рассматриваем всевозможные маршруты, в которых u является предпоследним пунктом. Вершины, соединенные с вершиной u ребрами, назовем соседями этой вершины. Для каждого соседа рассмотрим новую длину пути, равную сумме текущей метки u и длины ребра, соединяющего u с этим соседом. Если полученная длина меньше метки соседа, заменим метку этой длиной. Рассмотрев всех соседей, пометим вершину u как посещенную и повторим шаг.

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

 

11. Определение функционально полной системы функций. Основные примеры функционально полных систем. Определение. Система функций {f1 f2, ..., fn ...} из Р2 называется (функционально) полной, если любая булева функция может быть записана в виде формулы через функции этой системы. Рассмотрим примеры полных систем. 1. Система P2 — множество всех булевых функций — является полной системой. 2. Система бета = {x_отрицание, x1 & x2 , x1vx2) представляет пол­ную систему. Ясно, что не каждая система является полной, на-пример, система бета = {0, 1) не полная. Следующая тео­рема позволяет сводить вопрос о полноте одних систем к вопросу о полноте других систем. Теорема Пусть даны две системы функций из Р2: бета={f1 ,f2, ...} (I) омега={g1 ,g2, ...} (II) относительно которых известно, что система I полна и каждая ее функция выражается в виде формулы через функции системы II. Тогда система II является полной.   12. Многочлен Жегалкина. Методы вычисления многочлена Жегалкина для булевой функции. Определение Многочленами Жегалкина назваются формулы над множеством функций FJ={ 0, 1, *, +} (* - конъюнкция). Таким образом, каждый многочлен Жегалкина (возможно, после раскрытия скобок и "приведения" подобных членов) представляет сумму (по модулю 2) положительных (монотонных) элементарных конъюнкций (т.е. элементарных конъюнкций без отрицаний). Теорема . Для любой булевой функции существует задающий ее многочлен Жегалкина. Он единственен с точностью до перестановок слагаемых и порядка переменных в конъюнкциях. Полином Жегалкина это форма представления логической функции с помощью Функции Жегалкина (Исключающее ИЛИ). Для получения полинома Жегалкина следует выполнить следуюющие действия: Получить ДНФ функции Все ИЛИ заменить на Исключающее ИЛИ (+) Во всех термах заменить элементы с отрицанием на конструкцию: («элемент» «исключающее ИЛИ» 1) (x_отрицание = x+1) Раскрыть скобки по правилам алгебры Жегалкина и привести попарно одинаковые термы   13. Замкнутый класс функций. Основные замкнутые классы. Определение: Пусть Sum(CP2), мн-во ф-ций из P2 представимых формулами над sum назыв [sum]. Определение: Класс sum(CP2) наз функцион замкнутым, если sum=[sum]. Основные замкнутые классы: самодв, лин, монотон, сохран 0 и 1. 9.Метод Квайна – Мак-Клоски для нахождения минимальной ДНФ Формализация Мак-Клоски.   Каждой ЭК ставим в соответствие булев вектор. (x с отрицанием – 0, без отрицания – 1).   1. Выписываем все ЭК из СДНФ функции в формализованном виде в столбец, располагая их в порядке возрастания числа единиц в векторах и разбивая на классы по числу единиц. 2. Между ЭК проводим все возможные склеивания. Результат записываем в новый столбец справа, а ЭК, участвовавшие в склеивании, помечаем звездочкой. Склеивать можно только ЭК из соседних классов. 3. Для полученного столбца еще раз применяем шаг 2. 4. Все ЭК, которые остались непомеченными звездочкой, являются простыми импликантами. 5. Строим таблицу Квайна по следующему правилу: А) Каждой строке ставим в соответствие простую импликанту Пi. Б) Каждому столбцу – ЭК из СДНФ Kj. 6. Если Пi.покрывает Kj , то в соответствующей клетке ставим знак +. 7. Ищем ядровые импликанты (столбец, содержащий только 1 знак +). Та строка и есть ядровая (строка, в какой этот крестик содержится). 8. Строим сокращенную таблицу (Вычеркиваем ядровые строки, а затем – столбцы, где есть вычеркнутые крестики). 9. Ядро дополняем до тупиковой ДНФ (Ищем минимальную комбинацию строк так, чтобы в каждый столбец входил хотя бы один крестик). Дизъюнкция этих строк даст тупиковые ДНФ. Среди всех тупиковых ДНФ выбираем минимальную  

 


 

20-21-22 23 20 Паросочетание. Теорема Холла о совершенном паросочетании. Паросочетание — это множество ребер, не имеющих общих концов. Теорема Холла Для того, чтобы в двудольном графе существовало совершенное паросочетание, необходимо и достаточно, чтобы для любого подмножества S из множества V выполнялось условие [S] <= [γ(S)].   21 Алгоритм нахождения максимального паросочетания 1)Строим в двудольном графе произвольное паросочетание 2)Делаем наши паросочетания толстыми ребрами 3) Ищем тонкие цепи (Это те в которых тонких ребер на одно больше чем толстых) 4)Если нашли тонкую цепь меняем толстые и тонки ребра местами, если нет, то найденное паросочетание максимально   22 Зада об оптимальном назначении(алгоритм её решения) Есть m работников и m работ. Каждый из работников выполняет каждую работу с определенной эффективностью. Требуется распределить работы таким образом, чтобы каждый работник выполнял только одну работу, выполнялись все работы и суммарная эффективность была максимальна среди всех возможных таких распределений. A = (aij) – матрица эффективности. А(М*М)   А = В терминах матрицы эффективности задача состоит в нахождении М элементов, расположенных в разных строках и разных столбцах, чтобы их сумма была максимальной. Дан двудольный полный граф с V = M, W = M Даны длины ребер. Задача состоит в нахождении совершенного паросочетания, сумма длин всех ребер которого максимальна. Алгоритм. 1. Всем вершинам Vi даем метку аi = max по всем элементам нужной строки. По всем j присваиваем метку 0. 2. Ищем ребра, для которых выполняется условие Ai + Bj = Aij Строим граф, в который входит все вершины исходного графа и найденные ребра. 3. В построенном графе ищем максимальное паросочетание. Если найденное паросочетание совершенно, то алгоритм закончен. Если нет, то переходим дальше. 4. Из теоремы Холла существует подмножество S из V, [S] > ф(S). Ищем это подмножество. Для каждой вершины Vi из S метку Ai уменьшают на 1, а для wj из ф(s) метку Vj увеличивают на 1. 5. Переходим на начало шага 2 с новыми значениями меток.   Содержание: 1. Операции над множествами, их свойства. Аксиомы булевой алгебры. 2. Характеристические векторы подмножеств. (не будет) булевых векторов. 3. Элементарные булевы функции. Их выражение через основные. 4. ДНФ и СДНФ. Методы приведения булевой функции к СКНФ и СДНФ. 5. Минимальная ДНФ. Тривиальный алгоритм минимизации. 6. Определение интервала и максимального интервала булевой функции. 7. Геометрический метод минимизации булевой функции от трех переменных. 8. Метод Карно для минимизации булевых функций. 9. Метод Квайна для минимизации булевых функций. 10. Двойственная функция. Принцип двойственности. 11. Определение функционально полной системы функций. Основные примеры функционально полных систем. 12. Многочлен Жегалкина. Методы вычисления многочлена Жегалкина для булевой функции. 13. Замкнутый класс функций. Основные замкнутые классы. 14. Леммы о несамодвойственной, о монотонной и о нелинейной функциях. 15. Теорема Поста о функциональной полноте. 16. . Понятие графа. Маршруты, циклы, связность. Определение дерева, его свойства. 17. Понятие орграфа. Сумматор n-разрядных двоичных чисел. 18. Планарные графы. Теорема Понтрягина-Куратовского. (не будет) 19. Алгоритмы отыскания кратчайших путей в графе. Минимальны остов. 20. Паросочетание. Теорема Холла о совершенном паросочетании. 21. Алгоритм отыскания максимального паросочетания. 22. Задача об оптимальном назначении. Алгоритм её решения. 23. Транспортные сети и потоки. Алгоритм Форда-Фалкерсона.    

 


 

    23 Алгоритм нахождения максимального потока (Алгоритм Форда – Фалькерсона). 1. Берем любой поток в транспортной сети. 2. Строим граф перестроек g* по следующему правилу: В него входят все вершины исходного графа g. Те ребра, на которых значение функции потока в исходном графе g были равны 0, входят в новый граф без изменений со своими пропускными способностями. Все ребра, на которых ф(x) > 0 в новом графе g* заменяются двумя ребрами x* и x**. Ребро x* направлено в ту же сторону, что и x, и пропускная способность c(x*) = c(x) – ф(x). Ребро x** направлено в противоположную сторону ребру x, и пропускная способность c(x**) = ф(x). Ребра с нулевой пропускной способностью можно не рисовать. 3. В графе g* ищем путь из А в В по ребрам с ненулевой пропускной способностью. Если его нет, то имеющийся поток является максимальным и алгоритм закончен. Иначе переходим к пункту 4. (Этот путь называется увеличенной цепью. min(c(x)) – минимальное значение пропускной способности этой цепи). 4. Меняем значение функции потока в графе g для тех ребер, которые соответствуют найденному пути в графе перестроек по следующему правилу: Если направление ребра x в графе g совпадает с направлением пути, то новое ф(x) = ф(x) +  Если же направление противоположно направлению пути, то ф(x) = ф(x) -  5. Переходим на шаг 2 с новым потоком.  

 





Читайте также:
Что входит в перечень работ по подготовке дома к зиме: При подготовке дома к зиме проводят следующие мероприятия...
Восстановление элементов благоустройства после завершения земляных работ: Края асфальтового покрытия перед его восстановлением должны...
История государства Древнего Египта: Одним из основных аспектов изучения истории государств и права этих стран является...
Что такое филология и зачем ею занимаются?: Слово «филология» состоит из двух греческих корней...

Рекомендуемые страницы:


Поиск по сайту

©2015-2021 poisk-ru.ru
Все права принадлежать их авторам. Данный сайт не претендует на авторства, а предоставляет бесплатное использование.
Дата создания страницы: 2016-02-12 Нарушение авторских прав и Нарушение персональных данных


Поиск по сайту:

Обратная связь
0.017 с.