Материал: Методические указания к выполнению лабораторных работ по дисциплине «Дискретная математика» для студентов направления подготовки бакалавров. Собенина О.В., Пак А.А
ПРАКТИЧЕСКАЯ ЧАСТЬ
Задания
1.Написать программу, позволяющую осуществлять переход от матрицы смежности к матрице инциденций для ориентированного графа.
2.Написать программу, позволяющую осуществлять переход от матрицы смежности к матрице инциденций для неориентированного графа.
3.Написать программу, позволяющую строить простой граф с заданной последовательностью степеней, если он существует.
4.Написать программу, позволяющую для произвольного графа определять количество путей заданной длины из каждой вершины в каждую.
5.Написать процедуру для определения, является ли данный граф связным.
6.Написать программу, позволяющую находить сильные компоненты связного графа.
7.Написать программу, позволяющую получать матрицы достижимости и контрдостижимости для произвольного графа.
8.Написать программу, реализующую алгоритм опреде-
|
ления уровней графа без контуров. |
|
||
9. |
Написать |
программу, которая для |
заданных графов |
|
|
G1 (X1,U1) |
и |
G2 (X2,U2) строит |
объединение этих |
|
графов. |
|
|
|
10. |
Написать |
программу, которая для |
заданных графов |
|
|
G1 (X1,U1) |
и |
G2 (X2,U2) строит пересечение этих гра- |
|
|
фов. |
|
|
|
11.Написать программу, которая переводит матрицу смежности в список ребер и список инцидентности для ориентированного графа
29
12.Написать программу, которая переводит матрицу инцидентности в список ребер и список инцидентности для неориентированного графа.
Порядок выполнения работы
1.Получить задание у преподавателя.
2.Разработать алгоритм решения задачи.
3.Реализовать полученный алгоритм.
4.Проанализировать результаты работы алгоритма.
5.Оформить отчет по лабораторной работе.
Содержание отчета
1.Номер и тема лабораторной работы.
2.Цель выполнения работы.
3.Схема алгоритма.
4.Исходные данные и результаты вычислений.
5.Анализ полученных результатов и вывод по работе.
Контрольные вопросы
1.С помощью какой структуры данных можно представить список инцидентности?
2.Как представить список ребер ?
3.Какой способ представления графов является лучшим в смысле экономии памяти?
4.Какой способ представления графов является худшим в смысле экономии памяти?
5.Чем отличается матрица смежности неориентированного графа от матрицы смежности ориентированного ?
6.Как в матрице смежности представить информацию о кратных ребрах?
7.Как в матрице инцидентности представит информацию о петлях?
30
8.Как получить матрицу пересечения графов по матрицам смежности исходных графов?
9.Как получить матрицу объединения графов по матрицам смежности исходных графов?
10.Как получить матрицу пересечения графов по матрицам инцидентности исходных графов?
11.Как получит матрицу объединения графов по матрицам инцидентности графов?
12.Как с помощью матрицы смежности построит матрицу достижимостей?
Лабораторная работа № 4
ПРОГРАММНАЯ РЕАЛИЗАЦИЯ ПРОЦЕДУРЫ СОСТАВЛЕНИЯ СКНФ И СДНФ ДЛЯ ПФ
Цель работы: изучение специальных разложений формул переключательных функций (ПФ), нормальных и совершенных нормальных форм. Получение практических навыков программной реализации алгоритмических процедур.
Программное средство: среда разработки приложений MS Visual Studio, языки программирования С#, C++.
Теоретические сведения
Покажем, что для каждой ПФ существует ей равносильная специального вида. Пусть v есть 0 или 1. Введем обозначе-
ние X1v x1,v 1x1,v 0
Заметим, что |
ПФ X1v 1 тогда и только тогда, когда |
X1 v, то есть vv |
1. |
31
Следовательно, ПФ X1v1 X2v2 ... Xnvn на наборе
(v1,v2,...,vn) принимает значение 1, а на любом другом – зна-
чение 0. Аналогично ПФ X1v1 X2v2 ... Xnvn принимает зна-
чение 0 только на наборе (v1 ,v2 ,..., vn ), а на всех остальных
наборах – 1.
Теорема 1. Для любой ПФ имеет место равносильность
F(X1,X2,...,Xn ) X1 F(1, X2,...,Xn ) X1F(0, X2,...,Xn ),
называемая дизъюнктивным разложением по переменной Х1.
Пример.
Для ПФ (Х1→ Х2 ^Х3) определить дизъюнктивное разложение по переменной Х1.
X1 X2 X3 X1 (1 X2 X3) X1 (0 X2 X3)X1 X2 X3 X1.
Следствие. Для любой ПФ F(X1,X2,...,Xn) и любо- |
|
||||||||||||
го натурального k имеет место равносильность |
|
|
|||||||||||
F(X |
1 |
, X |
2 |
,...,X |
n |
) |
|
|
Xv1 |
Xv2 |
... X vk |
|
|
|
|
|
|
(v ,v |
,...,v |
k |
) 1 |
2 |
k |
|
|||
|
|
|
|
|
|
|
1 2 |
|
|
|
|
|
|
F(v1,...,vk ,Xk 1,...,Xn) ,
называемая дизъюнктивным разложением F(X1,X2,...,Xn)
по переменным X1,X2,...,Xn .
Теорема 2. Для любой ПФ имеет место равносильность
F(X1,X2,...,Xn) (X1 F(0,X2,...,Xn))
(X1 F(1,X2,...,Xn))
называемая конъюнктивным разложением по переменной Х1.
32
Пример. Для ПФ
определить конъюнктивное разложение по переменной Х1.
X1 X2 X3 (X1 (0 X2 X3)) (X1 (1 X2X3) X1 (X2 X3))
Следствие. Для любой ПФ |
|
F(X1,X2,...,Xn) и любого |
|||||||||||||
натурального k имеет место равносильность |
|
|
|
||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
... |
|
|
|
F(X |
,X |
2 |
,...,X |
n |
) |
|
) |
( |
Xv1 |
|
Xv2 |
Xvk |
|||
1 |
|
|
|
(v ,v |
,...,v |
1 |
2 |
|
k |
||||||
|
|
|
|
|
|
1 2 |
k |
|
|
|
|
|
|
|
|
F(v1,...,vk ,Xk 1,...,Xn)), |
|
|
|
|
|
F(X1,X2,...,Xn) |
|||||||||
называемая конъюнктивным разложением |
|||||||||||||||
по переменным X1,X2,...,Xn .
Таким образом, для любой ПФ существует равносильная
ей, содержащая только константы 0 и 1, символы , , и пе-
ременные.
Определим некоторые канонические представления ПФ.
ПФ называется элементарной конъюнкцией (дизъюнкци-
ей), если она является конъюнкцией (дизъюнкцией) переменных и отрицаний переменных.
Пример.
X Y Z - элементарная конъюнкция.
X Z - элементарная дизъюнкция.
Говорят, что ПФ задана в дизъюнктивной нормальной форме (ДНФ), если она является дизъюнкцией элементарных конъюнкций.
Пример. X Y Z X Y Y Z - ДНФ.
33