Тема: ПРЕДСТАВЛЕНИЕ РЕЗУЛЬТАТОВ МОДЕЛИРОВАНИЯ. РАБОТА С ГРАФАМИ

ПРАКТИЧЕСКАЯ РАБОТА № 15

Тема: ПРЕДСТАВЛЕНИЕ РЕЗУЛЬТАТОВ МОДЕЛИРОВАНИЯ. РАБОТА С ГРАФАМИ

Цель выполнения практической работы: Приобрести практические навыки по решению алгоритмических задач, связанных с анализом графов, а так же по использованию графов, деревьев, списков при описании объектов и процессов окружающего мира.

Теоретическая часть

Для того, чтобы получить информационную модель любого реального объекта или процесса, необходимо рассмотреть его с системной точки зрения. Объект моделирования рассматривается в качестве системы. Наиболее часто используемой формой описания информационной модели являются таблицы и графы, отображающие структуру системы, взаимосвязи между ее элементами.

Граф - это множество точек или вершин и множество линий или ребер, соединяющих между собой все или часть этих точек. Граф является информационной моделью некоторого объекта или системы объектов.

Неориентированный граф - это граф , в котором нет направления линий.

Направленные ациклические графы широко используются в приложениях: в компиляторах, в искусственном интеллекте, в статистике и машинном обучении.

Дерево — это связный ациклический граф.  Связность означает наличие путей между любой парой вершин, ацикличность — отсутствие циклов и то, что между парами вершин имеется только по одному пути.

Лес — упорядоченное множество упорядоченных деревьев.

Ориентированное (направленное) дерево — ацикличный орграф (ориентированный граф, не содержащий циклов), в котором только одна вершина имеет нулевую степень захода (в неё не ведут дуги), а все остальные вершины имеют степень захода 1 (в них ведёт ровно по одной дуге). Вершина с нулевой степенью захода называется корнем дерева, вершины с нулевой степенью исхода (из которых не исходит ни одна дуга) называются концевыми вершинами или листьями.

Двоичное (бинарное) дерево — иерархическая структура данных, в которой каждый узел имеет не более двух потомков (детей). Как правило, первый называется родительским узлом, а дети называются левым и правым наследниками.

Списки

Линейный односвязный список – это последовательность линейно связанных элементов. В списке разрешены операции добавления и удаления любого элемента. Частными случаями линейного односвязного списка являются стек и очередь.

Операции, которые можно производить над списками:

- добавление элемента в список (в начало, в конец в середину);

- перемещение элемента в списке  вперед/назад

- удаление элемента из списка;

- выборка диапазона элементов;

- поиск предыдущего / следующего элемента.

Рассмотрим примеры задач:

Пример построения бинарного дерева :

Пусть, например, дана последовательность целых чисел: {5, 2, 8, 7, 2, 9, 1, 6}

Первое число 5, оно будет записано в корень дерева. (рис. а).

Второе число 2, меньше значения в корне дерева, значит оно будет записано в левое «поддерево», (см. рис. б).

Следующее число 8 больше значения в корне, соответственно, оно будет записано в правое поддерево (рис. в).

Следующее число 7 больше, чем значение в корне дерева, значит, оно должно быть записано в правое поддерево, но правое поддерево уже построено. Сравниваем 7 со значением в корне правого поддерева – числом 8. Так как добавляемое значение меньше значения в корне правого поддерева, то добавляем левое поддерево уже к этому корню (рис. г).

Полностью сформированное бинарное дерево для нашей последовательности {5, 2, 8, 7, 2, 9, 1, 6} представлено на рис. д.

Пример задачи с использованием графа для определения различных путей и определения кратчайшего пути на графе.

Как преобразовать информацию, представленную в табличной форме в граф?

Как определить все пути в графе?

Определить кратчайший путь?

Решение:

Проанализируем таблицу.

Такую таблицу называют весовой матрицей. Части таблицы, разделённые диагональю – симметричны, т.е. содержат одни и те же данные. Следовательно, можно рассматривать данные любой половины таблицы, разделенной диагональю. Теперь приступим к построению взвешенного графа по этой таблице.

Определим все пути в графе и расстояние, пройденное на этом пути (вес в данном случае - расстояние в км.)

  Будем делать обход по графу в алфавитном порядке, т.е. сначала вс е пути через АВ, АС, AD и т.д.

