- •1.Понятие множества. Виды множеств. Основное отношение между элементом и множеством. Способы задания множеств.
- •3.Объединение множеств. Пример. Дизъюнкция. Пересечение множеств. Пример. Конъюнкция. Тавтология. Противоречие.
- •4.Дополнение множества. Отрицание. Стрелка Пирса. Штрих Шеффера. Примеры.
- •5.Разность множеств. Импликация. Пример. Симметрическая разность. Эквивалентность. Пример.
- •6.Элементарные булевы функции. Методы доказательства в логике Буля.
- •8.Свойства операций над множествами, свойства элементарных булевых функций (доказать два свойства). Приоритет операций над множествами.
- •10.Многочлен Жегалкина. Теорема Жегалкина. Алгоритмы построения многочлена Жегалкина.
- •11.Линейные и нелинейные булевы функции. Алгоритм определения линейности (или нелинейности) булевой функции.
- •12.Определения: графа, ориентированного и неориентированного графов. Элементы графа и отношения между ними. Виды графов. Изоморфность графов.
- •13.Способы задания графа.
- •14.Определения: сети, пропускной способности дуги, потока по сети, источника и стока. Задача о величине максимального потока по сети и алгоритм её решения. Теорема Форда-Фалкерсона.
- •16.Деревья и их элементы. Остов. Теорема Кирхгофа. Цикломатическое число графа.
- •18.Алгоритмы поиска дерева минимального веса.
- •18.Нахождение кратчайшего пути между источником и стоком сети. Алгоритм Дейкстры.
16.Деревья и их элементы. Остов. Теорема Кирхгофа. Цикломатическое число графа.
Дерево -это связный ациклический граф (то есть граф, не содержащий циклов, между любой парой вершин которого существует ровно один путь) Пусть G — произвольный (n, m)-граф с k компонентами связности. Если G — не лес, то в нем (его компонентах связности) существуют циклы. Рассмотрим какой-либо цикл и удалим из него некоторое ребро. При этом количество компонент связности не увеличится. Если после этого еще останутся циклы, то рассмотрим следующий из них и снова удалим какое-либо его ребро. Продолжим этот процесс до тех пор, пока не исчезнут все циклы. Полученный в результате подграф, который, очевидно, является лесом и имеет столько же компонент связности, как и исходный граф G, называется остовом графа G. Матрица Кирхгофа — одно из представлений графа с помощью матрицы. Матрица Кирхгофа используется для подсчета остовных деревьев данного графа (матричная теорема о деревьях), а также используется в спектральной теории графов. Цикломатическое число графа — минимальное число ребер, которые надо удалить, чтобы граф стал ациклическим. Существует соотношение: p1(G) = p0(G) + | E(G) | − | V(G) | , где p1(G)— цикломатическое число, p0 — число компонент связности графа, | E(G) | — число рёбер, а | V(G) | — число вершин.
18.Алгоритмы поиска дерева минимального веса.
Алгоритм Прима — алгоритм построения минимального остовного дерева взвешенного связного неориентированного графа. Построение начинается с дерева, включающего в себя одну (произвольную) вершину. В течение работы алгоритма дерево разрастается, пока не охватит все вершины исходного графа. На каждом шаге алгоритма к текущему дереву присоединяется самое лёгкое из рёбер, соединяющих вершину из построенного дерева, и вершину не из дерева. Алгоритм Крускала (или алгоритм Краскала) — алгоритм построения минимального остовного дерева взвешенного связного неориентированного графа. Вначале текущее множество рёбер устанавливается пустым. Затем, пока это возможно, проводится следующая операция: из всех рёбер, добавление которых к уже имеющемуся множеству не вызовет появление в нём цикла, выбирается ребро минимального веса и добавляется к уже имеющемуся множеству. Когда таких рёбер больше нет, алгоритм завершён. Подграф данного графа, содержащий все его вершины и найденное множество рёбер, является его остовным деревом минимального веса
18.Нахождение кратчайшего пути между источником и стоком сети. Алгоритм Дейкстры.
Находит кратчайшее расстояние от одной из вершин графа до всех остальных. Алгоритм работает только для графов без рёбер отрицательного веса. Алгоритм широко применяется в программировании и технологиях, например, его использует протокол OSPF для устранения кольцевых маршрутов. Каждой вершине из V сопоставим метку — минимальное известное расстояние от этой вершины до a. Алгоритм работает пошагово — на каждом шаге он «посещает» одну вершину и пытается уменьшать метки. Работа алгоритма завершается, когда все вершины посещены.
Инициализация. Метка самой вершины a полагается равной 0, метки остальных вершин — бесконечности. Это отражает то, что расстояния от a до других вершин пока неизвестны. Все вершины графа помечаются как непосещённые.
Шаг алгоритма. Если все вершины посещены, алгоритм завершается. В противном случае, из ещё не посещённых вершин выбирается вершина u, имеющая минимальную метку. Мы рассматриваем всевозможные маршруты, в которых u является предпоследним пунктом. Вершины, в которые ведут рёбра из u, назовем соседями этой вершины. Для каждого соседа вершины u, кроме отмеченных как посещённые, рассмотрим новую длину пути, равную сумме значений текущей метки u и длины ребра, соединяющего u с этим соседом. Если полученное значение длины меньше значения метки соседа, заменим значение метки полученным значением длины. Рассмотрев всех соседей, пометим вершину u как посещенную и повторим шаг алгоритма.