Основные понятия теории графов



Скачать 396.01 Kb.
страница2/5
Дата11.10.2012
Размер396.01 Kb.
ТипЛекция
1   2   3   4   5

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


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

М
атрица смежности
– это матрица n×n, где n - число вершин. Строка с номером i содержит 1 в строке с номером j, если существует дуга из вершины i в вершину j.

Пример. Составить матрицу смежности для взвешенного графа:

Решение:




a

b

c

d

a

0

1

10

0

b

1

0

2

10

с

10

2

0

3

d

0

10

3

0

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

Решение:





a

b

c

d

a

0

1

1

0

b

1

0

1

0

с

1

1

0

1

d

0

0

1

0
Н
ебольшое затруднение возникнет в том случае, если в графе разрешаются ребра с весом 0. Тогда придется хранить два массива: один с нулями и единицами, которые служат показателем наличия ребер, а второй - с весами этих ребер.
Задание 2. Неориентированный граф задан матрицей смежности. Нарисовать граф.





1

2

3

4

5

6

1

0

1

1

0

0

0

2

0

0

0

1

1

0

3

0

1

0

0

0

0

4

0

0

0

0

1

0

5

0

0

1

0

0

0

6

0

0

0

0

0

0
Ответ:



Задание 3. Составить матрицу смежности для следующего графа:


Ответ:




1

2

3

4

5

1

0

1

1

0

0

2

1

0

0

1

1

3

1

0

0

1

0

4

0

1

1

0

0

5

0

1

0

0

0


Матрица смежности для неориентированного графа будет симметричной относительно своей главной диагонали, а для орграфа - несимметричной.

Удобство матрицы смежности состоит в наглядности и прозрачности алгоритмов, основанных на ее использовании. А неудобство - в несколько завышенном требовании к памяти: если граф далек от полного, то в массиве, хранящем матрицу смежности, оказывается много "пустых мест" (нулей).

Матрица инцидентности


Матрица инцидентности имеет размер m*n, где n – количество вершин, m – количество дуг графа. Элемент матрицы, соответствующий k-дуге и i-ой вершине, равен

  • +1, если дуга выходит из вершины;

  • –1, если дуга входит в вершину


  • и нули во всех остальных строках.

Пример. Для неориентированного графа на рисунке матрица инцидентности:



Задание 1. Составить матрицу инцидентности для следующего графа:



Ответ:




a

b

c

d

e

1

1

0

0

-1

0

2

-1

1

0

0

-1

3

0

-1

1

0

0

4

0

0

-1

1

1

5

0

0

0

0

0

Задание 2. Ориентированный граф задан матрицей инцидентности. Вершины обозначены номерами 1, 2, 3, 4, 5, 6, а ребра латинскими буквами a, b, c, d, e, f, g, h, i.



Нарисовать граф.

Ответ:


Список ребер


Этот способ задания наиболее удобен для внешнего представления входных данных. Каждая строка входного файла содержит информацию об одном ребре или дуге в следующем виде:

<номер начальной вершины> <номер конечной вершины> [<вес ребра>]

Например, для следующих графов получим списки:



a b

a c

b c

b d

c d

c f

f d

b f



a b 1

a c 10

b c 2

b d 10

c d 3

Списки смежности


Этот способ задания графов подразумевает, что для каждой вершины будет указан список всех смежных с нею вершин (для ориентированного графа – список вершин, являющихся концами исходящих дуг):

<номер начальной вершины>: <номера смежных вершин>

Пример: (рис. графов см. выше)

1) a: b c

b: c d f

c: d f

d: f

2) a: b 1 c 10

b: a 1 c 2 d 10

c: a 10 d 3

d: b 10 c 3

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

Type refnode=^node;

refarc=^arc;

node=record {список вершин}

id:integer; {номер вершины}

infnode:integer; {вес}

next:refnode; {указатель на следующую вершину в списке}

arclist:refarc {указатель на список дуг}

end;

arc=record {список дуг определенной вершины}

infarc:integer; {вес}

next:refarc; {указатель на следующую дугу, исходящую из данной вершины}

adj1:refnode {указатель на вершину, в которую ведет данная дуга}

end;

В универсальном динамическом представлении используется линейный список. Для любой вершины можно хранить ее вес.

Например, для графа следующего вида

типы данных для представления графов:

Type refnode=^node;

refarc=^arc;

node=record {список вершин}

id:integer; {номер вершины}

infnode:integer; {вес}

next:refnode; {указатель на следующую вершину в списке}

arclist:refarc {указатель на список дуг}

end;

arc=record {список дуг определенной вершины}

infarc:integer; {вес}

next:refarc; {указатель на следующую дугу, исходящую из данной вершины}

adj:refnode {указатель на вершину, в которую ведет данная дуга}

end;



получим следующее представление:


