Лабораторная работа №1 / MDLAB1.DOC

Краткие теоретические сведения.

Определение графа - Граф - это пара (V,E), где V - конечное непустое множество вершин, а E - множество неупорядоченных пар <u,v> вершин из V называемых ребрами. Говорят, что ребро s=<u,v> соединяет вершины u и v. Ребро s и вершина u (а также s и v) называются инцидентными, а вершины u и v - смежными. Ребра, инцидентные одной и той же вершине, также называют смежными. степень вершины равна числу ребер, инцидентных ей.

Часть графа G = (V,E) - это такой граф G' = (V',E'), что V' принадлежит V и E' принадлежит E. Подграфом графа G называется такая его часть G', которая вместе со всякой парой вершин u, v содержит и ребро <u,v>, если только оно есть в G.

Путь, соединяющий вершины u и v, - это последовательность вершин v(0), v(1), ... , v(n) (n>=0) такая, что v(0)=u, u(n)=v и для любого i ( 0 <= i <= n-1 ) вершины v(i) и v(i+1) соединены ребром. Длина пути v(0), v(1), ... ,v(n) равна количеству его ребер т.е. n. Путь замкнут, если v(0) = v(n). Путь называется простым, если все его вершины различны. Замкнутый путь, в котором все ребра различны называется циклом. Простой цикл - это замкнутый путь, все вершины которого, кроме v(0) и v(n), попарно различны. Гамильтоновым называется граф, в котором существует простой цикл, содержащий все вершины графа (но не обязательно все его ребра).

Расстояние между двумя вершинами - это длина кратчайшего пути, соединяющего эти вершины. Обод - это граф, вершины которого v(0), v(1), ..., v(n) ( n >= 2 ) можно занумеровать так, что для всех i (1<=i<=n-1) вершина v(i) соединена ребрами с v(i-1), v(i+1), вершина v(0) - c v(n), а других ребер нет.

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

Дополнением графа G называется граф G' с тем же множеством вершин что и у G, причем две различные вершины смежны в G' тогда и только тогда, когда они не смежны в G.

Граф называется полным, если любые две его различные вершины соединены ребром. Два графа G и H изоморфны если существует взаимно однозначное отображение ( называемое изоморфизмом ) множества вершин графа G на множество вершин графа H, сохраняющее смежность. Автоморфизмом графа G называется изоморфизм графа G на себя.

Ориентированный граф, или орграф, G = (V,E) отличается от графа тем что E - это множество упорядоченных пар (u,v) вершин u,v принадлежащих V, называемых дугами. Дуга (u,v) ведет от вершины u к вершине v. При этом вершину v называют преемником вершины u, а u - предшественником вершины v.

Понятия части орграфа, пути, расстояния между вершинами, простого и замкнутого пути, цикла определяются для орграфа так же, как и для графа, но с учетом ориентации дуг.

Деревом называется связный граф без циклов.

Пустой граф (дерево) - это граф с пустым множеством вершин.

Корневое дерево - это связный орграф без циклов, удовлетворяющий следующим условиям:

а). имеется ровно одна вершина, называемая корнем, к которой не ведет ни одной дуги;

б). к каждой вершине, отличной от корня, ведется ровно одна дуга;

в). преемники всякой вершины упорядочены.

Вершины корневого дерева, не имеющие преемников, называются листьями.

Лабораторная работа N 1

Тема: Хранение графов в памяти ЭВМ.

Цель работы: 1. Освоение и изучение способов задания графов: матрица

инцидентности, матрица смежности, список смежности.

2. Разработка процедур преобразования видов хранения

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

Способы задания графов -

-----------------------------

Существует три основных способа задания графа:

1). Матрица инцидентности;

2). Матрица смежности;

3). Список смежности ( инцидентности );

Рассмотрим подробнее каждый из этих способов задания графа:

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

--------------------------

Представляет собой матрицу m на n, где m - количество ребер или дуг графа ( орграфа ), а n - количество вершин. На пересечении i - ой строки и j - ого столбца проставляются значения по следующему правилу:

" 1 " - если i - ое ребро и j - ая вершина инцидентны ( для

орграфа - если i - ая дуга "входит" в j - ую вершину );

" 0 " - если i - ая дуга и j - ая вершина не инциндентны;

" -1 " - только в случае орграфа: если i - ая дуга "выходит"

из j - ой вершины );

Как легко можно заметить, этот способ задания графа довольно неэффективен: каждая строка такой матрицы содержит только 2 ячейки с ненулевыми значениями ( очевидно, так как одно ребро (дуга) может быть инцидентно не более чем двум вершинам). В результате мы имеем довольно неэкономное использование диковой или оперативной памяти ЭВМ - в зависимости от того, где хранится информация о нашем графе.

Типичный пример задания матрицы инцидентности на языке Pascal - при помощи двумерного массива m на n:

Matr_Ints: array [1..LinksCount, 1..TopsCount] of integer;

