1.5 Гибель линейной сети. Атака на узлы

При атаке на узлы линейной сети средняя доля выживших узлов находится из соотношения d(Ump) - (n - m)/n; d(Smy) = 1 - d(Umy). После подстановки значений

d(Umy)= d(Ump) - (n-m)/n; d(Umy)=l-d(Umy)

После подстановки значений d(Umy) и упрощения получаем

Графические зависимости d(Sy) от n и dny показаны на (Рисунок 5). Они имеют выпуклый вид, то есть потери при гибели узлов существенно возрастают.

Исследование связности кольца (rизб=const)

Теоретические зависимости:

Исследование связности “мостика” (rизб=2, n=var)

Теоретические зависимости:

Исследование связности “песочных часов” (rизб=2, n=var)

Теоретические зависимости:

Исследование связности сетей (rизб=3, n=var)

Теоретические зависимости:

2.2 Оценка влияния числа избыточных дуг на вероятность связности

Ввод сети Рисунок 9

Формирование неприведённого уравнения связности Рисунок 10

Блок-схема алгоритма приведения коэффициентов Рисунок 11

Блок-схема алгоритма анализа гибели сети (разрыв дуг) Рисунок 12

Блок-схема алгоритма анализа гибели сети (атака на узлы) Рисунок 13

Процедура нахождения и сбора фрагментов сети Рисунок 14

Процедура получения списка доступных вершин Рисунок 15

Блок-схема функции реализующей алгоритм поисками минимального пути Дейкстеры Рисунок 16

Интерфейс программы

Для исследования связности сетей написана программа, позволяющая графическим методом задавать параметры сетей и получать наглядные числовые и графические зависимости.

Рисунок 17 Главное окно программы

Язык программирования: Object Pascal

· kord одномерный массив типа point размерностью 255 точек содержащий координаты точек возможного расположения вершин

· smez двухмерный динамический массив типа integer содержащий эталонную матрицу смежности исследуемой сети

· smez3 двухмерный динамический массив дублирующий эталонный smez, служит для исследования связности сети при разрыве 1,2..n дуг

· versh одномерный массив типа point размерностью 40 точек содержащий координаты вершин относительно границ поля отведенного для рисования

· form - одномерный массив строкового типа содержащий теоритические зависимости сети

· dug одномерный динамический массив содержащий все существующие в сети дуги. В формате “0102”, где первые два числа первая вершина а последние два - вторая вершина.

· nversh переменная численного типа содержащая сведения о количестве вершин сети.

· ndug переменная численного типа содержащая сведения о количестве дуг сети.

3.3 Результаты исследований гибели сетей при атаке на узлы

procedure TForm1.Image1MouseDown(Sender: TObject; Button: TMouseButton;

Shift: TShiftState; X, Y: Integer);

var i,j,p,tek:integer;

begin

Image1.Canvas.Brush.Color:=clBlack;

Image1.Canvas.Pen.Color:=clBlack;

Image1.Canvas.Pen.Mode := pmMask;

//ShowMessage(inttostr(x)+' '+inttostr(y));

p:=0;

tek:=1;

for i:=0 to 225 do begin

if (x>kord[i].x-10) and (x<kord[i].x+10) and (y>kord[i].y-10) and (y<kord[i].y+10) then begin

Image1.Canvas.EllipseC(kord[i].x,kord[i].y,3,3);

Image1.Canvas.Pen.Width:=4; //возвращаем все как было

for j:=0 to 40 do begin // проверка новая вершина или нет

if (versh[j].x=kord[i].x) and (versh[j].y=kord[i].y) then begin

p:=1;

tek:=j;

Break;

end;

end;

if p=0 then begin // добавление новой вершины

versh[nversh]:=kord[i];

tek:=nversh;

//Image1.Canvas.TextOut(kord[i].x,kord[i].y,InttoStr(nversh));

nversh:=nversh+1;

end;

smez[pred,tek]:=1;

smez[tek,pred]:=1;

smez[tek,tek]:=0;

pred:=tek;

if prev.x<>0 then begin

