Программа "1-орграф"
Оглавление
1. Постановка задачи
2. Построение исходного графа
3. Алгоритм проверки связности
4. Результаты
5. О программе
Приложение 1
Edit
Приложение 2
Матрица p
Приложение 3
Матрица s
Приложение 4 f
Приложение 5
Распечатка программы «1-орграф»
1. Постановка задачи
Определения.
Орграф – граф, вершины которого связаны ориентированными дугами.
Полносвязный орграф – орграф, в котором существуют пути между каждой пар вершин по дугам, ориентированным в одном направлении.
Частично связанный орграф – существует путь от исходной вершины ко всем остальным вершинам орграфа.
Дуги на этом пути назовём активированными.
Если между двумя вершинами несколько дуг, активируется одна дуга.
Ограничение: в каждую вершину, кроме исходной входит не более одной активированной дуги.
Определив возможности связи каждой вершины со всеми другими, можно сделать заключение о полносвязности графа.
Возможно, есть критерии, которые позволят определить полносвязность орграфа на анализе ограниченного числа частично связанных орграфов.
Разработана программа «1- орграф» для построения пути из исходной вершины орграфа во все доступные вершины.
То есть строится дерево с ориентированными путями из исходной вершины к другим вершинам. На пути от исходной вершины в остальные вершины дуги ориентированы в одном направлении.
2. Построение исходного графа
n – число вершин исходного орграфа
Построение исходного графа тоже, что в программе «АКСОН».
const m и b задают отсутствие связей между вершинами исходного орграфа
3. Алгоритм проверки связности
Const b – исходная вершина орграфа
Алгоритм сводится к const x итерациям.
На первой итерации помечаются рангом 1 все вершины, соединенные с исходной вершиной дугой исходящей из исходной вершины.
На каждой последующей итерации последовательно перебираются помеченные вершины с самым высоким рангом, например z, и при наличии дуги из помеченной вершины в множество непомеченных непомеченной вершине условно присваивается ранг на единицу выше – z+1.
Соответствующая дуга активируется.
Ранг z+1.
После перебора всех помеченных вершин всем условно помеченным вершинам присваивается ранг помеченных.
4. Результаты
В результате расчётов находятся
u – число помеченных дуг.
В случае частично связанного орграфа u = n-1
p[1..n,1..n] – матрица: вершины - активированные дуги.
Указан ранг дуг.
f[1..n] – перечень рангов вершин
f[2..n] – перечень: числа помеченных дуг входящих в помеченные вершины
f[3..n] – перечень: числа помеченных дуг исходящих из помеченных вершин
f[4..n] – перечень: помеченные вершины – сумма исходящих помеченных дуг
Результаты счета в Приложениях 1 - 4
5. О программе
Программа «1-орграф» на Дельфи -7.
Распечатка программы «1-орграф» - Приложение 5
Скачать программу
https://yadi.sk/d/YqgjgUvQblTJ6g
Приложение 1
Edit
Приложение 2
Матрица p
Приложение 3
Матрица s
Приложение 4 f
Приложение 5
Распечатка программы «1-орграф»
Программа
Приложение 1
const
n =150;// ÷ число вершин исходного графа
a1 = 70;//для вычисления числа дуг
b=1;// начальная вершина
m=50;// вычисление отсутствия связи между вершинами графа
x= 13 ;// ÷вычисление отсутствия связи между вершинами графа
unit Unit1;
interface
uses
Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,
Dialogs, Grids, StdCtrls;
type
TForm1 = class(TForm)
StringGrid1: TStringGrid;
Button1: TButton;
Button2: TButton;
Button3: TButton;
Button5: TButton;
Label1: TLabel;
StringGrid2: TStringGrid;
StringGrid3: TStringGrid;
StringGrid4: TStringGrid;
Button4: TButton;
Edit1: TEdit;
Edit2: TEdit;
Label4: TLabel;
Label5: TLabel;
Edit3: TEdit;
Label2: TLabel;
Label3: TLabel;
Label7: TLabel;
Label6: TLabel;
procedure Button1Click(Sender: TObject);
procedure Button5Click(Sender: TObject);
procedure Button2Click(Sender: TObject);
procedure Button4Click(Sender: TObject);
private
{ Private declarations }
public
{ Public declarations }
end;
var
Form1: TForm1;
implementation
{$R *.dfm}
n =25;// ÷ число вершин исходного графа
a1 = 70;//для вычисления числа дуг
b=1;// начальная вершина
m=50;// вычисление отсутствия связи между вершинами графа
x= 13 ;// ÷вычисление отсутствия связи между вершинами графа
var
Tick: Cardinal;
s:array [1..n, 1 ..n] of integer;// ñâÿçè àêñîí - äåíäðèòû
p : array [1..n,1..n] of integer;// ñîñòîÿíèå íåéðîíîâ
f : array [1..5,1..n] of integer;// ñîñòîÿíèå âõîäíîãî ñèãíàëà
k, a, u, t, b1, d1, d, g, q,i,j,h,i1,i2 : integer; //
j1,j2,j3,j4,j5,j6,j7,j8, i3,i4,i5,i6,i7,i8,i0: integer; //
w, z1,z2, z3: integer;//
m1 ,m2,m3,m4,m5, m6,m7 ,m8: integer;//
t3: integer;
ia, ib,ic, id ,it, ja, jb, jc, jd ,jt: integer;//
zz ,ss, vv, sss, uu ,kk :integer;//
e, r, r1, r2, r3, r4, r5, r6, r7, r8, r9 : integer;//
ff ,tt ,c1, g1,cc,ccc,ww: integer;//
l1, l2 ,l3,l4: variant;//
procedure TForm1.Button1Click(Sender: TObject);
// îêàíòîâêà
begin
for q:=1 to n //íóìåðàöèÿ ïî ãîðèçîíòàëè â òàáë ¹1 ,
do StringGrid1.Cells[q,0]:=IntToStr(q);
for q:=1 to n // íóìåðàöèÿ ïî âåðòèêàëè â òàáë ¹1 ,
do StringGrid1.Cells[0,q]:=IntToStr(q);
for q:=1 to n //íóìåðàöèÿ ïî ãîðèçîíòàëè â òàáë ¹2,
do StringGrid2.Cells[q,0]:=IntToStr(q);
for q:=1 to n // íóìåðàöèÿ ïî âåðòèêàëè â òàáë ¹2 ,
do StringGrid2.Cells[0,q]:=IntToStr(q);
for q:=1 to n //íóìåðàöèÿ ïî ãîðèçîíòàëè â òàáë ¹4,
do StringGrid4.Cells[q,0]:=IntToStr(q);
for q:=1 to n // íóìåðàöèÿ ïî âåðòèêàëè â òàáë ¹4 ,
do StringGrid4.Cells[0,q]:=IntToStr(q);
end;
procedure TForm1.Button2Click(Sender: TObject);
begin
for i:=1 to n do
for j:= 1 to n do
if i<>j then
begin s[i,j] := random ( a1);
h:= random (m);
if h>3 then s[i,j] := 0;
end;
for k:= 1 to x do begin
Form1.Caption:=IntToStr(GetTickCount-Tick);
if k=1 then
for j := 1 to n do
if (S[b,j] > 0) then begin
p[1,j] :=1; f[1,j] :=1
end;
if k>1 then
for i:=1 to n do
for j:= 1 to n-1 do
if p[i,j]=k-1 then
begin
for a:=1 to n-1 do
if ( (s[j,a+1]>0 )and (p[j,a+1] =0)) then
if f[1,a+1]= 0 then begin
p[j,a+1] := k; f[1,a+1]:=k end;
end;
end;
for i:=1 to n do
for j:=1 to n do
if p[i,j]> r then
begin r:= p[i,j]; e:=i; g:=j end;
for i:=1 to n do
for j:=1 to n do
if p[i,j]> 0 then
u:= u+1;
for i:=1 to n do
for j:=1 to n do
if p[i,j]> 0 then
f[2,j]:= f[2,j]+1;
for j:=1 to n do
for i:=1 to n do
if p[j,i]> 0 then
f[3,j]:= f[3,j]+1;
l1 := u/(n-1);
for i:=1 to n do
for j:=1 to n do
for w:=1 to n do
if p[i,j]=w then
f[4,w] := f[4,w] +1;
for i:=1 to n do
for j:=1 to n do
if p[i,j]>0 then r1:= r1+1;
for i:=1 to n do
for j:=1 to n do
if s[i,j]>0 then r2:= r2+1;
for i:=1 to n do begin
r3 := r3 +f[1,i];
r4 := r4 + f[2,i];
r5 := r5 + f[3,i];
end;
l2:= r3/(n-1);
for i:=1 to n do
for j:=1 to n do
StringGrid4.Cells[j,i]:=
IntToStr( s[i,j]);
for i:=1 to 4 do
for j:= 1 to n do
StringGrid1.Cells[j,i]:=
IntToStr( f[i,j]);
for i:=1 to n do
for j:= 1 to n do
StringGrid2.Cells[j,i]:=
IntToStr( p[i,j]);
Edit1.Text := 'm='+'---'+IntToStr(m)+' ' +
'n='+'---'+IntToStr(n)+' ' +
'x='+'---'+IntToStr(x) +' ' +
'a1='+'---'+IntToStr(a1) +' ' +
'k='+'---' +IntToStr(k) +' ' +
'l1='+'---'+ FormatFloat('0.000',l1) +' ' +
'l2='+'---'+ FormatFloat('0.000',l2);
Edit2.Text := 'r='+'---'+IntToStr(r)+' ' +
'e='+'---'+IntToStr(e)+' ' +
'g='+'---'+IntToStr(g)+' ' +
'u='+'---'+IntToStr(u) +' ' +
'x='+'---'+IntToStr(x) ;
Edit3.Text :=
'r1='+'---'+IntToStr(r1)+' ' +
'r2='+'---'+IntToStr(r2)+' ' +
'r3='+'---'+IntToStr(r3)+' ' +
'r4='+'---'+IntToStr(r4) +' ' +
'r5='+'---'+IntToStr(r5)
end;
procedure TForm1.Button4Click(Sender: TObject);
begin
end;
///////// ///////////////////////////////////////////////////////
procedure TForm1.Button5Click(Sender: TObject);
begin
close
end;
//initialization
// randomize;
end.