Практическая работа №2 по МДК 01.02: Математический аппарат для построения компьютерных сетей наименование работы: Решение задач по теории графов. Построение матрицы достижимости.

Смоленский колледж телекоммуникаций
(филиал) федерального государственного бюджетного образовательного
учреждения высшего образования
«Санкт-Петербургский государственный университет телекоммуникаций
им. проф. М.А. Бонч-Бруевича»
















Практическая работа №2

по МДК 01.02: Математический аппарат для построения компьютерных сетей

наименование работы: Решение задач по теории графов. Построение матрицы достижимости.


для специальности: 09.02.02
работа рассчитана на 2 часа
составлена преподавателем: Скряго О.С.











Смоленск, 2016








1. Цель работы: получить практические навыки по построению матриц достижимости.
2. Литература:
2.1. Асанов, М. О. Дискретная математика: графы, матроиды, алгоритмы: Учебное пособие. 2-е изд. / М.О. Асанов , В.А.Баранский , В.В. Расин - СПб. : Издательство «Лань» 2012г. 368с. - ISBN 978-5-8114-1068-2
2.2. Мельников, О.И. Теория графов в занимательных задачах. Изд.4, испр. и доп./О.И. Мельников 2012. 240 с. М.: Книжный дом "Либриком" ISBN978-5-9775-0232-0
2. 3. Новиков, Ф.А. Дискретная математика: Учебник для вузов. 2-е изд. Стандарт третьего поколения: учебник / Ф.А. Новиков. - СПб. : Питер 2012, 400с.- ISBN 978-5-496-00015-4

3. Подготовка к работе:
3.1. Повторить тему «Основные понятия графа».
3.2. Подготовить бланк отчета (см.п.7).
3.3. Ответить на вопросы допуска:
3.3.1. Сформулируйте определения матрицы смежности?
3.3.2. Сформулируйте определение матрицы достижимости?
3.3.3. Сформулируйте определение графа ?
4. Основное оборудование:
4.1. не используется.
5. Задание:
1.1.Выполните задания согласно варианту. Составить матрицу достижимости двумя способами.


Вариант 1. Вариант 2.





Вариант 3. Вариант 4.
















Вариант 5. Вариант 6.



Вариант 7. Вариант 8.











Вариант 9. Вариант 10.














6. Порядок выполнения работы:
6.1. Ознакомиться с заданием.
6.2. Определить номер варианта (в соответствии с номером в журнале).
6.3. Выполнить задания в соответствии с вариантом.
6.4. Ответьте на контрольные вопросы.
7. Содержание отчёта:
7.1. Название и цель работы.
7.2 Ответы на вопросы допуска.
7.2. Указать номер варианта, привести условия заданий своего варианта.
7.3. Представить результат выполнения заданий.
7.4. Ответы на контрольные вопросы.
7.5. Вывод о проделанной работе.

8. Контрольные вопросы:
8.1. Сформулируйте определение матрицы инцидентности?
8.2. Сформулируйте определения маршрута графа?
8.3.Как представляется достижимость графически?
8.4.Какой граф называют изоморфным?
8.5. какой граф называют смешанным?

Составил преподаватель __________________________Скряго О.С.



Приложение
Важной задачей в теории графов является нахождение матрицы достижимости по матрице смежности. Можно доказать, что матрица достижимости может быть получена как итерация матрицы смежности:
[ Cкачайте файл, чтобы посмотреть картинку ]где элементами матриц являются нули и единицы, о операции соответствуют операциям идемпотентного полукольца [ Cкачайте файл, чтобы посмотреть картинку ]. В этом случае матрица [ Cкачайте файл, чтобы посмотреть картинку ] может быть получена при решении уравнения [ Cкачайте файл, чтобы посмотреть картинку ], так как оно эквивалентно уравнению[ Cкачайте файл, чтобы посмотреть картинку ], где [ Cкачайте файл, чтобы посмотреть картинку ] -- единичная матрица.
Таким образом, для получения матрицы [ Cкачайте файл, чтобы посмотреть картинку ] необходимо решить [ Cкачайте файл, чтобы посмотреть картинку ] систем уравнений следующего вида для [ Cкачайте файл, чтобы посмотреть картинку ]:
[ Cкачайте файл, чтобы посмотреть картинку ]где [ Cкачайте файл, чтобы посмотреть картинку ] - элементы матрицы смежности, а [ Cкачайте файл, чтобы посмотреть картинку ] -- элементы единичной матрицы. Решением каждой из систем будет [ Cкачайте файл, чтобы посмотреть картинку ]-й столбец матрицы [ Cкачайте файл, чтобы посмотреть картинку ].
[ Cкачайте файл, чтобы посмотреть картинку ]

Рисунок1. Ориентированный граф

Рассмотрим пример. На рисунке [ Cкачайте файл, чтобы посмотреть ссылку ] показан ориентированный граф из шести вершин, матрица смежности которого равна:
[ Cкачайте файл, чтобы посмотреть картинку ]
1-й столбец[ Cкачайте файл, чтобы посмотреть картинку ]


2-й столбец
[ Cкачайте файл, чтобы посмотреть картинку ]
3-6 столбцы
Вычисляются аналогично.
Полученная матрица достижимости примет вид:
[ Cкачайте файл, чтобы посмотреть картинку ]





















$ X = A \odot X$$ E$$ n$$ k = \overline{1, n}$\begin{displaymath}\left\{\begin{array}{l}x_1 = a_{1 1} \odot x_1 \oplus a_{......_{n n}\odot x_n \oplus \varepsilon_{n k}\end{array}\right.,\end{displaymath}$ a_{i j}$$\displaystyle A = \left(\begin{array}{cccccc}0 & 1 & 0 & 0 & 0 & 0\\0 & 0 & ......0 & 0 & 0\\0 & 1 & 0 & 1 & 0 & 0\\0 & 0 & 1 & 0 & 1 & 0\end{array}\right)$\begin{displaymath}\begin{array}{c}\left\{\begin{array}{l}x_1 = 1 \odot x_2...... x_4 = 0\\x_5 = 0\\x_6 = 0\end{array}\right.\end{array}\end{displaymath}HYPER15Основной шрифт абзаца

Приложенные файлы

  • doc 107
    Скряго О.С.
    Размер файла: 312 kB Загрузок: 4

Добавить комментарий