p:=0;

Image1.Canvas.MoveTo(prev.x,prev.y);

Image1.Canvas.LineTo(kord[i].x,kord[i].y);

end;

prev:=kord[i];

end;

end;

//перерисовка всех точек

for i:=0 to nversh-1 do begin

Image1.Canvas.Pen.Width:=14;

Image1.Canvas.EllipseC(versh[i].x,versh[i].y,3,3);

Image1.Canvas.Font.Color:=clWhite;

Image1.Canvas.Pen.Mode := pmMask;

Image1.Canvas.Brush.Color:=clBlack;

Image1.Canvas.TextOut(versh[i].x-3,versh[i].y-6,InttoStr(i));

end;

end;

procedure TForm1.Button3Click(Sender: TObject); //очистка

var i,j:integer;

begin

jpg.Canvas.Clear;

prev.x:=0;

Form1.FormShow(Sender);

for i:=0 to 200 do begin // перебор

for j:=0 to 200 do begin

smez[i,j]:=-1;

end;

end;

for i:=0 to 40 do begin

versh[i].x:=0 ;

versh[i].y:=0 ;

dug[i]:='';

end;

nversh:=0;

pred:=0;

ndug:=0;

nz:=0;

nraz:=0;

end;

Программный код формирования уравнения связности и нахождение численных значений

procedure TForm1.Button6Click(Sender: TObject);

var i,ig,j,n,g,g2,h,tek,pred,kk,p:integer;

html: TIpHtml;

ms:TMemoryStream;

MyString:AnsiString;

pr:real;

koef: array[0..40] of integer;

koef2: array[0..40] of integer;

s,str,ps,vr:string;

new:boolean;

res: Word;

begin

nraz:=2;

prev.x:=0;

n:=0;

h:=1;

kk:=0;

for i:=0 to 40 do begin

koef[i]:=0;

koef2[i]:=0;

end;

for i:=0 to nversh-1 do begin // заполнение массива дуг

for j:=i+1 to nversh-1 do begin

if smez[i,j]=1 then begin

dug[h]:=formatm(i)+formatm(j);

h:=h+1;

end;

end;

end;

n:=h-1;

Label2.Caption:='r='+inttoStr(n);

Label3.Caption:='n='+inttoStr(nversh);

str:='';

kk:=0;

res:=1;

if n>17 then begin // ограничение

res := MessageDlg('Данная процедура может занять более '+FloattoStr(power(2,(n-17)))+' минут. Продолжить?', mtInformation, [mbOk, mbCancel], 0);

end;

if res<>2 then begin

for i:=1 to (1 shl n)-1 do begin

for j:=1 to n do if(i and(1 shl(j-1)))>0 then

begin

str:=str+dug[j];

end;

if true then begin //length(str)

g2:=1;

smez3:=smez; // дублируем исходную матрицу

for g:=0 to round(length(str)/4)-1 do begin // удаление дуг

smez3[strtoint(copy(str,g2,2)),strtoint(copy(str,g2+2,2))]:=-1;

smez3[strtoint(copy(str,g2+2,2)),strtoint(copy(str,g2,2))]:=-1;

g2:=g2+4;

//ShowMessage(str+' '+inttostr(connect));

end;

//if (length(str)/4)=2 then Memo1.Append(str+' '+inttostr(connect));

if connect=0 then begin

koef[round(length(str)/4)]:=koef[round(length(str)/4)]+1;

if round(length(str)/4)>kk then kk:=round(length(str)/4);

end;

str:='';

end;

end;

//обработка строки

koef[0]:=1;

h:=h-1;

vr:=vr+'+1*p^'+inttostr(h)+'+';

for i:=1 to kk do Memo1.Append(inttostr(koef[i])+'+p^');

for i:=1 to kk do vr:=vr+naq(koef[i],h-i,i)+'+';

for ig:=0 to h+1 do begin

p:=pos('p^'+inttostr(h-ig),vr);

if p<>0 then begin

while pos('p^'+inttostr(h-ig),vr)<>0 do begin

