Лабораторная работа №4
ПРЕДСТАВЛЕНИЕ ГРАФОВ
Цель работы: Получение навыков программирования в MathCad на основе работы с графами.
Методические указания
Теоретические сведения приведены в параграфе 6.3.
Задание
Написать функцию, реализующую заданную операцию в MathCad. Варианты заданий приведены в таблице 10.3.
Таблица 10.3
|
Вариант |
Операция |
|
1 |
Преобразование матрицы смежности в матрицу инцидентности |
|
2 |
Преобразование матрицы смежности в список пар вершин |
|
3 |
Преобразование матрицы смежности в список списков графа |
|
4 |
Преобразование матрицы инцидентности в матрицу смежности |
|
5 |
Преобразование матрицы инцидентности в список пар вершин |
|
6 |
Преобразование матрицы инцидентности в список списков графа |
|
7 |
Преобразование списка пар вершин в матрицу смежности |
|
8 |
Преобразование списка пар вершин в матрицу инцидентности |
|
9 |
Преобразование списка пар вершин в список списков графа |
|
10 |
Преобразование списка списков графа в матрицу смежности |
|
11 |
Преобразование списка списков графа в матрицу инцидентности |
|
12 |
Преобразование списка списков графа в список пар вершин |
Задания на типовую работу
Дана булева функция F(X,Y,Z,T) = (001a4 a3a2a1a0 1010 1100), где a4a3a2a1a0 – двоичный код варианта.
1) Минимизировать F.
2) Определить FÎK0, FÎK1, FÎK*, fÎK<, FÎKL.
3) Определить ДF/ДX, ДF/ДY, дF/ДZ, ДF/ДT, дF/ДXдY, ДF/ДYдZ, дF/ДZдX, ДF/ДTдY, ДF / ДXдYдZ, ДF/ДXдYдT, дF/ДXдYдZдT
4) Минимизировать с использованием логических тождеств (равносильностей) функцию G(X,Y,Z) = ØF(X,Y,Z,Y)Å YÞØXÛF(X,Y,Z,X)
5) Минимизировать функцию g(x, y,z) c помощью диаграммы Вейча.
Дано множество A = {1, 3, 4, 6, N mod 8, N mod 2, N mod 5, (N+1) mod 10, (N+3) mod 8} и множество B = {2, 3, 5, 6, N mod 8, N mod 2, N mod 4, N mod 9, (N+2) mod 8}, где N – номер варианта. Универсальное множество принять AÈB. Замечание: если мощности получаемых множеств больше 10, то записать только три первых и два последних элемента.
1) Записать множества в нормальном виде (т. е. отсортированное и без повторений).
2) Определить мощности множеств.
3) Определить {1, 3, N mod 2}Í A.
4) Определить объединение, пересечение и разность множеств A и B.
5) Определить дополнения множеств A и B.
5) Определить 2A .
6) Определить мощности 2A и 2B.
7) Определить A´B.
8) Определить предикат PÍ A´B, A mod B = 0, AÎA, BÎB.
9) Отобразить предикат графически.
10) Составить любое отображение F, полученное из предиката P.
11) Отобразить F графически в виде точек.
12) Определить область значения и область определения отображения F.
Дано множество M = {0, 1, 2, …, 9}
1) Определить предикат RÍ M´M, (N + A) mod B = 0, AÎM, BÎM.
2) Показать, что R является (или не является) рефлективным, антирефлективным, симметричным, антисимметричным, транзитивным.
3) Получите из R отношение эквивалентности, отношение строгого и нестрогого порядка исключив некоторые элементы.
Пусть N = N, M = N – 4, где N – номер варианта.
Определить число перестановок из N, перестановок с повторениями из N, размещений M из N, размещений с повторениями M из N, сочетаний M из N, сочетаний с повторениями M из N.
Дан список пар вершин ориентированного графа:
E={(0, N mod 3),(N mod 3, N mod 4),(4,1),(N mod 2, N mod 5),(N mod 4, N mod 2), (N mod 5, N mod 4),(0, 2),(1, 3)}. (N = N + 5, N – номер варианта)
1) Устранить петли и кратные дуги.
2) Нарисовать граф, обозначить дуги (ребра) буквами.
3) Построить матрицу смежности графа.
4) Построить матрицу инцидентности графа.
5) Построить список списков вершин графа.
6) "Угадать" диаметр графа.
7) Определить число компонент сильной связности.
8) Получить неориентированный граф, заменив дуги ребрами в данном ориентированном графе.
9) Выполнить задания 2-6, 10-14 для полученного неориентированного графа.
10) Определить является ли граф гамильтоновым.
11) Определить является ли граф эйлеровым.
12) Определить связность, реберную связность и минимальную степень вершин графа. Сравнить эти значения.
| < Предыдущая | Следующая > |
|---|