Задание. Нарисовать списковое представление графа (см. задание 2 раздела «Матрица инцидентности».

Рассмотрим основные процедуры работы с графами.
Основные процедуры работы с графами
Добавление вершины

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

Procedure AddNode(Var graph: refnode; n,x:integer);

Var p:refnode;

Begin new(p);

With p^ do

Begin id:=n;

Infnode:=x;

Arclist:=nil;

Next:graph

End;

graph:=p;

end;

Добавление дуги


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

Procedure AddArc(u,v:refnode; y:integer);

Var a:refarc;

Begin if u=nil or v=nil then writeln(‘Отсутствует вершина’)

Else begin

New(a);

With a^ do begin

Infarc:=y;

Adj:=v;

Next:=u^.arclist

End;

u^.arclist:=a

end

end;

Удаление дуг и вершин


Для удаления дуги указываются две ссылки на вершины, которые эта дуга соединяет. Приведенная ниже процедура удаляет элемент из списка дуг, выходящих из вершины u, если в нем записана ссылка на вершину v. Если таких элементов несколько, то удаляется первый встретившийся.

Procedure DeleteArc(u,v:refnode);

Var a,before:refarc;

Run:boolean;

Begin

If u<>nil then Begin

a:=u^.arclist;

run:=truel

while a<>nil and run do

if a^.adj=v then run:=false

else begin

before:=a;

a:=a^.next

end;

if a<>nil then begin

if a=u^.arclist then u^.arclist:=a^.next

else before^.next:=a^.next;

dispose(a)

end

end

end;

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

Procedure DeleteNode(Var graph:refnode; v:refnode);

Var before,p,q:refnode;

a,after:refarc;

begin

p:=graph;

while p<>nil do {цикл по всем вершинам графа}

begin

q:=p^.next;

if p<>v then begin

DeleteArc(p,v) {удаление дуг, направленных удаляемой вершине}

before:=p;

end

else Begin {удаление вершины v и всех дуг, исходящих из нее}

if p=graph then graph:=q; {если это первая вершина}

a:=p^.arclist;

{удаление списка дуг вершины v}

while a<>nil do

begin

after:=a^.next;

dispose(a);

a:=after

end;

if p=graph then graph:=q

else before^.next:=q;

dispose(p);

end;

p:=q;

end

end;

Просмотр графа


Просмотр графа заключается в посещении всех вершин и дуг графа и выводе в стандартный файл всей информации о графе. Для непустого графа информация группируется по вершинам (списки смежности).

Procedure BrowseGraph(graph:refnode);

Var a:refarc;

Nn,na: integer; {счетчики количества вершин и дуг}

Begin

Nn:=0; na:=0;

while graph<>nil do

begin

writeln(‘Вершина ’, graph^.id,’ с весом ’ ,graph^.infnode);

writeln(‘Список дуг:’);

a:=graph^.arclist;

if a=nil then writeln(‘пуст’);

while a<>nil do begin

writeln(‘Дуга к вершине ’, (a^.adj)^.id,’, вес дуги ’,a^.infarc);

na:=na+1;

a:=a^.next;

end;

nn:=nn+1;

graph:=graph^.next;

end;

writeln(‘В графе ’, nn, ‘вершин и ‘, na,’ дуг’)

end;

Алгоритмы на графах: поиск в глубину и поиск в ширину,

алгоритм Дейкстры
1   2   3   4   5

Похожие:

Основные понятия теории графов iconЭлементы теории графов
...
Основные понятия теории графов iconТеория графов и ее приложения
Основные понятия. Графы неориентированные и ориентированные. Способы задания графов. Матрицы смежности и инцидентности графа. Понятие...
Основные понятия теории графов iconОсновные понятия теории графов
Д. Кенига только в 1936 г., но многочисленные прикладные задачи и головоломки (которые, кстати, поддавались формулировкам в терминах...
Основные понятия теории графов iconОсновные понятия теории графов граф и его виды
Первая работа по теории графов принадлежит Леонарду Эйлеру (1736 год), хотя термин «граф» впервые ввел в 1936 году венгерский математик...
Основные понятия теории графов iconВопросы к экзамену Основные понятия теории графов (определение графа, виды графов, смежность, инцидентность, кратность ребер, степень вершины). Примеры
Способы задания графов. Матричный способ задания. Свойства матриц смежности и инцидентности. Привести примеры
Основные понятия теории графов iconЛекция 11: Графы и деревья
...
Основные понятия теории графов iconVi. Элементы теории графов. Основные понятия теории графов. Определение Графом
Определение Графом называется совокупность 2-х множеств Х и У. Х это множество точек, называемых вершинами графа, а у это множество...
Основные понятия теории графов iconМетодические указания к самостоятельным и семинарским занятиям по теории графов Москва 2006
Предназначены для решения задач по теории графов как при самостоятельном изучении теории графов, так и при решении задач на семинарах...
Основные понятия теории графов iconГрафы 4 Основные понятия теории графов 4
Пример Метод модульно-ориентированного анализа и проектирования сложных систем 10
Основные понятия теории графов iconОб орграфах, имеющих минимальные вершинные 1-расширения с малым количеством дополнительных дуг
В работе используются основные понятия теории графов в соответствии с работой [1]
Разместите кнопку на своём сайте:
ru.convdocs.org


База данных защищена авторским правом ©ru.convdocs.org 2016
обратиться к администрации
ru.convdocs.org