p:=pos('p^'+inttostr(h-ig),vr);

j:=p;

str:='';

repeat

j:=j-1;

until (vr[j]='+') or (vr[j]='-') or (j=0);

for g:=j to p-2 do str:=str+vr[g];

koef2[h-ig]:=koef2[h-ig]+strtoint(str);

vr[p]:='t';

end;

end;

end;

if not Otch.Checked then StringGrid1.ColCount:=2;

if Otch.Checked then StringGrid1.ColCount:=notch+2;

StringGrid1.Cells[0,0]:='p';

StringGrid1.Cells[0,1]:='0';

StringGrid1.Cells[1+notch,1]:='0';

StringGrid1.Cells[1+notch,0]:=bukv[notch]+')';

for i:=1 to 10 do begin

pr:=0;

for ig:=1 to h+1 do

if koef2[ig]<>0 then begin

pr:=pr+koef2[ig]*power((i/10),ig);

end;

StringGrid1.Cells[0,i+1]:=floattostr(i/10);

StringGrid1.Cells[1+notch,i+1]:=Format('%.5n',[pr]); //вывод в таблицу

end;

MyString:='<html>P<SUB>C</SUB>='; // нормальное отображение

for ig:=1 to h+1 do

if koef2[ig]<>0 then begin

if koef2[ig]>0 then MyString:=MyString+'+'+inttostr(koef2[ig])+'p<SUP>'+inttostr(ig)+'</SUP>'

else MyString:=MyString+inttostr(koef2[ig])+'p<SUP>'+inttostr(ig)+'</SUP>';

end;

MyString:=MyString+'</html>';

html:=TIpHtml.Create;

ms:=TMemoryStream.Create;

ms.Write(MyString[1],Length(MyString));

if otch.Checked then begin /// отчет!!

form[notch]:=MyString;

notch:=notch+1;

//Image1.Picture.SaveToFile(IntToStr(notch)+'.bmp');

jpg.Assign(Image1.Picture.Bitmap);

jpg.CompressionQuality:= 100;

jpg.SaveToFile(IntToStr(notch)+'.jpg');

if notch=6 then Button6.Enabled:=false;

end;

ms.Position:=0;

html.LoadFromStream(ms);

IpHtmlPanel1.SetHtml(html);

ms.free;

end;

end;

Программный код построения графиков вероятности связности

procedure TForm1.Button11Click(Sender: TObject);

var i,j,nox,noy,XI,Yi:integer;

Rect: TRect;

Points: Array[0..3] of TPoint;

begin

Image2.Canvas.Brush.Color:=clWhite; //присваиваем кисти цвет формы.

Image2.Canvas.FillRect(0,0,Width,Height); //заливаем Image выбранным цветом кисти.

Image2.Canvas.Pen.Width:=1;

Image2.Canvas.Pen.Color:=clBlack;

Image2.Canvas.Line(25,Image2.Height-15,Image2.Height-5,Image2.Height-15); // горизонтальная палка ох

Image2.Canvas.Line(Image2.Height-5,Image2.Height-15,Image2.Height-15,Image2.Height-11); // стрелочка

Image2.Canvas.Line(Image2.Height-5,Image2.Height-15,Image2.Height-15,Image2.Height-19); // ->

Image2.Canvas.Line(25,Image2.Height-15,25,10); // вертикальная палка оу

Image2.Canvas.Line(25,10,29,20); // cтрелка

Image2.Canvas.Line(25,10,21,20); // ^

Image2.Canvas.Font.Size:=7;

nox:=10;

noy:=10; // кол-во меток по Оу

noy:=maxoy;

nox:=maxoy;

for i:=0 to noy do begin { длина оси отступ } // черточки и цифры по осям

Image2.Canvas.TextOut(trunc((Image2.Height-45)/nox)*i+25,Image2.Height-10,Form1.StringGrid1.Cells[0,i+1]);

Image2.Canvas.Line(trunc((Image2.Height-45)/nox)*i+25,Image2.Height-10,trunc((Image2.Height-45)/nox)*i+25,Image2.Height-20); // черточки |

