Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
КН
Кафедра:
Кафедра СКС
Інформація про роботу
Рік:
2013
Тип роботи:
Звіт до лабораторної роботи
Предмет:
Дискретна математика
Частина тексту файла (без зображень, графіків і формул):
Міністерство освіти і науки України
Національний університет „Львівська політехніка”
Кафедра СКС
Звіт
з лабораторної роботи № 3
з дисципліни: “Дискретна матетематика”
Львів 2013
Мета: навчитися створювати програму яка обчислює задачу про кістякове дерево екстремальної (мінімальної або максимальної) ваги
Теоретичні відомості
Діяльність сучасного суспільства тісно пов’язана з різного роду сітками – наприклад, транспорт, комунікації, розподіл товарів і т. д. математичний аналіз таких сіток став предметом фундаментальної важливості. В даній лабораторній роботі на прикладах показано, що аналіз сіток по суті еквівалентний вивченню орфографії.
Завод електричних масажних щіток хотів би надіслати на даний ринок декілька ящиків своєї продукції. Припустимо, що ці ящики можна послати по декількох різних каналах, показаних на рис. 1, де – завод, – ринок., а числа означають максимальне число ящиків, що може бути надіслано по цій сітці, не перевищуючи допустиму пропускну здатність кожного каналу.
Рис. 1
Рисунок 1 може описувати і другі ситуації. Наприклад, якщо кожна дуга цього орграфа являє собою вулицю з одностороннім рухом, а відповідні числа означають максимально можливий потік транспорту (число машин в годину) по цій вулиці, то хотілось би знайти найбільше можливе число машин, які можуть проїхати із за одну годину.
Цей рисунок можна розглядати і як схему електричної сітки, і тоді задача полягає в знаходженні максимального струму, який можна пропустити по цій сітці при умові, що задані допустимі струми окремих приводів.
ОСНОВНА ЗАДАЧА ТЕОРІЇ ТРАНСПОРТНИХ СІТОК
Введемо основні поняття теорії.
Означення 1.1. транспортна сітка є сукупність двох об’єктів:
Зв’язного графа з властивостями:
В графі відсутні петлі.
В графі існує одна і лише одна вершина така, що множина .
В графі існує одна і лише одна вершина , така, що множина .
Цілочисельною невід’ємною функцією , заданою на множині Г дуг графа . Вершина називається входом сітки, вершина – виходом.
Значення функції на дузі називається пропускною здатністю дуги.
Означення 1.2. Нехай – множина дуг, що заходять в вершину , а множина дуг, що виходять в вершини . Цілочисельна невід’ємна функція , задана на множині Г дуг графа , називається потоком, якщо вона задовольняє такі умови:
Означення 1.3. Величина – називається величиною потоку і позначається через.
Задача. На даній транспортній сітці побудувати потік найбільшої величини. Перш ніж викласти алгоритм розв’язку задачі, введемо ще два терміни. Дуга називається насиченою, якщо , потік називається повним, якщо кожен шлях від до містить хоча б одну насичену дугу.
АЛГОРИТМ ФОРДА-ФАЛКЕРСОНА ДЛЯ ЗНАХОДЖЕННЯ ПОТОКУНАЙБІЛЬШОЇ ВЕЛЕЧИНИ
Розглянемо алгоритм Форда на прикладі графа зображеного на мал.1 .
Припустимо, у нас витік буде в 1 вузлі, а стік в 4 вузлі. Алгоритм можна розбити на три кроки:
1.Пошук довільного шляху з витоку до стоку. Якщо такого немає, то видаємо значення максимальної пропускної спроможності і алгоритм завершується.
2.Знаходження в обраному шляху ребра з мінімальною пропускною здатністю. Додаємо значення цього ребра до пропускної спроможності, яка на початку виконання алгоритму дорівнює 0.
3.Віднімання з усіх значень ребер шляху, значення мінімального ребра цього шляху. При цьому саме ребро звернутися в 0 і його вже не можна враховувати в подальшому. Далі продовжуємо з кроку 1.
На початку у нас пропускна здатність дорівнює 0 (P = 0). Припустимо, ми знайшли шлях з витоку 1 в стік 4 через вершини 2 і 3, тобто весь шлях можна записати як (1-2-3-4). У цьому шляху мінімальне ребро з'єднує вершини 2 і 3, його значення 5, збільшуємо пропускну спроможність на 5 (Р = 5). Віднімаємо 5 з ребер з'єднують вершини 1 і 2, 2 і 3, 3 і 4. З вихідного графа у нас випало ребро з'єднує вершини 2 і 3. Вийшов граф зображений на мал.2.
У цьому графі знову шукаємо довільний шлях з 1 в 4. Знайшли (1-2-5-4), де мінімальне ребро з'єднує 2 і 5, його значення 6. Збільшуємо пропускну здатність на 6 (P = 5 +6 = 11). Віднімаємо 6 з усіх ребер шляху, випадає ребро 2-5 (мал.3).
На наступному кроці знаходимо шлях (1-6-5-4), мінімальне ребро 1-6 дорівнює 7, тоді P = 11 +7 = 18. Віднімаємо з ребер шляху 6, при цьому випадає ребро 1-6 і граф розпадається на дві компоненти мал.4.Ми не знаходимо шляху з витоку в стіл і алгоритм завершено. Отримуємо максимальну пропуснну здатність 18 .
Повний потік . Застосовуючи правила 4, 5 алгоритму Форда-Фалкерсона, отримаємо .
Варіанти домашніх завдань
– відповідає порядковому номеру студента в журналі групи.
– пропускна здатність дуги в напрямку від вершини до вершини .
Кількість вершин рівна . – нульова вершина, – вершина .
Скласти програму знаходження згідно з алгоритмом Форда-Фалкерсона і знайти
Код програми мовою Delphi:
unit Pasik;
interface
uses
Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,
Dialogs, StdCtrls, Buttons, Grids;
type
TForm1 = class(TForm)
StringGrid1: TStringGrid;
Label1: TLabel;
BitBtn2: TBitBtn;
Label2: TLabel;
procedure FormCreate(Sender: TObject);
procedure FormPaint(Sender: TObject);
procedure DrawLine(a1,a2,c: integer);
procedure StringGrid1SetEditText(Sender: TObject; ACol, ARow: Integer;
const Value: String);
procedure BitBtn2Click(Sender: TObject);
procedure DrawGraph;
private
{ Private declarations }
public
{ Public declarations }
end;
TMyPoint=record
x:integer;
y:integer;
name:string
end;
var
Form1: TForm1;
MyPoint:array[1..5] of TMyPoint;
koef:integer;
implementation
{$R *.dfm}
procedure TForm1.DrawGraph;
var
x,kx,ky,a,b:integer;
begin
Form1.Refresh;
for x:=1 to 5 do
begin
kx:=MyPoint[x].x+koef;
ky:=MyPoint[x].y+koef;
Form1.Canvas.Ellipse(kx,ky,kx+10,ky+10);
Form1.Canvas.TextOut(kx,ky-15,MyPoint[x].name);
end;
for a:=2 to 5 do
for b:=1 to a-1 do
if ((StringGrid1.Cells[b,a]<>'') and (StrtoInt(StringGrid1.Cells[b,a])>0)) then DrawLine (a,b,1);
end;
procedure TForm1.DrawLine(a1,a2,c: integer);
var
x1,y1,x2,y2:integer;
begin
if c=1 then Form1.Canvas.Pen.Color:=clBlack;
if c=2 then Form1.Canvas.Pen.Color:=clRed;
x1:=MyPoint[a1].x+koef+5;
y1:=MyPoint[a1].y+koef+5;
Form1.Canvas.MoveTo(x1,y1);
x2:=MyPoint[a2].x+koef+5;
y2:=MyPoint[a2].y+koef+5;
Form1.Canvas.LineTo(x2,y2);
Form1.Canvas.Pen.Color:=clBlack;
end;
procedure TForm1.FormCreate(Sender: TObject);
var
x:integer;
begin
StringGrid1.Cells[1,0]:='A';
StringGrid1.Cells[2,0]:='B';
StringGrid1.Cells[3,0]:='C';
StringGrid1.Cells[4,0]:='D';
StringGrid1.Cells[5,0]:='E';
StringGrid1.Cells[0,1]:='A';
StringGrid1.Cells[0,2]:='B';
StringGrid1.Cells[0,3]:='C';
StringGrid1.Cells[0,4]:='D';
StringGrid1.Cells[0,5]:='E';
for x:=1 to 5 do StringGrid1.Cells[x,x]:='X';
MyPoint[1].x:=10;
MyPoint[1].y:=70;
MyPoint[1].name:='A';
MyPoint[2].x:=20;
MyPoint[2].y:=30;
MyPoint[2].name:='B';
MyPoint[3].x:=70;
MyPoint[3].y:=80;
MyPoint[3].name:='C';
MyPoint[4].x:=90;
MyPoint[4].y:=20;
MyPoint[4].name:='D';
MyPoint[5].x:=120;
MyPoint[5].y:=50;
MyPoint[5].name:='E';
DrawGraph;
koef:=50;
end;
procedure TForm1.FormPaint(Sender: TObject);
var
x,kx,ky:integer;
begin
for x:=1 to 5 do
begin
kx:=MyPoint[x].x+koef;
ky:=MyPoint[x].y+koef;
Form1.Canvas.Ellipse(kx,ky,kx+10,ky+10);
Form1.Canvas.TextOut(kx,ky-15,MyPoint[x].name);
end;
end;
procedure TForm1.StringGrid1SetEditText(Sender: TObject; ACol,
ARow: Integer; const Value: String);
begin
if ACol=ARow then
begin
StringGrid1.Cells[ACol,ARow]:='X';
Exit;
end;
if StringGrid1.Cells[ACol,ARow]=Value then
begin
StringGrid1.Cells[ARow,ACol]:= Value ;
DrawGraph;
end;
end;
procedure TForm1.BitBtn2Click(Sender: TObject); //main
var
a:array[1..5,1..5] of integer;
t,min,x,y,u,i,j,k,n:longint;
b,c:array[1..5] of integer;
begin
for i:=2 to 5 do
for j:=1 to i-1 do
if ((StringGrid1.Cells[j,i]<>'') and (StrtoInt(StringGrid1.Cells[j,i])>0)) then n:=i;
for i:=1 to 5 do
for j:=1 to 5 do
if (StringGrid1.Cells[i,j]='') or (StringGrid1.Cells[i,j]='X') then a[i,j]:=32000
else a[i,j]:=StrToInt(StringGrid1.Cells[i,j]);
for i:=1 to 5 do
begin
c[i]:=0;
b[i]:=0;
end;
k:=0;
u:=1;
c[1]:=1;
b[u]:=1;
while u<n do
begin
min:=32000;
for i:=1 to u do
if b[i]>0 then
begin
t:=b[i];
for j:=1 to n do
if (a[t,j]<min) and (c[j]=0) then
begin
min:=a[t,j];
y:=t;
x:=j;
end;
end;
inc(u);
b[u]:=x;
c[x]:=1;
k:=k+a[y,x];
DrawLine (x,y,2);
a[y,x]:=32000;
a[x,y]:=32000;
end;
Label2.Caption:='Ðåçóëüòàò: '+IntToStr(k);
end;
end.
Висновок : на основі проведеної лабораторної робити я ознайомився з алгоритмом Пріма для знаходження мінімальнї або максимальнї ваги графа. Та навчився розв'язувати задачі за допомогою цього алгоритма.
06.04.2015 11:04-
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора