Описание программного кода
Прикладная программа Max_potоk написана языком Object Pascal в интегрированной среде Delphi7.
Окно программы (Form1: TForm) содержит такие компоненты:
- текстовые поля (Eij: TEdit ; Inij: TEdit (i,j = 1..10));
– компоненты (STy: TStaticText (y = 1..10), OSTx: TStaticText (x = 1..10), VSTz: TStaticText (z = 1..10), OVSTe: TStaticText (e = 1..10), StaticTextij: TStaticText (i = 4, j = 1..4));
- надписи (Label1, Label2, Label3: TLabel);
- панель группировки компонентов (GB1: TGroupBox);
- кнопки (Buttonk: TButton (k = 1..5)).
В программе отслеживается 7 действий (табл. 6).
Таблица 6
Название действия | Назначение |
TButton1.Click | Рассчитывает максимальный поток |
TButton2.Click | Создаёт таблицы матриц пропускных способностей и потока заданной размерности |
TButton3.Click | Считает одну итерацию |
TButton4.Click | Выводит пометки |
TButton5.Click | Начинает итерацию заново |
TForm1.Create | Задаёт высоту и ширину окна программы |
TForm1.Close | Совершает затухание формы при её закрытии |
Предназначение текстовых полей приведено в таблице 7.
Метка поля | Название поля | Предназначение |
Количество | Col | Задаётся количество вершин сети |
s= | SSS | Задаётся источник сети |
t= | TTT | Задаётся сток сети |
Вершина | р1 | Задаётся вершина, пометки которой будут рассчитываться |
Предыдущая вершина | р2 | Выводятся пометки вершины |
Знак | р3 | |
d | р4 | |
Максимальный поток | max | Выводится максимальный поток сети |
Xij | Inij | Задаётся матрица пропускных способностей сети |
Xij | Eij | Выводится матрица потока в сети |
Таблица 7
ВЫВОДЫ
Решая жизненные практические задачи, мы неоднократно сталкиваемся с проблемой поиска максимальных потоков в сетях (поиск максимального потока машин в сети дорог без возникновения пробок, поиск максимального количества нефти, которую можно перекачать по трубопроводу и др.).
В данной работе изучалась эта проблема, была рассмотрена теория, которая изучает методы поиска максимальных потоков в сетях, изучен алгоритм поиска максимального потока (алгоритм Форда-Фалкерсона), в интегрированной среде Delphi было разработано дополнение, которое позволяет в удобной для пользователя форме найти максимальный поток в заданной сети.
Это дополнение может быть использовано при проведении практических занятий по теме ”Теория графов” для студентов специальностей “Математика” и “Информатика” при изучении дисциплины “Дискретная математика”, а также для проверки тестовых заданий по этой теме.
ЛИТЕРАТУРА
1. Алгоритмы и программы решения задач на графах и сетях. Отв. ред. М.И. Нечепуренко. –Новосибирск: Наука. Сиб. отделение, 1990. – 513 с.
2. Андрійчук В.І., Комарницький М.Я., Іщук Ю.Б. Вступ до дискретної математики: Навчальний посібник. – Київ: Центр навчальної літератури, 2004. – 254 с.
3. Архангельский А.Я. Приемы программирования в Delphi. Версии 5 – 7. М.: ЗАО «Издательство БИНОМ», 2003.
4. Дискретна математика: Підручник/ Ю.М. Бардачов, Н.А. Соколова, В.Є. Ходаков; за ред. В.Є. Ходакова. – К.: Вища шк., 2002. – 287 с.: іл.
5. Дискретная математика: логика, группы, графы/ О.Е. Акимов. – 2-е изд., доп. – М.: Лаборатория Базовых Знаний, 2003. – 376 с.: ил.
6. Зыков А.А. Основы теории графов. – М.: Наука, 1987. – 381 с.
7. Климова Л.М. Delphi 7. Основы программирования. Решение типовых задач. Самоучитель – М.: КУДИЦ-ОБРАЗ, 2004. – 480 с.
8. Крістофідес Р. “Теория графов”. Переклад на російську мову “Мир” 1978.
9. Лекции по дискретной математике/ Ю.В. Капитонова, С.Л. Кривой, А.А. Летичевский и др. – СПб.: БХВ-Петербург, 2004. – 624 с.
10. Лекции по теории графов/ Емеличев В.А., Мельниченков О.И., Сарванов В.И., Тышкевич Р.И. – М.: Наука, Гл. ред. физ.-мат. лит., 1990. – 384 с.
11. Лекции по теории графов: Учебн. пособие. – М.: Наука, 1990. – 384 с.
12. Липский В. Комбинаторика для программистов: Пер. с польск. – М.: Мир, 1988. – 213 с.: ил.
13. Магрупов Т.М. Графы, сети, алгоритмы и их приложения/ Под ред. Ф.Б. Абуталиева; АН УсССР, Ин-т кибернетики с ВЦ УзНПО “Кибернетика”: – Ташкент: Фан, 1990. – 120 с.
14. Математическое программирование (с элементами информационных технологий): Учеб. пособие для студ. нематемат. спец. вузов/ В.Р. Кулян, Е.А. Юнькова, А.Б. Жильцов. – К.: МАУП, 2000. – 124 с.: ил.
15. Мiхайленко В.М. Дискретна математика. – К.: Європейський ун-т, 2003. – 319.
16. Новиков Ф.А. Дискретная математика для программистов. – СПб.: Питер, 2004. – 302 с.: ил.
17. Седжвік Д. “Програмирование на С++. Часть 5. Алгоритмы на графах”. Київ, 2003.
18. Теория графов и её применение: сборник научных трудов/ Институт математики им. С.Л. Соболева. – Новосибирск, 1996. – 106 с.
19. Яблонский С.В. Введение в дискретную митематику. – М.: Наука, 1986. – 384 с.
ПРИЛОЖЕНИЕ
unit Unit1;
interface
uses
Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,
Dialogs, Grids, DBGrids, AxCtrls, OleCtrls, VCF1, ComCtrls, StdCtrls;
type
TForm1 = class(TForm)
E11: TEdit; E21: TEdit; E31: TEdit; E41: TEdit; E51: TEdit; E61: TEdit;
E71: TEdit; E81: TEdit; E91: TEdit; E101: TEdit; E12: TEdit; E22: TEdit;
E32: TEdit; E42: TEdit; E52: TEdit; E62: TEdit; E72: TEdit; E82: TEdit;
E92: TEdit; E102: TEdit; E13: TEdit; E23: TEdit; E33: TEdit; E43: TEdit;
E53: TEdit; E63: TEdit; E73: TEdit; E83: TEdit; E93: TEdit; E103: TEdit;
E14: TEdit; E24: TEdit; E34: TEdit; E44: TEdit; E54: TEdit; E64: TEdit;
E74: TEdit; E84: TEdit; E94: TEdit; E104: TEdit; E15: TEdit; E25: TEdit;
E35: TEdit; E45: TEdit; E55: TEdit; E65: TEdit; E75: TEdit; E85: TEdit;
E95: TEdit; E105: TEdit; E16: TEdit; E26: TEdit; E36: TEdit; E46: TEdit;
E56: TEdit; E66: TEdit; E76: TEdit; E86: TEdit; E96: TEdit; E106: TEdit;
E17: TEdit; E27: TEdit; E37: TEdit; E47: TEdit; E57: TEdit; E67: TEdit;
E77: TEdit; E87: TEdit; E97: TEdit; E107: TEdit; E18: TEdit; E28: TEdit;
E38: TEdit; E48: TEdit; E58: TEdit; E68: TEdit; E78: TEdit; E88: TEdit;
E98: TEdit; E108: TEdit; E19: TEdit; E29: TEdit; E39: TEdit; E49: TEdit;
E59: TEdit; E69: TEdit; E79: TEdit; E89: TEdit; E99: TEdit; E109: TEdit;
E110: TEdit; E210: TEdit; E310: TEdit; E410: TEdit; E510: TEdit;
E610: TEdit; E710: TEdit; E810: TEdit; E910: TEdit; E1010: TEdit;
In11: TEdit; In21: TEdit; In31: TEdit; In41: TEdit; In51: TEdit;
In61: TEdit; In71: TEdit; In81: TEdit; In91: TEdit; In101: TEdit;
In12: TEdit; In22: TEdit; In32: TEdit; In42: TEdit; In52: TEdit;
In62: TEdit; In72: TEdit; In82: TEdit; In92: TEdit; In102: TEdit;
In13: TEdit; In23: TEdit; In33: TEdit; In43: TEdit; In53: TEdit;
In63: TEdit; In73: TEdit; In83: TEdit; In93: TEdit; In103: TEdit;
In14: TEdit; In24: TEdit; In34: TEdit; In44: TEdit; In54: TEdit;
In64: TEdit; In74: TEdit; In84: TEdit; In94: TEdit; In104: TEdit;
In15: TEdit; In25: TEdit; In35: TEdit; In45: TEdit; In55: TEdit;
In65: TEdit; In75: TEdit; In85: TEdit; In95: TEdit; In105: TEdit;
In16: TEdit; In26: TEdit; In36: TEdit; In46: TEdit; In56: TEdit;
In66: TEdit; In76: TEdit; In86: TEdit; In96: TEdit; In106: TEdit;
In17: TEdit; In27: TEdit; In37: TEdit; In47: TEdit; In57: TEdit;
In67: TEdit; In77: TEdit; In87: TEdit; In97: TEdit; In107: TEdit;
In18: TEdit; In28: TEdit; In38: TEdit; In48: TEdit; In58: TEdit;
In68: TEdit; In78: TEdit; In88: TEdit; In98: TEdit; In108: TEdit;
In19: TEdit; In29: TEdit; In39: TEdit; In49: TEdit; In59: TEdit;
In69: TEdit; In79: TEdit; In89: TEdit; In99: TEdit; In109: TEdit;
In110: TEdit; In210: TEdit; In310: TEdit; In410: TEdit; In510: TEdit;
In610: TEdit; In710: TEdit; In810: TEdit; In910: TEdit; In1010: TEdit;
ST1: TStaticText; ST2: TStaticText; ST3: TStaticText; ST4: TStaticText;
ST5: TStaticText; ST6: TStaticText; ST7: TStaticText; ST8: TStaticText;
ST9: TStaticText; ST10: TStaticText; OST1: TStaticText;
OST4: TStaticText; OST3: TStaticText; OST2: TStaticText;
OST5: TStaticText; OST6: TStaticText; OST7: TStaticText;
OST8: TStaticText; OST9: TStaticText; OST10: TStaticText;
VST1: TStaticText; VST2: TStaticText; VST3: TStaticText;
VST4: TStaticText; VST5: TStaticText; VST6: TStaticText;
VST7: TStaticText; VST8: TStaticText; VST9: TStaticText;
VST10: TStaticText; OVST1: TStaticText; OVST2: TStaticText;
OVST3: TStaticText; OVST4: TStaticText; OVST5: TStaticText;
OVST6: TStaticText; OVST7: TStaticText; OVST8: TStaticText;
OVST9: TStaticText; OVST10: TStaticText; SSS: TEdit;
StaticText41: TStaticText; TTT: TEdit; StaticText42: TStaticText;
Button1: TButton; StaticText43: TStaticText; StaticText44: TStaticText;
col: TEdit; label1: TLabel; Button2: TButton; Label2: TLabel;
max: TEdit; Button3: TButton; GB1: TGroupBox; Label3: TLabel;
Label4: TLabel; Label5: TLabel; Label6: TLabel; p1: TEdit;
p2: TEdit; p3: TEdit; p4: TEdit; Button4: TButton; Button5: TButton;
procedure Button1Click(Sender: TObject);
procedure Button2Click(Sender: TObject);
procedure FormClose(Sender: TObject; var Action: TCloseAction);
procedure FormCreate(Sender: TObject);
procedure Button3Click(Sender: TObject);
procedure Button4Click(Sender: TObject);
procedure Button5Click(Sender: TObject);
private
{ Private declarations }
public
{ Public declarations }
end;
function min(x,y: double): double;
const p1=10;
type
sign=(minus,plus);
ibool=0..1;
Rec=record
s:sign; {направление дуги}
n:1..p1; {предшествующая вершина в аугментальной цепи}
delta:double; {величина возможного увеличения потока}
end;
var
Form1: TForm1;
F: array of array of double;
P: array of Rec;
implementation
{$R *.dfm}
function min(x,y: double): double;
begin
if x < y then
Result := x
else
Result := y;
end;
procedure TForm1.Button1Click(Sender: TObject);
label M;
const p1=10;
type
sign=(minus,plus);
ibool=0..1;
Rec=record
s:sign; {направление дуги}
n:1..p1; {предшествующая вершина в аугментальной цепи}
delta:double; {величина возможного увеличения потока}
end;
var i,j: integer;
del,ch:double;
C,F: array of array of double;
P: array of Rec;
N,S: array of ibool;
a:ibool;
pp,s1,t1,x: byte;
input,output:array of array of TEdit;
begin
pp:=StrToInt(col.Text);
SetLength(input,pp);
SetLength(output,pp);
SetLength(C,pp);
SetLength(F,pp);
SetLength(P,pp);
SetLength(N,pp);
SetLength(S,pp);
for i:=0 to pp-1 do
begin
SetLength(input[i],pp);
SetLength(output[i],pp);
SetLength(C[i],pp);
SetLength(F[i],pp);
end;
for i:=1 to pp do
for j:=1 to pp do
begin
F[i-1,j-1] := 0; {вначале поток нулевой}
input[i-1,j-1]:=FindComponent(Format('In%d%d',[i,j])) as TEdit;
output[i-1,j-1]:=FindComponent(Format('E%d%d',[i,j])) as TEdit;
if input[i-1,j-1].Text<>'' then C[i-1,j-1]:=StrToFloat(input[i-1,j-1].Text)
else C[i-1,j-1]:=0;
end;
s1 := StrToInt(SSS.Text[2]);
if (s1=1) and (length(SSS.Text)=3) then
s1:=10;
t1 := StrToInt(TTT.Text[2]);
if (t1=1) and (length(TTT.Text)=3) then
t1:=10;
M: {итерация увеличения потока}
for i:=1 to pp do
begin
S[i-1] := 0;
N[i-1] := 0;
with P[i-1] do
begin
//s := null;
//n := nil;
delta := 0;
end;
end;
S[s1-1]:=1;
with P[s1-1] do
begin
s:=plus;
n:=s1;
end;
repeat
a:=0; {признак расширения S}
for i:=1 to pp do
begin
if (S[i-1]=1) and (N[i-1]=0) then
begin
for j:=1 to pp do
begin
if C[i-1,j-1]<>0 then
begin
if (S[j-1]=0) and (F[i-1,j-1] < C[i-1,j-1]) then
begin
S[j-1] := 1;
with P[j-1] do
begin
s := plus;
n := i;
if i=s1 then delta := C[i-1,j-1] - F[i-1,j-1]
else delta := min(P[i-1].delta,C[i-1,j-1] - F[i-1,j-1]);
end;
a := 1;
end;
end;
if C[j-1,i-1]<>0 then
begin
if (S[j-1]=0) and (F[j-1,i-1]>0) then
begin
S[j-1] := 1;
with P[j-1] do
begin
s := minus;
n := i;
if i=s1 then delta := F[j-1,i-1]
else delta := min(P[i-1].delta,F[j-1,i-1]);
end;
a:=1;
end;
end;
end;
N[i-1] := 1;
end;
end;
if S[t1-1]<>0 then
begin
x:=t1;
del:=P[t1-1].delta;
while x<>s1 do
begin
if P[x-1].s=plus then
F[P[x-1].n-1,x-1]:=F[P[x-1].n-1,x-1]+del
else
F[x-1,P[x-1].n-1]:=F[x-1,P[x-1].n-1]-del;
x:=P[x-1].n
end;
goto M;
end;
until a=0;
ch:=0;
for i:=1 to pp do
begin
ch:=ch+F[s1-1,i-1];
for j:=1 to pp do
begin
if C[i-1,j-1]<>0 then
output[i-1,j-1].Text := FloatToStr(F[i-1,j-1])
else
output[i-1,j-1].Text := '';
end;
end;
max.Text := FloatToStr(ch);
end;
//----------------------------------------------------
procedure TForm1.Button2Click(Sender: TObject);
const p1=10;
var InG,InV,OutG,OutV :array[1..p1] of TStaticText;
i,pp,j: byte;
input,output:array[1..p1,1..p1] of TEdit;
begin
SSS.Text:='';
TTT.Text:='';
max.Text:='';
pp:=StrToInt(Col.Text);
SetLength(F,pp);
for i:=1 to pp do
begin
SetLength(F[i-1],pp);
for j:=1 to pp do
F[i-1,j-1] := 0;
end;
for i:=1 to p1 do
begin
InG[i] := FindComponent(Format('ST%d',[i])) as TStaticText;
InV[i] := FindComponent(Format('VST%d',[i])) as TStaticText;
OutG[i] := FindComponent(Format('OST%d',[i])) as TStaticText;
OutV[i] := FindComponent(Format('OVST%d',[i])) as TStaticText;
if i<=pp then
begin
InG[i].Visible:=true;
InV[i].Visible:=true;
OutG[i].Visible:=true;
OutV[i].Visible:=true;
end
else
begin
InG[i].Visible:=false;
InV[i].Visible:=false;
OutG[i].Visible:=false;
OutV[i].Visible:=false;
end;
for j:=1 to p1 do
begin
input[i,j] := FindComponent(Format('In%d%d',[i,j])) as TEdit;
output[i,j] := FindComponent(Format('E%d%d',[i,j])) as TEdit;
if (i<=pp) and (j<=pp) then
begin
input[i,j].Visible:=true;
output[i,j].Visible:=true;
input[i,j].Text:='';
output[i,j].Text:='';
end
else
begin
input[i,j].Visible:=false;
output[i,j].Visible:=false;
end;
end;
end;
end;
procedure TForm1.FormClose(Sender: TObject; var Action: TCloseAction);
var
i, cavb : 0..255;
begin
if AlphaBlend=False then
begin
AlphaBlendValue:=255;
AlphaBlend:=True;
end;
cavb:=AlphaBlendValue;
for i := cavb downto 0 do
begin
AlphaBlendValue := i;
Application.ProcessMessages;
end
end;
procedure TForm1.FormCreate(Sender: TObject);
begin
Form1.Height:=600;
Form1.Width:=800;
end;
procedure TForm1.Button3Click(Sender: TObject);
var i,j: integer;
del:double;
C: array of array of double;
N,S: array of ibool;
a:ibool;
pp,s1,t1,x: byte;
input,output:array of array of TEdit;
begin
p1.Text :='';
p2.Text :='';
p3.Text :='';
p4.Text :='';
pp:=StrToInt(col.Text);
SetLength(input,pp);
SetLength(output,pp);
SetLength(C,pp);
SetLength(P,pp);
SetLength(N,pp);
SetLength(S,pp);
for i:=0 to pp-1 do
begin
SetLength(input[i],pp);
SetLength(output[i],pp);
SetLength(C[i],pp);
end;
for i:=1 to pp do
for j:=1 to pp do
begin
input[i-1,j-1]:=FindComponent(Format('In%d%d',[i,j])) as TEdit;
output[i-1,j-1]:=FindComponent(Format('E%d%d',[i,j])) as TEdit;
if input[i-1,j-1].Text<>'' then C[i-1,j-1]:=StrToFloat(input[i-1,j-1].Text)
else C[i-1,j-1]:=0;
end;
s1 := StrToInt(SSS.Text[2]);
if (s1=1) and (length(SSS.Text)=3) then
s1:=10;
t1 := StrToInt(TTT.Text[2]);
if (t1=1) and (length(TTT.Text)=3) then
t1:=10;
for i:=1 to pp do
begin
S[i-1] := 0;
N[i-1] := 0;
with P[i-1] do
begin
//s := null;
//n := nil;
delta := 0;
end;
end;
S[s1-1]:=1;
with P[s1-1] do
begin
s:=plus;
n:=s1;
end;
repeat
a:=0; {признак расширения S}
for i:=1 to pp do
begin
if (S[i-1]=1) and (N[i-1]=0) then
begin
for j:=1 to pp do
begin
if C[i-1,j-1]<>0 then
begin
if (S[j-1]=0) and (F[i-1,j-1] < C[i-1,j-1]) then
begin
S[j-1] := 1;
with P[j-1] do
begin
s := plus;
n := i;
if i=s1 then delta := C[i-1,j-1] - F[i-1,j-1]
else delta := min(P[i-1].delta,C[i-1,j-1] - F[i-1,j-1]);
end;
a := 1;
end;
end;
if C[j-1,i-1]<>0 then
begin
if (S[j-1]=0) and (F[j-1,i-1]>0) then
begin
S[j-1] := 1;
with P[j-1] do
begin
s := minus;
n := i;
if i=s1 then delta := F[j-1,i-1]
else delta := min(P[i-1].delta,F[j-1,i-1]);
end;
a:=1;
end;
end;
end;
N[i-1] := 1;
end;
end;
if S[t1-1]<>0 then
begin
x:=t1;
del:=P[t1-1].delta;
while x<>s1 do
begin
if P[x-1].s=plus then
F[P[x-1].n-1,x-1]:=F[P[x-1].n-1,x-1]+del
else
F[x-1,P[x-1].n-1]:=F[x-1,P[x-1].n-1]-del;
x:=P[x-1].n
end;
Break;
end;
until a=0;
for i:=1 to pp do
begin
for j:=1 to pp do
begin
if C[i-1,j-1]<>0 then
output[i-1,j-1].Text := FloatToStr(F[i-1,j-1])
else
output[i-1,j-1].Text := '';
end;
end;
end;
procedure TForm1.Button4Click(Sender: TObject);
var s1,ver: byte; // Вершина
begin
p4.Font.Name := 'MS Sans Serif';
ver := StrToInt(p1.Text[2]);
if (ver=1) and (length(p1.Text)=3) then
ver:=10;
s1 := StrToInt(SSS.Text[2]);
if (s1=1) and (length(SSS.Text)=3) then
s1:=10;
if P[ver-1].s=plus then p3.Text := '+'
else p3.Text := '-';
p2.Text := 'x' + IntToStr(P[ver-1].n);
if ver<>s1 then
p4.Text := FloatToStr(P[ver-1].delta)
else
begin
p4.Font.Name :='Symbol';
p4.Text := 'Ґ';
end;
end;
procedure TForm1.Button5Click(Sender: TObject);
var pp,i,j : integer;
output:array of array of TEdit;
begin
pp:=StrToInt(Col.Text);
SetLength(F,pp);
SetLength(output,pp);
for i:=1 to pp do
begin
SetLength(output[i-1],pp);
SetLength(F[i-1],pp);
for j:=1 to pp do
begin
F[i-1,j-1] := 0;
output[i-1,j-1]:=FindComponent(Format('E%d%d',[i,j])) as TEdit;
output[i-1,j-1].Text := '';
end;
end;
end;
end.