Автор работы: Пользователь скрыл имя, 06 Апреля 2011 в 04:53, курсовая работа
Теория графов – это область дискретной математики, особенностью которой является геометрический подход к изучению объектов. Теория графов находится сейчас в самом расцвете. Обычно её относят к топологии (во многих случаях рассматриваются лишь топологические свойства графов), однако она пересекается со многими разделами теории множеств, комбинаторной математики, алгебры, геометрии, теории матриц, теории игр, математической логики и многих других математических дисциплин.
Сети. Сеть вычислительных машин состоит из взаимосвязанных узлов, которые посылают, передают дальше и получают сообщения различных видов. Мы заинтересованы не только в обеспечении возможности получать сообщения из любого другого узла, но и в том, чтобы эта возможность сохранялась для всех пар узлов и в случае изменения конфигурации сети. Например, возможно, потребуется проверить работу конкретной сети, чтобы убедиться в отсутствии некоторого небольшого подмножества узлов или соединений, настолько критичного для работы всей сети, что его утрата может привести к разъединению остальных пар узлов.
Структура программы. Компилятор строит графы для представления структуры вызовов крупной системы программного обеспечения. Элементами в этом случае являются различные функции или программные модули, составляющие систему; соединения отождествляются либо с возможностью того, что одна функция может вызвать другую функцию (статический анализ), или с фактическим вызовом, когда система находится в рабочем состоянии (динамический анализ). Нам нужно выполнить анализ графа, чтобы определить, как достичь максимальной эффективности при выделении системных ресурсов для конкретной программы.
Эти примеры демонстрируют, насколько широк диапазон приложений, для которых граф служит подходящей абстракцией, и, соответственно, диапазон вычислительных задач, с которыми доведется столкнуться при работе с графами.
Модели графов, в которых с каждым ребром связывают веса или стоимости, используются во многих приложениях. В картах авиалиний, в которых ребрами отмечены авиарейсы, такие веса означают расстояния или стоимость проезда. В электронных схемах, где ребра представляют электрические соединения, веса могут означать длину соединения, его стоимость или время, необходимое для распространения по ней сигнала. В задачах календарного планирования веса могут представлять время или расходы, затрачиваемые на выполнение задач, либо время ожидания завершения соответствующей задачи. Естественно, в таких ситуациях возникают вопросы, касающиеся различных аспектов минимизации стоимости. Наиболее изучены алгоритмы решения двух задач такого рода:
1) Определение пути с наименьшей стоимостью, соединяющего все точки;
2)
Отыскание пути наименьшей
Первый тип алгоритма применяется для решения задач на неориентированных графах, которые представляют такие объекты как электрические цепи, находит минимальное остовное дерево. Второй тип алгоритма, применяемый для решения задач на орграфах, которые представляют такие объекты, как карты авиарейсов, определяет кратчайшие пути. Эти алгоритмы находят широкое применение не только в приложениях, связанных со схемами авиарейсов и электрическими схемами, они используются также и при решении задач, возникающих во взвешенных графах.
Задача
поиска минимального остовного дерева
произвольного взвешенного
Литература
Приложение
Реализация алгоритма Прима-Краскала на языке Паскаль
uses wincrt;
Const
N=5; {N - число вершин графа}
type
Matrix=array[1..N,1..N] of Integer; {матрица расстояний графа}
var
D,Ostov: Matrix; {D - матрица весов исходного графа, Ostov - матрица весов искомого остова}
color_of_top: array[1..N] of integer; {цвет вершин графа}
i,j,k,x,y,d_min: Integer; {d_min - текущая минимальная длина ребра}
ne_virozhd: Boolean;
BEGIN
ClrScr;
{Инициализируем граф - вводим матрицу весов графа D[i,j]}
for i:=1 to N do begin
WriteLn('Введите элементы ',i,'-й строки матрицы весов графа:');
WriteLn('Если вершины не связаны ребром - вводим любое отрицательное число');
for j:=1 to N do begin
Write('D[',i,',',j,']='); Read(D[i,j]);
end;
end;
{Выводим матрицу весов графа D[i,j]}
WriteLn;
WriteLn('Матрица весов графа:');
for i:=1 to N do begin
for j:=1 to N do begin
If D[i,j]>=0 then Write(D[i,j]:5) else Write(' x');
end;
WriteLn;
end;
{Инициализируем
матрицу остовного дерева
for i:=1 to N do
for j:=1 to N do
Ostov[i,j]:=0;
{"Раскрашиваем" вершины графа в разные цвета}
for i:=1 to N do
color_of_top[i]:=i;
k:=0; {k - число ребер остовного дерева}
ne_virozhd:=false;
{Общий шаг алгоритма}
while k<N-1 do begin
{Задаем первоначальное значение длины искомого ребра, заведомо большее всех имеющихся у графа}
d_min:= 30000;
{Находим ребро минимальной длины, не включенное до этого в остов графа}
for i:=1 to N-1 do
for j:=i+1 to N do
if (i<>j)and(D[i,j]>0) and (D[i,j]<d_min) and (color_of_top[i]<>color_of_
begin
d_min:=D[i,j];
x:=i;
y:=j;
ne_virozhd:=true;
end;
if ne_virozhd=true then begin
{Включаем найденное ребро минимальной длины в остов}
Ostov[x,y]:=D[x,y];
{Меняем цвет всех вершин, входящих в остов, на один цвет}
for i:=1 to N do
if color_of_top[i] = y then color_of_top[i] := x;
end;
{Увеличиваем количество рассмотренных ребер}
k:=k+1;
end;
{Выводим матрицу весов остова}
WriteLn;
WriteLn('Искомая матрица весов остова:');
for i:=1 to N do begin
for j:=1 to N do begin
If Ostov[i,j]>0 then Write(Ostov[i,j]:5) else Write(' x');
end;
WriteLn;
end;
END.