Image2.Canvas.TextOut(5,Image2.Height-10-trunc((Image2.Height-45)/noy)*i,Form1.StringGrid1.Cells[0,i+1]);

Image2.Canvas.Line(20,Image2.Height-15-trunc((Image2.Height-45)/noy)*i,30,Image2.Height-15-trunc((Image2.Height-45)/noy)*i);

end;

Image2.Canvas.Pen.Color:=clGray;

for i:=1 to noy do begin // серые полоски

Image2.Canvas.Line(trunc((Image2.Height-45)/nox)*i+25,Image2.Height-15,trunc((Image2.Height-45)/nox)*i+25,10); // полосочки |

Image2.Canvas.Line(25,Image2.Height-15-trunc((Image2.Height-45)/noy)*i,Image2.Height-15,Image2.Height-15-trunc((Image2.Height-45)/noy)*i);

end;

Image2.Canvas.Pen.Width:=2;

Image2.Canvas.Pen.Mode := pmMask;

for j:=1 to StringGrid1.ColCount-1 do begin // по столбцам

Image2.Canvas.Pen.Color:=Colores[j mod 7];

Image2.Canvas.Brush.Color:=Colores[j mod 7];

for i:=2 to StringGrid1.RowCount-1 do begin // по строчкам

if StringGrid1.Cells[0,i]<>'' then begin { FloatToStr(10*(i-1)/skokan(j)) Grx(StringGrid1.Cells[0,i-1])}

Memo1.Append(StringGrid1.Cells[0,i]+' / '+InttoStr(skokan(j)));

Figur(Grx(StringGrid1.Cells[0,i]),Gry(StringGrid1.Cells[j,i]),j);

Image2.Canvas.Line(Grx(StringGrid1.Cells[0,i-1]),Gry(StringGrid1.Cells[j,i-1]),Grx(StringGrid1.Cells[0,i]),Gry(StringGrid1.Cells[j,i]));

end; // это нормальный график

end;

Image2.Canvas.Line(Image2.Height+20,25*j,Image2.Height+30,25*j);

Figur(Image2.Height+25,25*j,j);

Image2.Canvas.Pen.Mode := pmCopy;

Image2.Canvas.Brush.Color:=clWhite;

Image2.Canvas.TextOut(Image2.Height+35,25*j-7,bukv[j-1]);

end;

end;

Программный код расчета гибели сети детерминированным способом при разрыве дуг

procedure TForm1.Button10Click(Sender: TObject);

var i,ig,j,n,g,g2,h,tek,pred,kk,p:integer;

html: TIpHtml;

ms:TMemoryStream;

MyString:AnsiString;

pr:real;

koef: array[0..40] of integer;

koef2: array[0..40] of integer;

s,str,ps,vr:string;

new:boolean;

res: Word;

// для графика,которого нет

kff:real;

maxk:integer;

begin

kostgraph:=0;

nraz:=2;

prev.x:=0;

n:=0;

h:=1;

kk:=0;

for i:=0 to 40 do begin

koef[i]:=0;

koef2[i]:=0;

end;

for i:=0 to nversh-1 do begin // заполнение массива дуг

for j:=i+1 to nversh-1 do begin

if smez[i,j]=1 then begin

dug[h]:=formatm(i)+formatm(j);

h:=h+1;

end;

end;

end;

n:=h-1;

Label2.Caption:='r='+inttoStr(n);

Label3.Caption:='n='+inttoStr(nversh);

mnbu[notch]:='(n='+inttoStr(nversh)+')';

str:='';

kk:=0;

res:=1;

if n>17 then begin // ограничение

res := MessageDlg('Данная процедура может занять более '+FloattoStr(power(2,(n-17)))+' минут. Продолжить?', mtInformation, [mbOk, mbCancel], 0);

end;

if res<>2 then begin

for i:=1 to (1 shl n)-1 do begin

for j:=1 to n do if(i and(1 shl(j-1)))>0 then

begin

str:=str+dug[j];

end;

if true then begin //length(str)

g2:=1;

