Лабораторная работа №18 Тема: Разработка алгоритмов и программ с использованием алгоритмов на графах

Цель: Сформировать умения разрабатывать алгоритмы и программы с использованием алгоритмов на графах

Программное обеспечение: TURBO PASCAL 7.1

Оснащение: персональный компьютер, практикум

Время проведения: 2 уч. часа

 

Литература:

Павловская Т.А. Паскаль. Программирование на языке высокого уровня. Учебник для вузов. СПб.: Питер, 2008.

ВОПРОСЫ ВХОДНОГО КОНТРОЛЯ:

1. Сформулируйте определение размещения.

2. Сформулируйте определение сочетания.

3. Приведите примеры комбинаторных алгоритмов.

КРАТКИЕ ТЕОРЕТИЧЕСКИЕ СВЕДЕНИЯ

Граф – это нелинейная многосвязная динамическая структура, отображающая свойства и связи сложного объекта.

 

Многосвязная структура обладает следующими свойствами:

- на каждый элемент (узел, вершину) может быть произвольное количество ссылок;

- каждый элемент может иметь связь с любым количеством других элементов;

- каждая связка (ребро, дуга) может иметь направление и вес.

 

В узлах графа содержится информация об элементах объекта. Связи между узлами задаются ребрами графа. Ребра графа могут иметь направленность, показываемую стрелками, тогда они называются ориентированными, ребра без стрелок – неориентированными.

Граф, все связи которого ориентированные, называется ориентированным графом или орграфом; граф со всеми неориентированными связями – неориентированным графом; граф со связями обоих типов – смешанным графом. Неориентированные связи приведены на рисунке 18.1 а, а ориентированные – на рисунке 18.1 б.

 

Рисунок 18.1 ― Графы: а – неориентированный и б –ориентированный

Для ориентированного графа число ребер, входящих в узел, называется полустепенью захода узла, выходящих из узла – полустепенью исхода. Количество входящих и выходящих ребер может быть любым, в том числе и нулевым. Граф без ребер является нуль-графом.

Если ребрам графа соответствуют некоторые значения, то граф и ребра называются взвешенными. Мультиграфом называется граф, имеющий параллельные (соединяющие одни и те же вершины) ребра, в противном случае граф называется простым.

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

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

 

Логически структура-граф может быть представлена матрицей смежности или матрицей инцидентности.

Матрицей смежности для n узлов называется квадратная матрица adj порядка n. Элемент матрицы a (i, j) равен 1, если узел j смежен с узлом i (есть путь < i, j >), и 0 – в противном случае (рис. 18.2).

Рисунок 18.2 ― Граф и его матрица смежности

 

Если граф неориентирован, то a (i, j) = a (j, i), т. е. матрица симметрична относительно главной диагонали.

Матрицы смежности используются при построении матриц путей, дающих представление о графе по длине пути: путь длиной в 1 – смежный участок, путь длиной 2 – (< A,B >,< B,C >),... в n смежных участков, где n – максимальная длина, равная числу узлов графа. На рисунке 18.3 даны путевые матрицы пути adj 2, adj 3, adj 4 для графа рисунке 18.2.

Рисунок 18.3 ― Матрицы путей

 

Матрицы инцидентности используются только для орграфов. В каждой строке содержится упорядоченная последовательность имен узлов, с которыми данный узел связан ориентированными (исходящими) ребрами. На рисунке 18.4 показана матрица инцидентности для графа на рисунке 18.2.

Рисунок 18.4 ― Матрицы инцидентности

 

Машинное представление оpгpафов

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

 

Матричное представление орграфов

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

Например, для простого ориентированного графа, изображенного на рисунке 18.2, массив определяется как:

mas:array[1..4,1..4]=((0,1,0,0),(0,0,1,1), (0,0,0,1),(1,0,1,0))

Матрицы смежности применяются тогда, когда в графе много связей и матрица хорошо заполнена.

 

Связное представление орграфов

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

В первом варианте два типа элементов – атомарный и узел связи. На рис. 5 показана схема такого представления для графа на рисунке 18.2. Скобочная запись связей этого графа:

(< A,B >,< B,C >,< C,D >,< B,D >,< D,C >)

Рисунок 18.5 ― Машинное представление графа элементами двух типов

 

Более рационально представлять граф элементами одного формата, двойными: атом-указатель и указатель-указатель или тройными: указатель-data/down-указатель. На рисунке 18.6 тот же граф представлен элементами одного формата.

 

Рисунок 18.6 ― Машинное представление графа однотипными элементами

 

Многосвязная структура – граф – находит широкое применение при организации банков данных, управлении базами данных, в системах программного иммитационного моделирования сложных комплексов, в системах исскуственного интеллекта, в задачах планирования и в других сферах.

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

МЕТОДИЧЕСКИЕ УКАЗАНИЯ

{Алгоритм Дейкстры} Program Example_1; Const n=5; max=10000; Var a: Array [1..n,1..n] of Integer; v0,w,edges: Integer; from,tu,length: Array [1..n] of Integer; Procedure adjinit;{эта пpоцедуpа задает вес pебеp гpафа посpедством опpеделения его матpицы смежности A pазмеpом N x N } Var i,j: Integer; Begin {"обнуление" матpицы (веpшины не связаны)} For i:=1 to n do For j:=1 to n do a[i,j]:=max; For i:=1 to n do a[i,i]:=0;{задание длин pебеp, соединяющих смежные узлы гpафа} a[1,2]:=12; a[1,3]:=18; a[1,4]:=10; a[2,1]:=12; a[2,3]:=6; a[2,5]:=9; a[3,1]:=18; a[3,2]:=6; a[3,4]:=7; a[3,5]:=3; a[4,1]:=10; a[4,3]:=7; a[4,5]:=15; a[5,2]:=9; a[5,3]:=3; a[5,4]:=15; end;Procedure printmat;{эта пpоцедуpа выводит на экpан дисплея матpицу смежности A взвешенного гpафа} Var i,j: Integer; Begin writeln; writeln('Матpица смежности взвешенного гpафа (',n,'x',n,'):'); writeln; For i:=1 to n do Begin write ('Е'); For j:=1 to n do If a[i,j]=max Then write(' ----') Else write(a[i,j]:6); writeln(' Е') End; writeln; writeln (' ("----" - pебpо отсутствует)') end;Procedure dijkst;

 

СОДЕРЖАНИЕ РАБОТЫ: Написать программу с использованием алгоритма обхода графа в глубину.

 

ВОПРОСЫ ВЫХОДНОГО КОНТРОЛЯ:

1. Сформулируйте определение графа.

2. Перечислите виды графов.

3. Приведите примеры алгоритмов для работы с графами.

ДОМАШНЕЕ ЗАДАНИЕ

Выучить алгоритмы с применением графов.