Методические указания. Протокол выполнения алгоритма для n = 3. i Р

ПРЕДСТАВЛЕНИЕ ГРАФОВ

Лабораторная работа №4

End proc

End while

return q

Пример

Протокол выполнения алгоритма для n = 3.

i	Р	В

Задание

1. Реализовать алгоритм (на любом языке программирования), описанный в теоретическом материале (номер варианта соответствует номеру алгоритма).

2. Получить результаты работы алгоритма для четырех видов различных исходных данных.

Цель работы: Получение навыков программирования в MathCad на основе работы с графами.

Теоретические сведения приведены в параграфе 6.3.

Задание

Написать функцию, реализующую заданную операцию в MathCad. Варианты заданий приведены в таблице 10.3.

Таблица 10.3

Вариант	Операция
	Преобразование матрицы смежности в матрицу инцидентности
	Преобразование матрицы смежности в список пар вершин
	Преобразование матрицы смежности в список списков графа
	Преобразование матрицы инцидентности в матрицу смежности
	Преобразование матрицы инцидентности в список пар вершин
	Преобразование матрицы инцидентности в список списков графа
	Преобразование списка пар вершин в матрицу смежности
	Преобразование списка пар вершин в матрицу инцидентности
	Преобразование списка пар вершин в список списков графа
	Преобразование списка списков графа в матрицу смежности
	Преобразование списка списков графа в матрицу инцидентности
	Преобразование списка списков графа в список пар вершин

Задания на типовую работу

Дана булева функция f (x, y, z, t) = (001a₄ a₃a₂a₁a₀ 1010 1100), где a₄a₃a₂a₁a₀ – двоичный код варианта.

1) Минимизировать f.

2) Определить f Î K ₀, f Î K ₁, f Î K _*, fÎ K _<, f Î K_L.

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) Определить 2 ^A .

6) Определить мощности 2 ^A и 2 ^B.

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) Определить связность, реберную связность и минимальную степень вершин графа. Сравнить эти значения.

Литература

1. Горбатов В.А. Основы дискретной математики. – М.: Высшая школа, 1986.

2. Горбатов В.А. Фундаментальные основы дискретной математики. – М.: Наука, 2000. – 544с.

3. Иванов Б.Н. Дискретная математика. Алгоритмы и программы: Учеб.пособие. – М: Лаборатория Базовых Знаний, 2001 – 288с.

4. Кузнецов О.П. Дискретная математика для инженеров М. 1960

5. Новиков Ф.А. Дискретная математика для программистов – СПб.: Питер, 2002. – 304 с.

6. Яблонский С.В. Введение в дискретную математику. – М.: Наука, 1979.

Дата добавления: 2014-12-27