Матрица смежности -

-------------------------

Представляет собой квадратную матрицу n на n, где n- количество вершин графа.

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

При более подробном рассмотрении можно заметить, что в случае графа без петель матрица имеет ряд особенностей:

во-первых, главная диагональ матрицы всегда заполнена нулями,

так как вершина не может быть смежна сама себе;

во-вторых, если наш граф неориентированный - то часть матрицы

под главной диагональю и над ней абсолютно идентичны.

На Pascal-е матрица смежности, как и матрица инцидентности чаще всего задается при помощи двумерного массива:

Matr_Sm :array [1..TopsCount,1..TopsCount] of byte,

либо

Matr_Sm :array [1..TopsCount,1..TopsCount] of boolean;

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

Список смежности и список инцидентности -

----------------------------------------------

Список смежности представляет собой список из n строк, ( n - количество вершин), где в i - ой строке записываются номера вершин, смежных с ершиной под номером i. Как мы видим, этот список тем больше, чем больше связей между вершинами графа.

Список инцидентности задается аналогично списку смежности, только с одной лишь разницей, что в i - ой строке записываются номера ребер ( или дуг ), инцидентных данной ( i - ой ) вершине.

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

Пусть задан граф на n вершинах и требуется создать некоторую структуру переменных в памяти ЭВМ, отображающую список смежности, составленный для данного графа. Для начала выясним, что будет представлять собой данная структура. Так как строка списка содержит номера вершин, то естественно предположить, что мы должны иметь некоторую цепочку динамических переменных целочисленного типа, связанных между собой. Такая связь обеспечивается использованием указателей, обьединенных вместе с целочисленной переменной в запись ( Pascal: record ). Для того, чтобы обеспечить хранение входных указателей в такие цепочки, используется одномерный массив указателей, имеющий длину, равную количеству вершин графа. Признаком конца цепочки можно использовать каое либо значение, не допускаемое при нумерации вершин ( например - "0" ), занесенное в целочисленную переменную последнего блока.

Для созданя такой структуры предварительно необходимо сделать объявления такого рода:

Type

BlockPtr = ^BlockType;

BlockType = record

Number :integer;

Point :BlockPtr;

end;

Var

In_Ptr :array [1..TopsCount] of BlockPtr;

Создание цепочки в памяти осуществляется при вводе списка смежности при помощи процедуры New (BlockPtr_Type_Variable), где BlockPtr_Type_Variable - переменная типа BlockPtr.

Задание

1. Разработать процедуры ввода графа в виде матрицы инцидентности, матрицы смежности и списка смежности с возможностью корректировки введенных данных.

2. Разработать процедуры преобразования различных форм хранения графа:

-- из матрицы смежности в список смежности и обратно;

-- из матрицы инцидентности в список смежности и обратно;

3. Используя указанные выше процедуры, получить программу, выполняющую следующие функции:

-- ввод графа в любой из трех форм представления (по требованию пользователя) с возможностью коррекции данных;

-- хранение введенного графа в памяти ЭВМ в виде списка смежности;

-- вывод информации о графе в любом из трех видов ( также по требованию пользователя ) на дисплей;

Текст программы на языке Pascal.

program mgraf;

uses crt;

type pgraf=^graf;

graf=record

num:integer;

next:pgraf;

end;

var

start,current,prev:pgraf;

k,f,l:integer;

mat,mat1:array[0..100,0..100] of integer;

procedure vmi;

var a,b,c,i,j,d:integer;

begin

a:=0;b:=0; d:=0;

writeln('vvedite razmernosti grafa');

write('colvo reber ');readln(a);

write('colvo versin ');readln(b);

write('orgraf (1-yes,0-no) ');readln(f);

if f=1 then f:=-1

else f:=1;

for i:=0 to a-1 do

begin

write('rebro ',i+1,': ');

for j:=0 to b-1 do

read(mat[i,j]);

end;

start:=nil;

for i:=0 to b-1 do

begin

new(current);

if d=0 then

begin

start:=current; d:=1;prev:=current; end

else

begin

prev^.next:=current;

prev:=current;

end;

current^.num:=i+1;

current^.next:=nil;

for j:=0 to a-1 do

if mat[j,i]=f then

for c:=0 to b-1 do

begin

if (mat[j,c]=1) and (i<>c) then

begin

new(current); prev^.next:=current; current^.num:=c+1; current^.next:=nil;

prev:=current;

end;

end;

new(current); prev^.next:=current; current^.num:=-1; current^.next:=nil;

prev:=current;

end;

end;

procedure vms;

var i,j,b,d:integer;

begin

d:=0;

writeln('vvedite razmernosti grafa');

write('colvo versin ');readln(b);

write('orgraf (1-yes,0-no) ');readln(f);

if f=1 then f:=-1

else f:=1;

for i:=0 to b-1 do

begin

write('versina ',i+1,' : ');

