Московский АвиационныйИнститут
(ГосударственныйТехнический Университет)
филиал «Восход»КафедраМиПОИСЛабораторнаяработаподискретной математике
«Графическоепредставление графа»
(отчет)
Преподаватель ____________/Крохина Н.В./
Студент группы ДМ 2-26 ___________/Толоконников А.В./
г.Байконур
2002 г.
1. Задача
Составитьалгоритм перехода к графическому представлению для неориентированного графа иреализовать его программным путем, если граф задан матрицей смежностей.
2. Алгоритм решения,поставленной задачи
1) Вводитсяколичество вершин неориентированного графа.
2) Есликоличество вершин больше 7, то переходим к пункту 3; иначе переходим к пункту4.
3) Генераторомслучайных чисел произвольно задаются связи между вершинами в матрицесмежностей, переходим к пункту 5.
4) Вводятсясвязи между вершинами, исходя из следующего условия: не существует пути длинойв одно ребро из одной вершины в другую – ставим «0», существует путь междудвумя вершинами длиной в одно ребро – ставим «1», существует путь из вершины всаму себя – ставим «2». Все введенные данные заносятся в матрице смежностей.
5) Взависимости от количества введенных вершин производится разбиение экрана на N секторов относительно центраэкрана.
6) На граничныхлиниях секторов на одинаковом удалении от центра экрана выводим вершины.
7) Производимчтение из матрицы смежностей. Если связь между вершинами есть, то выводим наэкран отрезок, соединяющий одну вершину с другой, если связи нет — рассматриваемследующую связь. Если связь циклическая изменяем цвет вершины с зеленого накоричневый.
3. Распечаткапрограммы решения задачи
Program Graphs;
Uses Crt,Graph;
Const
M=25;{Предельное число вершин графа}
R=200;{Радиус окружности, на которой лежат вершины (центры окружностей)}
Type
Koor = Record
X,Y: Integer
End;
MasKoor = Array[1..M] Of Koor;
Smezno = Array[1..M,1..M] of Integer;
Var
Driver, Mode,
N,I,J:Integer; {Количество вершинграфа}
A: MasKoor;
B: Smezno;
ProcedureKoordinata; {Процедура задания координат вершин в зависимости от количествасекторов}
Var
Q,W:Real;
Begin
Writeln('Введитеколичество вершин графа: ');
Readln(N);
If N>M Then Halt;
Q:=6.28/N;
{Заданиекоординат вершин графа}
For I:=1 To N Do
Begin
W:=I*Q;
A[I].X:=300+Trunc(R*cos(W));
A[I].Y:=235+Trunc(R*sin(W));
End
End;
Procedure Vivod; {Выводвершинграфанаэкранмонитора}
Begin
For I:=1 To N Do
Begin
SetBkColor(0);
SetColor(2);
For J:=1 To 10 Do
Circle(A[I].X,A[I].Y,J)
End
End;
Procedure Smegnost; {Процедуразаданияматрицысмежностей}
Begin
For I:=1 To N Do
For J:=1 To N Do
B[I,J]:=9;
If N>7 Then
For I:=1 To N Do
For J:=1 To N Do
B[I,J]:=Random(3)
else
Begin
For I:=1 To N Do
For J:=1 To N Do
If B[I,J]=9 Then
Begin
Write('Введитесвязь[',I,',',J,']:= ');
Readln(B[I,J]);
B[J,I]:=B[I,J]
End
Else Writeln('Cвязь[',I,',',J,']:= ',B[I,J]);
End
End;
Procedure Linia;
Var K: Integer;
Begin
For I:=1 To N Do
For J:=1 To N Do
If (I=J) And (B[I,J]=2) Then {Циклическаясвязь}
Begin
SetColor(Brown);
For K:=1 To 10 Do
Circle(A[I].X,A[I].Y,K)
End else
If B[I,J]=1 Then {Обычнаясвязь}
Begin
SetColor(Red);
Line(A[I].X,A[I].Y,A[J].X,A[J].Y)
End
End;
{------------------------------------------------------------------}
Begin
ClrScr;
WriteLn('Вывод изображенияграфа на экран монитора');
Koordinata;
Smegnost;
Readln; {Задержкаэкрана}
Driver:=Detect;
InitGraph(Driver,Mode,'Egavga.bgi'); {Подключениеграфическогорежима}
Vivod;
Linia;
Readln;
Closegraph;{Отключение графического режима}
End.
неориентированныйграф вершина матрица
4. Результаты работыпрограммы для числа вершин равного 6Матрица смежностей вершин A B C D E F A 1 1 B 1 1 1 C 1 1 1 D 1 1 2 1 E 1 2 F 1 1 1 2
/>