Требования к представлению графов

 

Известны различные способы представления графов в памяти компьютера, которые различаются объемом занимаемой памяти и скоростью выполнения операций над графами. Представление выбирается, исходя из потребностей конкретной задачи. Далее приведены четыре наиболее часто используемых представления с указанием характеристики п(р, q) — объема памяти для каждого представления. Здесь р - число вершин, а q - число ребер. Указанные представления пригодны для графов и орграфов, а после некоторой модификации также и для псевдографов, мультиграфов и гиперграфов.

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

M : array [1..p, 1..p] of 0..1,

M [i, j] = 1, если вершина v_i смежна с вершиной v_j

 0, если вершины не v_i и v_j смежны.

Для матрицы смежности п(р, q) = O ( p ² ).

2. Матрица инциденций. Представление графа с помощью матрицы H : array [1..p, 1..q] of 0..1 (для орграфов H : array [1..p, 1..q] of -1..1), отражающей инцидентность вершин и рёбер, называется матрицей инциденций, где для неориентированного графа

H [i, j] = 1, если вершина v_i инцидентна ребру e_j,

 0, в противном случае.

а для ориентированного графа

 1, если вершина v_i инцидентна ребру e_j и является его концом,

 H [i, j] = 0, если вершина v_i и ребро e_j не инцидентны,

 -1, если вершина v_i инцидентна ребру e_j и является его началом

3. Списки смежности. Представление графа с помощью списочной структуры, отражающей смежность вершин и состоящей из массива указателей Г : array [1..р] оf ­ N на списки смежных вершин (элемент списка представлен структурой N : record v:1..р; п : ­ N endrecord), называется списком смежности. В случае представления неориентированных графов списками смежности п(р, q ) = О(р + 2 q ), а в случае ориентированных графов п(р, q) = О(р + q ).

4. Массив дуг. Представление графа с помощью массива структур Е : array [1..р] of record b,e : 1..p endrecord, отражающего список пар смежных вершин, называется мас сивом ребер(или, для орграфов, массивом дуг). Для массива ребер (или дуг) п(р, q) = О( 2 q ).

5. Обход графа — это некоторое систематическое перечисление его вершин (и/или ребер). Наибольший интерес представляют обходы, использующие локальную информацию (списки смежности). Среди всех обходов наиболее известны поиск в ширину и в глубину. Алгоритмы поиска в ширину и в глубину лежат в основе многих конкретных алгоритмов на графах.

ТЕОРЕМА Если граф G связен (и конечен), то поиск в ширину и поиск в глубину обойдут все вершины по одному разу.

Доказательство

1. Единственность обхода вершины. Обходятся только вершины, попавшие в Т. В Т попадают только неотмеченные вершины. При попадании в Т вершина отмечается. Следовательно, любая вершина будет обойдена не более одного раза.

2. Завершаемость алгоритма. Всего в Т может попасть не более р вершин. На каждом шаге одна вершина удаляется из Т. Следовательно, алгоритм завершит работу не более чем через р шагов.

3. Обход всех вершин. От противного. Пусть алгоритм закончил работу, и вер шина w не обойдена. Значит, w не попала в Т. Следовательно, она не былаотмечена. Отсюда следует, что все вершины, смежные с w , не были обойденыи отмечены. Аналогично, любые вершины, смежные с неотмеченными, самине отмечены (после завершения алгоритма). Но G связен, значит, существуетпуть ( v , w ). Следовательно, вершина v не отмечена. Но она была отмечена напервом шаге.

4.2 Реализация алгоритмов поиска в ширину и в глубину в программной среде Turbo Pascal

Задача состоит в том, найти путь из вершины A в вершину B. Будем задавать граф матрицей смежности, т.е. квадратной таблицей NxN, в которой на пересечении i-й строки и j-го столбца значение TRUE, если i и j соединены ребром, и FALSE в противном случае.

Поиск в ширину.

Подобно тому как, согласно принципу Гюйгенса, каждая точка волнового фронта является источником вторичной волны, мы, отправляясь из заданной вершины A, посещаем все смежные с ней вершины (т.е. вершины, в которые ведут стрелки из A). Каждая посещенная вершина становится источником новой волны и т.д. При этом необходимо позаботиться о том, чтобы не вернутся в ту вершину, в которой уже были. Для реализации алгоритма понадобятся: матрица m[1..n, 1..n] - матрица смежности графа; вспомогательный массив queue[1..n], в котором будет формироваться очередь, т.е. тип данных первый вошел – первый вышел (FIFO). Размер его достаточен, так как мы не посещаем вершины дважды. С массивом queue связаны две переменные - head и tail. В переменной head будет находиться номер текущей вершины, из которой идет волна, а при помощи переменной tail новые вершины помещаются в "хвост" очереди queue; вспомогательный массив visited[1..n], который нужен для того, чтобы отмечать уже пройденные вершины (visited[i]=TRUE <=> вершина i пройдена); вспомогательный массив prev[1..n] для хранения пройденных вершин. В этом массиве и будет сформирован искомый путь; переменная f, которая примет значение TRUE, когда путь будет найден. Кроме того, мы введем несколько вспомогательных переменных, которые понадобятся при организации циклов.