for j:=0 to b-1 do

read(mat[i,j]);

end;

for i:=0 to b-1 do

begin

new(current);

if d=0 then begin start:=current; prev:=current;d:=1; end

else begin prev^.next:=current; prev:=current; end;

current^.num:=i+1;

for j:=0 to b-1 do

if mat[i,j]=1 then

begin

new(current);

prev^.next:=current; prev:=current; current^.num:=j+1;

end;

new(current);

prev^.next:=current; prev:=current; current^.num:=-1;current^.next:=nil;

end;

end;

procedure vss;

var b,i,d,s:integer;

begin

d:=0;

writeln('vvedite razmernosti grafa');

write('colvo versin ');readln(b);

write('orgraf (1-yes,0-no) ');readln(f);

if f=1 then f:=-1

else f:=1;

for i:=0 to b-1 do

begin

new(current);

if d=0 then begin start:=current; prev:=current;d:=1; end

else begin prev^.next:=current; prev:=current; end;

current^.num:=i+1;

repeat

write('vvesti versinu smejnuiu versine ',i+1,'? (1-da) '); read(s);

if s=1 then

begin

new(current);

prev^.next:=current; prev:=current;read(current^.num);

end;

until s<>1;

new(current);

prev^.next:=current; prev:=current; current^.num:=-1;current^.next:=nil;

end;

end;

procedure oss;

var e:integer;

begin

e:=0;

current:=start;

while current^.next<>nil do

if current^.num=-1 then

begin

writeln(''); current:=current^.next; e:=0;

end

else

begin

if e=0 then

begin

write(' ',current^.num,'-');current:=current^.next;e:=1;

end

else

begin

write(' ',current^.num);current:=current^.next;

end;

end;

end;

procedure oms;

var i,j,a:integer;

begin

a:=0;

current:=start;

while current^.next<>nil do

begin

if current^.num=-1 then a:=a+1;

current:=current^.next;

end;

a:=a+1;

for i:=0 to a-1 do

for j:=0 to a-1 do

mat[i,j]:=0;

current:=start;

i:=0;j:=0;

i:=current^.num-1; current:=current^.next;

repeat

if current^.num=-1 then

begin

if current^.next<>nil then

begin

current:=current^.next; i:=current^.num-1; current:=current^.next;

end;

end

else

begin mat[i,current^.num-1]:=1; current:=current^.next; end;

until current^.next=nil;

for i:=0 to a-1 do

begin

write ('versina ',i+1,': ' );

for j:=0 to a-1 do

write(mat[i,j],' ');

writeln('');

end;

end;

procedure omi;

var i,j,a,d,m,c:integer;

begin

m:=0;

a:=0;

d:=0;

current:=start;

while current^.next<>nil do

begin

if current^.num=-1 then a:=a+1;

current:=current^.next;

end;

a:=a+1;

for i:=0 to a-1 do

for j:=0 to a-1 do

mat[i,j]:=0;

current:=start;

i:=0;j:=0;

i:=current^.num-1; current:=current^.next;

repeat

if current^.num=-1 then

begin

if current^.next<>nil then

begin

current:=current^.next; i:=current^.num-1; current:=current^.next;

end;

end

else

begin mat[i,current^.num-1]:=1; current:=current^.next; end;

until current^.next=nil;

for i:=0 to a-1 do

for j:=0 to a-1 do

if mat[i,j]=1 then

begin

for c:=0 to a-1 do

mat1[d,c]:=0;

mat1[d,i]:=f; mat1[d,j]:=1;

mat[j,i]:=0;d:=d+1;

end;

for i:=0 to d-1 do

begin

write ('rebro ',i+1,': ' );

for j:=0 to a-1 do

write(mat1[i,j],' ');

writeln('');

end;

end;

begin

repeat

clrscr;

writeln ('format vvoda');

write ('1-matrita int, 2-matrita smejn, 3-spisok smejn: ');

readln(k);

case k of

1:vmi;

3:vss;

2:vms;

end;

writeln('format vivida');

write ('1-matrita int, 2-matrita smejn, 3-spisok smejn: ');

readln(k);

case k of

1:omi;

2:oms;

3:oss;

end;

writeln('');

write('povtoriti? (1-yes,0-no) ');

read(l);

until l=0;

end.

Для выполнения каждой из поставленных перед программой задач используется одна из 6 процедур.

Заданный пример графа и его представления.

1

5 2

4

3

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

вершины
Ребра		1	2	3	4	5
	1	-1	1	0	0	0
	2	0	-1	1	0	0
	3	0	0	-1	1	0
	4	0	0	0	-1	1
	5	0	-1	0	1	0

 

 Матрица смежности.

Вершины
вершины		1	2	3	4	5
	1	0	1	0	0	0
	2	0	0	1	1	0
	3	0	0	0	1	0
	4	0	0	0	0	1
	5	0	0	0	0	0