smez3:=smez; // дублируем исходную матрицу

for g:=0 to round(length(str)/4)-1 do begin // удаление дуг

smez3[strtoint(copy(str,g2,2)),strtoint(copy(str,g2+2,2))]:=-1;

smez3[strtoint(copy(str,g2+2,2)),strtoint(copy(str,g2,2))]:=-1;

g2:=g2+4;

end;

//ShowMessage(str+' '+inttostr(connect));

//if (length(str)/4)=2 then Memo1.Append(str+' '+inttostr(connect));

koef[round(length(str)/4)]:=koef[round(length(str)/4)]+Length(jivnew);

koef2[round(length(str)/4)]:=koef2[round(length(str)/4)]+1;

//Memo1.Append('anton:'+IntToStr(anton2));

if round(length(str)/4)>kk then kk:=round(length(str)/4);

end;

str:='';

end;

end;

for i:=1 to kk do vr:=vr+InttoStr(koef[i])+' '+InttoStr(i)+'+';

Memo1.Append(vr);

if not Otch.Checked then StringGrid1.ColCount:=2;

if Otch.Checked then StringGrid1.ColCount:=notch+2;

StringGrid1.Cells[0,0]:='Количество изымаемых дуг';

StringGrid1.Cells[1+notch,0]:=bukv[notch]+')';

StringGrid1.Cells[0,1]:='0';

StringGrid1.Cells[1+notch,1]:=IntToStr(0);

//koef[kk]:=0;

maxk:=0; // для графика

for i:=0 to 10 do begin

if koef2[i]<>0 then begin

pr:=0;

pr:=koef[i]/koef2[i];

StringGrid1.Cells[0,i+1]:=floattostr(i);

StringGrid1.Cells[1+notch,i+1]:=Format('%.3n',[1-(pr/nversh)]); //вывод в таблицу (1-)

maxk:=maxk+1;

end

else StringGrid1.Cells[1+notch,i+1]:='0';

end;

if otch.Checked then begin /// отчет

form[notch]:=MyString;

notch:=notch+1;

//Image1.Picture.SaveToFile(IntToStr(notch)+'.bmp');

jpg.Assign(Image1.Picture.Bitmap);

jpg.CompressionQuality:= 100;

jpg.SaveToFile(IntToStr(notch)+'.jpg');

if notch=6 then Button6.Enabled:=false;

end;

end;

function jivnew:string;

var uze: array[0..13] of boolean;

str,sum:string;

i,j,k,kf:integer;

begin

for i:=0 to 13 do uze[i]:=false;

sum:='';

kf:=0;

for i:=0 to nversh-1 do begin

if not uze[i] then begin str:=anton1(i);

if str<>'' then for j:=1 to Length(str) do uze[StrToInt(str[j])]:=true;

//str:=anton1(i);

if Length(str)<>1 then sum:=sum+str;

end;

end;

//Form1.Memo1.Append(sum);

jivnew:=sum;

end;

function anton1(q:integer):string;

var

b:array[0..25]of boolean;//список просмотренных вершин

d:array[0..25] of longint;//кротчайшие расстояния

i, j, m, v,n: integer;

s:string;

begin

//Ввод данных

n:=nversh-1;

// q := 0; //начальная вершина

if (q < 1) or (q > n) then q := 1;

for i := 0 to n do

for j := 0 to n do

//Расчет

fillchar(b,sizeof(b),0);

fillchar(d,sizeof(d), 10000);

d[q] := 0;//расстояние до начальной вершины

for i:=0 to n do

begin

m := 1000;

for j := 0 to n do

if ( (d[j] <= m) and (not b[j]) ) then

begin

m:=d[j];

v:=j;

end;

b[v] := true;

for j := 0 to n do

if ((smez3[v,j]<>-1)and (not b[j]) and (d[v]+smez3[v,j]<d[j])) then

d[j]:=d[v]+smez3[v,j];

end;

anton1:='';

for i := 0 to n do begin

if d[i]<nversh then begin

anton1:=anton1+inttostr(i);

end;