Нахождение кратчайшего пути
end;
end.
Рабочее поле программы предназначено для визуального ввода графов.
Рабочее поле с введенным графом выглядит следующим образом:

ЗАКЛЮЧЕНИЕ
Теория графов находит широкое применение в различных областях науки и техники:
Графы и информация
Двоичные деревья играют весьма важную роль в теории информации. Предположим, что определенное число сообщений требуется закодировать в виде конечных последовательностей различной длины, состоящих из нулей и единиц. Если вероятности кодовых слов заданы, то наилучшим считается код, в котором средняя длина слов минимальна по сравнению с прочими распределениями вероятности. Задачу о построении такого оптимального кода позволяет решить алгоритм Хаффмана.
Двоичные кодовые деревья допускают интерпретацию в рамках теории поиска. Каждой вершине при этом сопоставляется вопрос, ответить на который можно либо "да", либо "нет". Утвердительному и отрицательному ответу соответствуют два ребра, выходящие из вершины. "Опрос" завершается, когда удается установить то, что требовалось.
Таким образом, если кому-то понадобится взять интервью у различных людей, и ответ на очередной вопрос будет зависеть от заранее неизвестного ответа на предыдущий вопрос, то план такого интервью можно представить в виде двоичного дерева.
Графы и химия
Еще А. Кэли рассмотрел задачу о возможных структурах насыщенных (или предельных) углеводородов, молекулы которых задаются формулой:
CnH2n+2
Молекула каждого предельного углеводорода представляет собой дерево. Если удалить все атомы водорода, то оставшиеся атомы углеводорода также будут образовывать дерево, каждая вершина которого имеет степень не выше 4. Следовательно, число возможных структур предельных углеводородов, т. е. число гомологов данного вещества, равно числу деревьев с вершинами степени не больше четырех.
Таким образом, подсчет числа гомологов предельных углеводородов также приводит к задаче о перечислении деревьев определенного типа. Эту задачу и ее обобщения рассмотрел Д. Пойа.
Графы и биология
Деревья играют большую роль в биологической теории ветвящихся процессов. Для простоты мы рассмотрим только одну разновидность ветвящихся процессов – размножение бактерий. Предположим, что через определенный промежуток времени каждая бактерия либо делится на две новые, либо погибает. Тогда для потомства одной бактерии мы получим двоичное дерево.
Нас будет интересовать лишь один вопрос: в скольких случаях n-е поколение одной бактерии насчитывает ровно k потомков? Рекуррентное соотношение, обозначающее число необходимых случаев, известно в биологии под названием процесса Гальтона-Ватсона. Его можно рассматривать как частный случай многих общих формул.
Графы и физика
Еще недавно одной из наиболее сложных и утомительных задач для радиолюбителей было конструирование печатных схем.
Печатной схемой называют пластинку из какого-либо диэлектрика (изолирующего материала), на которой в виде металлических полосок вытравлены дорожки. Пересекаться дорожки могут только в определенных точках, куда устанавливаются необходимые элементы (диоды, триоды, резисторы и другие), их пересечение в других местах вызовет замыкание электрической цепи.
В ходе решения этой задачи необходимо вычертить плоский граф, с вершинами в указанных точках.
Итак, из всего вышесказанного неопровержимо следует практическая ценность теории графов.
СПИСОК ЛИТЕРАТУРЫ
Белов Теория Графов, Москва, «Наука»,1968.
Новые педагогические и информационные технологии Е.С.Полат, Москва, «Akademia» 1999 г.
Кузнецов О.П., Адельсон-Вельский Г.М. Дискретная математика для инженера. – М.: Энергоатомиздат, 1988.
Кук Д., Бейз Г. Компьютерная математика. – М.: Наука, 1990.
Нефедов В.Н., Осипова В.А. Курс дискретной математики. – М.: Издательство МАИ, 1992.
Оре О. Теория графов. – М.: Наука, 1980.
Исмагилов Р.С., Калинкин А.В. Матеpиалы к пpактическим занятиям по куpсу: Дискpетная математика по теме: Алгоpитмы на гpафах. - М.: МГТУ, 1995
Смольяков Э.Р. Введение в теоpию гpафов. М.: МГТУ, 1992
Hечепуpенко М.И. Алгоpитмы и пpогpаммы pешения задач на гpафах и сетях. - Hовосибиpск: Hаука, 1990
Романовский И.В. Алгоpитмы pешения экстpемальных задач. - М.: Hаука, 1977
Писсанецки С. Технология разреженных матриц. - М.: Мир, 1988
Севастьянов Б.А. Вероятностные модели. - М.: Наука, 1992
Бочаров П.П., Печинкин А.В. Теория вероятностей. - М.: Изд-во РУДН, 1994
ПРИЛОЖЕНИЕ
Текст программы определения кратчайшего пути в графе
Модуль управления интерфейсом программы:
unit MainUnit;
interface
uses
Windows, Messages, SysUtils, Classes, Graphics, Controls, Forms, Dialogs,
StdCtrls,PaintingGraph, ComCtrls, ToolWin, ImgList, Menus,
ActnList, ExtCtrls;
const
crMyCursor = 5;
type
TForm1 = class(TForm)
SaveDialog1: TSaveDialog;
OpenDialog1: TOpenDialog;
ImageList1: TImageList;
ImageList2: TImageList;
LoadMenu: TPopupMenu;
ControlBar1: TControlBar;
ToolBar3: TToolBar;
OpenButton: TToolButton;
SaveButton: TToolButton;
ToolButton15: TToolButton;
ClearButton: TToolButton;
UpdateButton: TToolButton;
HelpButton: TToolButton;
ToolButton26: TToolButton;
RemovePointButton: TToolButton;
ToolButton28: TToolButton;
ToolButton32: TToolButton;
SettingButton: TToolButton;
ControlBar2: TControlBar;
AlgoritmToolBar: TToolBar;
KommiTool: TToolButton;
ToolButton: TToolButton;
NotFarButton: TToolButton;
MinLengthButton: TToolButton;
ToolButton5: TToolButton;
MovePointButton: TToolButton;
ActionList1: TActionList;
AShowGrig: TAction;
ASnapToGrid: TAction;
ASave: TAction;
ALoad: TAction;
ADelete: TAction;
GridToolBar: TToolBar;
Clock: TLabel;
Timer1: TTimer;
ShowGridButton: TToolButton;
AutoLengthButton: TToolButton;
SnapToGridButton: TToolButton;
PaintBox1: TPaintBox;
procedure FormMouseDown(Sender: TObject; Button: TMouseButton;
Shift: TShiftState; X, Y: Integer);
procedure FormCreate(Sender: TObject);
procedure FormMouseMove(Sender: TObject; Shift: TShiftState; X,
Y: Integer);
procedure FormPaint(Sender: TObject);
procedure FormKeyDown(Sender: TObject; var Key: Word;
Shift: TShiftState);
procedure ClearButtonClick(Sender: TObject);
procedure KommiToolButtonClick(Sender: TObject);
procedure PaintingToolButtonClick(Sender: TObject);
procedure SnapToGridButtonClick(Sender: TObject);
procedure HelpButtonClick(Sender: TObject);
procedure AutoLengthButtonClick(Sender: TObject);
procedure SettingButtonClick(Sender: TObject);
procedure NotFarButtonClick(Sender: TObject);
procedure MinLengthButtonClick(Sender: TObject);
procedure MovePointButtonClick(Sender: TObject);
procedure RemovePointButtonClick(Sender: TObject);
procedure Timer1Timer(Sender: TObject);
procedure ALoadExecute(Sender: TObject);
procedure AShowGrigExecute(Sender: TObject);
procedure ASaveExecute(Sender: TObject);
procedure PaintBox1Paint(Sender: TObject);
procedure UpdateButtonClick(Sender: TObject);
procedure EilerButtonClick(Sender: TObject);
procedure ClockClick(Sender: TObject);
private
procedure MyPopupHandler(Sender: TObject);
{ Private declarations }
public
{ Public declarations }
end;
var
Form1: TForm1;
implementation
uses IO,Data,Commercial,DrawingObject,Setting,NotFar,MinLength, Eiler,
SplashScreen;
{$R *.DFM}
procedure TForm1.FormMouseDown(Sender: TObject; Button: TMouseButton;
Shift: TShiftState; X, Y: Integer);
begin
if Button=mbLeft then begin
MyIO.FormMouseDown( X, Y);
if (MyIO.State=msMove)then
if MyIO.FirstPointActive then
Cursor := crMyCursor
else begin
Repaint;
Cursor := crDefault;
end;
end
else
MyIO.MakeLine(X, Y);
end;
procedure TForm1.FormCreate(Sender: TObject);
begin
Screen.Cursors[crMyCursor] := LoadCursor(HInstance, 'Shar');
MyIO:=TIO.Create(PaintBox1.Canvas);
MyData:=TData.Create;
MyDraw:=TDrawingObject.Create(PaintBox1.Canvas);
SaveDialog1.InitialDir:=ExtractFilePath(Application.ExeName)+'Grafs';
OpenDialog1.InitialDir:=ExtractFilePath(Application.ExeName)+'Grafs';
end;
procedure TForm1.FormMouseMove(Sender: TObject; Shift: TShiftState; X,
Y: Integer);
begin
MyIO.DrawLine(x,y);
end;
procedure TForm1.FormPaint(Sender: TObject);
begin
PaintBox1Paint(Sender);
end;
procedure TForm1.FormKeyDown(Sender: TObject; var Key: Word;
Shift: TShiftState);
begin
if (Key=vk_Escape) then
begin
MyData.Remove(MyData.Dimension);
MyDraw.Remove(MyData.Dimension);
Repaint;
end;
end;
procedure TForm1.MyPopupHandler(Sender: TObject);
var s:string;
begin
with Sender as TMenuItem do begin
s:=Caption;
MyData.Load(s);
System.Delete(s,length(s)-4,5);
MyDraw.Load(s+'.pos');
end;
Repaint;
end;
procedure TForm1.ClearButtonClick(Sender: TObject);
begin
MyData.Clear;
MyDraw.Clear;
Repaint;
end;
procedure TForm1.KommiToolButtonClick(Sender: TObject);
begin
If MyData.Dimension<2 then Exit;
MyCommercial:=TCommercial.Create;
MyCommercial.Make;
MyCommercial.Free;
end;
procedure TForm1.EilerButtonClick(Sender: TObject);
begin
If MyData.Dimension<2 then Exit;
EilerC:=TEiler.Create;
EilerC.Make;
EilerC.Free;
MyIO.DrawAll;
RePaint;
end;
procedure TForm1.PaintingToolButtonClick(Sender: TObject);
begin
If MyData.Dimension<2 then Exit;
MyPaint:=TPaintingGraphClass.Create;
MyPaint.Make;
RePaint;
MyPaint.Free;
end;
procedure TForm1.SnapToGridButtonClick(Sender: TObject);
begin
MyIO.FSnapToGrid:=SnapToGridButton.Down;
end;
procedure TForm1.HelpButtonClick(Sender: TObject);
begin
Application.HelpContext(10);
end;
procedure TForm1.AutoLengthButtonClick(Sender: TObject);
begin
MyIo.AutoLength:=AutoLengthButton.Down;
end;
procedure TForm1.SettingButtonClick(Sender: TObject);
begin
SettingForm.Show;
end;
procedure TForm1.NotFarButtonClick(Sender: TObject);
begin
If MyData.Dimension<2 then Exit;
MyNotFar:=TNotFar.Create;
MyNotFar.Make;
MyNotFar.Free;
end;
procedure TForm1.MinLengthButtonClick(Sender: TObject);
begin
If MyData.Dimension<2 then Exit;
MyMinLength:=TMinLength.Create;
MyMinLength.Make;
MyMinLength.Free;
end;
procedure TForm1.MovePointButtonClick(Sender: TObject);
begin
if MovePointButton.Down then MyIO.State:=msMove else
MyIO.State:=msNewPoint;
if MovePointButton.Down=false then
Cursor := crDefault;
end;
procedure TForm1.RemovePointButtonClick(Sender: TObject);
begin
if ReMovePointButton.Down then MyIO.State:=msDelete else
MyIO.State:=msNewPoint;
Repaint;
end;
procedure TForm1.Timer1Timer(Sender: TObject);
begin
Clock.Caption:=TimeToStr(Time);
end;
procedure TForm1.ALoadExecute(Sender: TObject);
var s:string;
begin
if OpenDialog1.Execute then
try
s:=OpenDialog1.Filename;
MyData.Load(s);
Delete(s,length(s)-4,5);
MyDraw.Load(s+'.pos');
finally
end;
Repaint;
end;
procedure TForm1.AShowGrigExecute(Sender: TObject);
begin
MyIO.FDrawGrid:=ShowGridButton.Down ;
Repaint;
end;
procedure TForm1.ASaveExecute(Sender: TObject);
var s:string;
m:TMenuItem;
begin
if SaveDialog1.Execute then
try
s:=SaveDialog1.Filename;
MyData.Save(s);
Delete(s,length(s)-4,5);
MyDraw.Save(s+'.Pos')
finally
end;
m:=TMenuItem.Create(Self);
m.Caption:=SaveDialog1.Filename;
m.OnClick := MyPopUpHandler;
LoadMenu.Items.Add(m);
end;
procedure TForm1.PaintBox1Paint(Sender: TObject);
begin
MyIO.DrawCoordGrid(16,16,ClientWidth-30,ClientHeight-140);
MyIO.DrawAll;
end;
procedure TForm1.UpdateButtonClick(Sender: TObject);
begin
MyDraw.SetAllUnActive;
MyIO.DrawAll;
MyIO.FirstPointActive:=false;
end;
procedure TForm1.ClockClick(Sender: TObject);
begin
Splash.Show;
end;
end.
Модуль управления окном настроек:
unit Setting;
interface
uses
Windows, Messages, SysUtils, Classes, Graphics, Controls, Forms, Dialogs,
Buttons, StdCtrls, Spin,IO,MainUnit, ExtCtrls;
type
TSettingForm = class(TForm)
GridGroupBox: TGroupBox;
Label1: TLabel;
Label2: TLabel;
ColorDialog1: TColorDialog;
Label3: TLabel;
OkBitBtn: TBitBtn;
CancelBitBtn: TBitBtn;
ColorButton: TPanel;
Label4: TLabel;
Label5: TLabel;
CoordCheckBox: TCheckBox;
GridCheckBox: TCheckBox;
StepSpinEdit: TSpinEdit;
MashtabSpinEdit: TSpinEdit;
Colors: TGroupBox;
Panel1: TPanel;
Panel2: TPanel;
Panel3: TPanel;
Label6: TLabel;
Label7: TLabel;
Label8: TLabel;
procedure ColorButtonClick(Sender: TObject);
procedure OkBitBtnClick(Sender: TObject);
procedure FormShow(Sender: TObject);
procedure FormClose(Sender: TObject; var Action: TCloseAction);
procedure CoordCheckBoxClick(Sender: TObject);
procedure GridCheckBoxClick(Sender: TObject);
procedure CancelBitBtnClick(Sender: TObject);
procedure Panel2Click(Sender: TObject);
private
{ Private declarations }
public
{ Public declarations }
end;
var
SettingForm: TSettingForm;
implementation
{$R *.DFM}
procedure TSettingForm.ColorButtonClick(Sender: TObject);
begin
if ColorDialog1.Execute then begin
ColorButton.Color:=ColorDialog1.Color;
MyIO.GridColor:=Color;
Form1.Repaint;
end;
end;
procedure TSettingForm.OkBitBtnClick(Sender: TObject);
begin
MyIO.GridColor:=ColorButton.Color;
MyIO.GrigStep:=StepSpinEdit.Value;
MyIO.Mashtab:=MashtabSpinEdit.Value;
Close;
end;
procedure TSettingForm.FormShow(Sender: TObject);
begin
with MyIO do begin
ColorButton.Color:=MyIO.GridColor;
StepSpinEdit.Value:=MyIO.GrigStep;
MashtabSpinEdit.Value:=MyIO.Mashtab;
CoordCheckBox.Checked:=MyIO.FDrawCoord;
GridCheckBox.Checked:=MyIO.FDrawGrid;
Panel2.Color:=RebroColor ;
Panel3.Color:=TextColor ;
Panel1.Color:=MovingColor ;
end;
end;
procedure TSettingForm.FormClose(Sender: TObject;
var Action: TCloseAction);
begin
with MyIO do begin
GridColor:=ColorButton.Color;
GrigStep:=StepSpinEdit.Value;
Mashtab:=MashtabSpinEdit.Value;
FDrawCoord:=CoordCheckBox.Checked;
FDrawGrid:=GridCheckBox.Checked;
Form1.ShowGridButton.Down:=GridCheckBox.Checked;
RebroColor:=Panel2.Color ;
TextColor:=Panel3.Color ;
MovingColor:=Panel1.Color ;
end;
Form1.Repaint;
end;
procedure TSettingForm.CoordCheckBoxClick(Sender: TObject);
begin
MyIO.FDrawCoord:=CoordCheckBox.Checked;
//Form1.Repaint;
end;
procedure TSettingForm.GridCheckBoxClick(Sender: TObject);
begin
MyIO.FDrawGrid:=GridCheckBox.Checked ;
//Form1.Repaint;
end;
procedure TSettingForm.CancelBitBtnClick(Sender: TObject);
begin
Close;
end;
procedure TSettingForm.Panel2Click(Sender: TObject);
begin
with Sender as TPanel do
if ColorDialog1.Execute then begin
Color:=ColorDialog1.Color;
end;
end;
end.
Вспомогательный модуль потроения графа в окне программы:
unit IO;
interface
uses Data,DrawingObject,Graphics,windows,Math,Controls,Dialogs,SysUtils;
type
MouseState=(msNewPoint,msLining,msMove,msDelete);
TIO=class
private
xt,yt,xs,ys: integer;
// FLining: boolean;
ActivePoint: integer;
MyCanvas: TCanvas;
public
GridColor: TColor;
RebroColor: TColor;
TextColor: TColor;
MovingColor: TColor;
State: MouseState;
FDrawGrid: boolean;
FDrawCoord: boolean;
FSnapToGrid: boolean;
GrigStep: integer;
FirstPoint: integer;
FirstPointActive: boolean;
LastPoint: integer;
AutoLength: boolean;
Mashtab: integer;
procedure MakeLine(X, Y: Integer);
procedure DrawPath(First,Last:integer;Light:boolean=false);
procedure IONewPoint(xPos,yPos:integer);
procedure DrawAll;
procedure FormMouseDown( X, Y: Integer);
procedure Select(FirstPoint,LastPoint:integer);
procedure DrawCoordGrid(x,y,x1,y1:integer);
procedure DrawLine(x1,y1:Integer);
procedure RemovePoint(Num:integer);
constructor Create(Canvas:TCanvas);
end;
var MyIO:TIO;
implementation
procedure TIO.MakeLine(X, Y: Integer);
var i:integer;
V1,V2:TPoint;
begin
i:=MyDraw.FindNumberByXY(X,Y);
if i<>-1 then
if State=msLining then begin
MyData.Rebro(ActivePoint,i);
if AutoLength then begin
V1:=MyDraw.FindByNumber(ActivePoint);
V2:=MyDraw.FindByNumber(i);
MyData.SetRebroLength(ActivePoint,i,Round(
sqrt(sqr(Mashtab*(V1.x-V2.x)/ GrigStep)+
sqr(Mashtab*(V1.y-V2.y)/ GrigStep))));
end;
MyCanvas.MoveTo(xs,ys);
MyCanvas.LineTo(xt,yt);
DrawPath(ActivePoint,i,false);
State:=msNewPoint;
MyDraw.SetUnActive(ActivePoint);
end
else begin
ActivePoint:=i;
State:=msLining;
xs:=MyDraw.FindByNumber(i).x; xt:=xs;
ys:=MyDraw.FindByNumber(i).y; yt:=ys;
MyDraw.SetActive(i);
end ;
end;
procedure TIO.DrawLine(x1,y1:Integer);
begin
if State=msLining then
with MyCanvas do
begin
Pen.Width:=2;
Pen.Color:=MovingColor;
Pen.Mode:=pmXor;
Pen.Style:=psSolid;
MoveTo(xs,ys);
LineTo(xt,yt);
MoveTo(xs,ys);
LineTo(x1,y1);
xt:=x1;
yt:=y1;
end;
{if State=msMove then
with MyCanvas do
begin
Pen.Width:=2;
Pen.Color:=MovingColor;
Pen.Mode:=pmXor;
Pen.Style:=psSolid;
MoveTo(xs,ys);
LineTo(xt,yt);
MoveTo(xs,ys);
LineTo(x1,y1);
xt:=x1;
yt:=y1;
end;}
end;
procedure TIO.FormMouseDown( X, Y: Integer);
var Mini,Maxi,i,j,Temp,Te:integer;
b,k:real;
Flag:Boolean;
function StepRound(Num,Step:integer):integer;
begin
if (Num mod Step)>(Step/2)then Result:=Num- Num mod Step+Step
else Result:=(Num div Step)*Step;
end;
begin
Te:=MyDraw.FindNumberByXY(X,Y);
if (Te=-1)and(state<>msMove) then
with MyData,MyDraw do begin
i:=1;
j:=1;
Flag:=false;
repeat
repeat
if (Dimension>0)and(Matrix[i,j]=1) then begin
Mini:=Min(FindByNumber(i).x,FindByNumber(j).x);
Maxi:=Max(FindByNumber(i).x,FindByNumber(j).x);
if Mini<>Maxi then
k:=(FindByNumber(i).y-FindByNumber(j).y)/(FindByNumber(i).x-FindByNumber(j).x)
else k:=0;
b:= FindByNumber(i).y- (k*FindByNumber(i).x) ;
if
(X>=Mini)and(X
( Y>=(k*X+b-8) )and ( Y<=(k*X+b+8))
then begin
Flag:=true;