Program breadth_first_search; Const n=9; m:array[1..n, 1..n] of boolean = ( (False, True, True, False, False, False, False, False,False), (True, False, True, False, False, False, True, True,False), (True, True, False, True, True, False, False, False,False), (False, False, True, False, True, False, False, False,False), (False, False, True, True, False, True, False, True,False), (False, False, False, False, True, False, True, True, True), (False, True, False, False, False, True, False, True, True), (False, True, False, False, True, True, True, False,False), (False, False, False, False, False, True, True, False, False) ); Var A, B: integer;Procedure A_to_B(A, B: integer); Var Visited: array[1..n] of boolean; Prev: array[1..n] of integer; c: array[1..n] of integer; head, tail: integer; f: boolean; i, v, k: integer; Begin head:=1; tail:=1; f:=False; For i:=1 to n do Begin Visited[i]:=False; Prev[i]:=0 End; C[tail]:=A; Visited[A]:=True; While (head<=tail) and not f do Begin v:=C[head]; head:=head+1; For k:=1 to n do if m[v, k] and not Visited[k] then Begin tail:=tail+1; C[tail]:=k; Visited[k]:=True; Prev[k]:=v; if k=B then Begin f:=true; break End End End; if f then Begin k:=B; Write(B); While Prev[k]<>0 do Begin Write('<-', Prev[k]); k:=Prev[k] end End else Write('Пути из ', A, ' в ', B, ' нет') end;Begin Write('A= '); readln(A); Write('B= '); readln(B); A_to_B(A, B) End.

Поиск в глубину.

Идея поиска в глубину проста: отправляясь от текущей вершины, мы находим новую (еще не пройденную) смежную с ней вершину, которую помечаем как пройденную и объявляем текущей. После этого процесс возобновляется. Если новой смежной вершины нет (тупик), возвращаемся к той вершине, из которой попали в текущую, и делаем следующую попытку. Если попадем в вершину B, печатаем путь. Если все вершины исчерпаны - такого пути нет. Заметим, что построенный таким образом алгоритм способен находить все пути из A в B, но первый найденный необязательно должен быть кратчайшим. Как обычно, алгоритм с возвратами легче всего оформить с помощью рекурсивной процедуры. Для ее реализации нам понадобятся: матрица m[1..n, 1..n] - матрица смежности графа; вспомогательный массив visited[1..n], который мы будем для того, чтобы отмечать уже пройденные вершины (visited[i]=TRUE <=> вершина i пройдена); переменная f, которая примет значение TRUE, когда путь будет найден.

Program depth_first_search; Const n=9; m:array[1..n, 1..n] of boolean = ( (False, True, True, False, False, False, False, False,False), (True, False, True, False, False, False, True, True,False), (True, True, False, True, True, False, False, False,False), (False, False, True, False, True, False, False, False,False), (False, False, True, True, False, True, False, True,False), (False, False, False, False, True, False, True, True, True), (False, True, False, False, False, True, False, True, True), (False, True, False, False, True, True, True, False,False), (False, False, False, False, False, True, True, False, False) ); Var A, B: integer;Procedure A_to_b(A, B: integer); Var Visited: array[1..n] of boolean; f: boolean; i: integer;Procedure Depth(p: integer); var k: integer; Begin Visited[p]:=True; For k:=1 to n do If not f then If m[p, k] and not Visited[k] then If k=B then Begin f:=True; Write(B); Break End else Depth(k); If f then write('<=', p); End;Begin For i:=1 to n do Visited[i]:=False; f:=false; Depth(A); If not f then write('Пути из ', A, ' в ', B, ' нет') End;Begin write('A= '); readln(A); write('B= '); readln(B); A_to_B(A, B) End.

 

 

Заключение

 

Курсовой проект выполнен на тему «Графы и их представление на ЭВМ». В нём рассмотрены следующие вопросы:

§ Определение графов: основное определение, смежность, другие определения;

§ Способы задания графов: изображение графа, способы численного представления графов, представление ориентированных граф;

§ Виды графов и операции над ними: элементы графов, изоморфизм графов, тривиальные и полые графы, двудольные графы, направленные орграфы и сети, операции над графами;

§ Представление графов в ЭВМ: требование к представлению графов, реализация алгоритмов поиска в глубину и ширину в программной среде Turbo Pascal;

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

После проделанной работы можно сделать следующий вывод:

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

Список использованной литературы

 

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

2. Судоплатов С.В., Овчинникова Е.В. Элементы дискретной математики: Учебник. – М.: ИНФРА-М, Новосибирск: Изд-во НГТУ, 2002. – 280 с. – (Серия «Высшее образование»)

3. Материал из Википедии — свободной энциклопедии. Элементы теории граф (http://referats/mat_graph);

4. Элементы теории граф (http://book.itep.ru/10/graph1021.htm).