Теория графов
Автор: Пользователь скрыл имя, 04 Марта 2015 в 21:30, курсовая работа
Краткое описание
Граф - совокупность точек и линий, в которой каждая линия соединяет две точки. Точки называются вершинами, или узлами, графа, линии - ребрами графа. Если ребро соединят две вершины, то говорят, что оно им инцидентно; вершины, соединенные ребром называются смежными. Две вершины, соединенные ребром, могут совпадать; такое ребро называется петлей. Число ребер, инцидентных вершине, называется степенью вершины
Оглавление
Элементы теории графов
Поиск в ширину
Поиск в глубину
Эйлеровы циклы
Задача Прима–Краскала
Алгоритм Дейкстры
Файлы: 1 файл
Курсовая работа по тис №1 (дисциплина) на тему- Теория графов и .doc
— 222.00 Кб (Скачать)
Uses Crt;
Const MaxSize=10;
Infinity=1000;
Var Mattr: array [1..MaxSize, 1..MaxSize] of integer;
Visited: array [1..MaxSize] of boolean;
Len,Path: array [1..MaxSize] of integer;
n, Start, Finish, k, i: integer;
Procedure Init;
Var f: text;
i, j: integer;
Begin
Assign(f, INPUT.MTR');
Reset(f);
Readln(f, n);
For i:=1 to n do
Begin
For j:=1 to n do Read(f, mattr[i,j]);
Readln(f)
End;
Write('Начальная вершина: '); Readln(Start);
For i:=1 to n do
Begin
Visited[i]:=False;
Len[i]:=Mattr[Start, i];
Path[i]:=Start
End;
Path[Start]:=0;
Visited[Start]:=True
End;
Function Possible: Boolean;
Var i: integer;
Begin
Possible:=True;
For i:=1 to n do If not Visited[i] then Exit;
Possible:=False
End;
Function Min: Integer;
Var i, minvalue, currentmin: integer;
Begin
Minvalue:=Infinity;
For i:=1 to n do
If not Visited[i] then
If Len[i]<minvalue then
Begin
currentmin:=i;
minvalue:=Len[i]
End;
min:=currentmin
End;
Begin
ClrScr;
Init;
While Possible do
Begin
k:=min;
Visited[k]:=True;
For i:=1 to n do
If Len[i]>Len[k]+Mattr[i, k] then
End
End;
Write('Конечная вершина: '); Readln(Finish);
Write(Finish);
Finish:=Path[Finish];
While Finish<>0 do
Begin
Write('<-', Finish);
Finish:=Path[Finish];
End;
ReadKey
End.
Например, для сети, описанной в предыдущей главе, кратчайший путь из 3-ей вершины в 8-ю будет: 8¬2¬3.
Список литературы.
- В помощь учителю математики", Йошкар-Ола, 1972 (ст. "Изучение элементов
теории графов");
- Олехник С. Н., Нестеренко Ю. В., Потапов М. К. "Старинные занимательные задачи", М. "Наука", 1988(часть 2, раздел 8; приложение 4);
- Гарднер М. "Математические головоломки и развлечения", М. "Мир", 1971;
- Оре О. "Графы и их применения", М. "Мир", 1965;