1.ABCDE – 25 км

2.ABCE – 15 км

3.ABDCE – 10 км

4.ACBDE – 31 км

5.ACDE – 24 км

6.ACE – 14 км

7.ADCE – 15 км

8.ADE – 19 км

9.AE – 16 км

Ответ: Кратчайший путь в данном графе : ABDCE – 10 км .

Теперь рассмотрим другой тип задач: вычисление количества путей на графе.

На карту нанесены 3 города (А, В и С).

Известно, что: между городами А и С — три дороги, между городами А и В — четыре дороги, между городами В и С — две дороги.

По каждой из этих дорог можно ехать в обе стороны. Сколькими различными способами можно проехать из А в С, посещая каждый город не более одного раза?

Решение.

Из города А в город С можно попасть либо напрямую, либо через город В. Попасть напрямую — 3 способа (3 дороги из А в С). Попасть через город В — 8 способов (из А в В — 4 дороги, из В в С — 2 дороги. Нужно проехать из А в В И из В в С. Варианты перемножаются. 4 * 2 = 8).

Оба рассмотренных варианта (напрямую ИЛИ через город В) нужно сложить. То есть, 3 + 8=11.

Ответ: 11.

Существует еще один метод задания графа: таблица инцидентности

Для заполнения этой таблицы необходимо пронумеровать ребра графа:

Правило заполнения:

1 – вершина с ребром соединена

0 – вершина с ребром не соединяется

Названия строк таблицы инцидентности – названия вершин графа, названия столбцов – номера ребер графа. Эта таблица не является симметричной и не имеет главной диагонали.

Примером применения неориентированного графа служит дорожная сеть.

Схема дорожной сети не является картой местности, здесь не соблюдается масштаб, схема не ориентирована по сторонам света. Вершинами графа дорожной сети являются названия населенных пунктов, а ребрами –дороги между ними. Чем сеть гуще, тем больше вариантов проезда между населенными пунктами.

Рассмотрим пример:

Район состоит из пяти поселков:

Марьино, Прокшино, Софьино, Булатово и Лукино.

Автомобильные дороги проложены между: Марьино и Прокшино, Марьино и Булатово, Прокшино и Лукино, Прокшино и Булатово, от Булатово до Софьино.

Пример схемы по этому описанию:

Поселки обозначены первыми буквами названий:

М – Марьино, П – Прокшино, С – Софьино, Б – Булатово, Л - Лукино

Глядя на этот граф, можно ответить на вопрос – через какие поселки нужно проехать, чтобы добраться из Софьино в Лукино?

Возможно два пути:

  1 вариант С – Б – П – Л (Софьино-Булатово-Прокшино-Лукино)

2 вариант С – Б – М – П – Л (Софьино-Булатово-Марьино-Прокшино-Лукино)

ПРАКТИЧЕСКАЯ ЧАСТЬ

1. Изучите теорию по теме занятия

2. Выполните задания

3. Оформите отчет в тетради.

ЗАДАНИЯ

Задача №1

Между населенными пунктами A, B, C, D, E, F построены дороги, протяженность которых
(в километрах) приведена в таблице.

Передвигаться можно только по дорогам, указанным в таблице.

Постройте взвешенный граф. Определите все возможные пути между пунктами A и F , и найдите длину кратчайшего из них.

Задача №2

На карту нанесены 4 города А, B , C и D .

Известно, что:

между городами А и С – две дороги,

между городами С и В – четыре дороги,

между городами А и В – три дороги,

между городами С и D – три дороги,

между городами В и D – три дороги.

По каждой из этих дорог можно ехать в обе стороны.

Сколькими различными способами можно проехать из А в D, посещая каждый город не более 1 раза?

Задача №3

Постройте бинарное дерево для последовательностей целых чисел

1) {12 , 7 , 17 , 15 , 53. 10, 11, 3, 14, 8}

2) {9, 12, 4, 54, 21, 7, 6, 19, 13,24}

3)    {17,15, 13, 8, 9,14, 25, 18, 27,21,12,5}

 Контрольные вопросы

1.     Какие виды графов Вы знаете?

2.      Где используются направленные ациклические графы?

3.       Примером какого графа является дорожная сеть?