Тема 11. Частичные булевы функций
Тема 11. Частичные булевы функций Краткая теория Булева функция называется частичной, если она определена не на всем множестве
Примеры решения задач Задача. Минимизировать частичную булеву функцию Решение:
МДНФ: Аналогично можно проводить рассуждения и для метода Квайна и для метода карт Карно. В общем случае необходим полный перебор всех возможных дополнений.
Упражнения 1. Минимизировать различными методами частичную булеву функцию: a) b) c)
Дополнительные упражнения 2. Минимизировать методом карт Карно частичную булеву функцию:
a) b)
Тема 12. Различные способы задания графов. Операции над графами Краткая теория Граф Граф содержащий только ребра называется неориентированным графом (неограф), а граф содержащий только дуги – ориентированным графом (орграф). Операция над графами (без кратных ребер и петель): 1. Дополнением графа 2. Объединением графов 3. Пересечением графов 4. Соединением (сложением) графов 5. Удаление вершины 6. Удаление ребра
Примеры решения задач Задача. Для графически заданного графа найти матрицы смежности и инцидентности.
Решение: Матрица смежности графа
Матрица инцидентности графа
Упражнения 1. Для графа заданного матрицей смежности найти графическое задание и матрицу инцидентности:
2. Для графа заданного матрицей смежности найти графическое задание и матрицу инцидентности:
3. Выполните действия и найдите соответствующую матрицу смежности для графа a)
b) c) d) e) f) g) где матрицы смежности для графов
Тема 13. Минимальные деревья Краткая теория Деревом называется связный граф без циклов. Матрицей весов графа называется матрица смежности в ячейках которой стоят веса соответствующих ребер (дуг) и знак бесконечности в случае отсутствия соответствующего ребра. Минимальным деревом называется остовное дерево графа с минимальным суммарным весом ребер. Жадный алгоритм построения минимального дерева: На каждом шаге алгоритма берется ребро с минимальным весом, не образовывающее циклов в строящемся графе. Алгоритм ближайшего соседа построения минимального дерева: В качестве исходной берется любая вершина графа. После этого, среди всех ребер инцидентных данной вершине берется ребро с наименьшим весом и включается в строящееся дерево. В дальнейшем к строящемуся дереву добавляются ребра, не образовывающие цикла, инцидентные какой-либо его вершине. Алгоритм удаления максимальных циклических ребер: На каждом шаге алгоритма удаляется ребро с максимальным весом образующее цикл в модифицируемом графе.
Воспользуйтесь поиском по сайту: ![]() ©2015 - 2025 megalektsii.ru Все авторские права принадлежат авторам лекционных материалов. Обратная связь с нами...
|