Файл: Алферова, З. В. Математическое обеспечение экономических расчетов с использованием теории графов.pdf

;нач

цел

Б1,

Б2,

CP;

цел

мае

А[20,

21], В[15, 1 6 ] ; С[30, 31], Л[10,21] ,

Л1[20,10],

Щ 1 0 , 1 6 ] ,

К1 [15,10];

цел

И, Ж , X, Р, Д, Е, П, 3,

Т, У, М, Н, К, СИ, Ш;

библ

('ВВОДЗ',

' I I ' ,

А,

В);

Н : = 2 0 ;

М: =

15;

Р : = 0 ;

Д : = 0 ; Е : = 0 ;

П : = 0 ; Т : = 0 ; Ш: = 1;

М20:

для

И : = 1:Н

цикл

нач

для

Х: = 1 : М

цикл

нач

если

А [И, 1] = В [ Х ,

1]

то

на

M l ;

кон;

Р : = Р + 1 ;

для

И : = 1 : Н

цикл

Л [Р, Ж ] : = А [ И , Ж ] ;

Ж : = И ;

для

И : = 1 : Н

цикл

Л1 [И, Р ] : =

А[И, Ж ] ;

кон;

П : = 3 ;

для

X: = 1 : М

цикл

нач

для

3 : = 1 : Р

цикл

нач

если

В[Х,

1 ] = С [ 3 , 1] то_на_М2;

кон;

Т : = Т + 1 ;

для

У: = 1 : 1 6

цикл

Ц[Т,У] : = В [ Х , У ] ;

У : = Х ;

для

Х: = 1 : М

цикл

Ц[Х, Т ] : = В [X, У];

Х : = У ;

М2:

кон;

нач

Е : = Р ;

для

Р : = 1 : Е

цикл

нач

С [ 3 , К ] : = Л [ Р ,

Ж ] ; К : = К + 1 ;

кон;

К : = Е ;

3: = 1;

для

И: = 1: Н

цикл

нач

С [ 3 , К ] : = Л [ И ,

Р];_на М40;

кон;

М40:

3 : = 3 + 1 ;

кон;

Е : = Т ;

для

Т: = 1: Е

цикл

нач

К: = 1;

для

У: == 1 : 16

цикл

_нач

С [ 3 , К ] : = Ц [ Т ,

У ] ;

если

К = Д

то на

МО;

К : = К + 1 ; н а М З ;

МО:

К : = К + Р ;

МЗ:

кон;

К : = 3 ;

3: = 1;

для

Х: = 1:М

цикл

иач

С [ 3 , К ] : = Ц [ Х , Т ] ;

ест

3 = Д _ т о на М4;

3 : = 3 + 1 ;

на

М5;

М4:

3 : = 3 + Р ;

М 5 :

кон;

3 : = 3 + 1 ;

кон;

К: = 1;

СИ: =

1;

Р : = 0 ;

М8:

для

3: = 1: Л

цикл

нач

если

С [ 3 , К] = С Р

то

на Мб; кон; на МЗО;

Мб:

К : = 3 ;

для_

3: = 1 : Л

цикл

СИ: = С И + С

[3, Д ] ;

если

С И > 2

_то

на

М7;

3 : = К ;

Ш : = 3 ;

на

М8;

М7:

П : = К ;

3 : = Д ;

3 : = 3 + 1 ;

С [ 3 , 1 ] : = Б 1 ;

С [ 3 , К ] : =

1; 3

: = 3 + 1 ;

С [ 3 , 1 ] : = Б 2 ;

С[3, . К] : = 1; _для

3 : = 1

: Д

цикл

нач

Д : = П ; если

С [ 3 , К] = 2

то

на

М9;

если С [ 3 , К] =

1

то

на М10;

на М П ;

М10: С [ 3 , К ] : = 0 ;

если

3 < ( Д — Т )

то_

ш_

М12;

К : = К + 2 ;

С [ 3 , К ] : = 1;

на М10;

М9:

С [ 3 , К ] : - 0 ;

К : = Д ;

К : = К + 1 ;

С [ 3 , К ] : =

1;

К : * = К + 1 ;

С [ 3 , К ] : = 1 ;

М П :

кон^

К : = П ;

3 : = К + 1 ; на

МЗО;

МЗО:

для

К: = 1 : ( Л + 1 )

цикл

нач

для

3: = 1 : Д цикл

нач

если

С [ 3 , К] = 2

то

на

М12;

М13*

кон;

М12:

С [ 3 , К ] : = 1;

на

MI2 ;

библ

(ВЫВОД!',

'Г, С);

M l :

K : = 3 ; C[3,1] : = А [ И , Ж ] ;

_для

К: = 1:(М+1 )

цикл

нач

С [ 3 , К ] : = А [ И , Ж ] + В [ Х , У ] ;

если Ж = ( Н + 1 ) _ г о на М21;

если

У = ( М + 1 )

_то

_на

М22; У : = У + 1 ;

Ж : = Ж + 1 ;

M23:j

кон;

М22:

У : = У + 1 ; В [ Х , У ] : = 0 ;

Ж : = Ж + 1 ; _ н а

М23;

М21:

е_сли

У = ( М + 1 )

то_

на

М24;

Ж : = Ж + 1 ;

А [ И , Ж ] : = 0 ; У : = У + 1 3

на

М23;

М24:

Д : = 3; 3: = 3 + 1 ;

на

М20;

кон;

графа

представлена

на

рис. 40.

Алгоритм перевода матрицы в

граф в языке АЛГЭК-С будет иметь следующий вид:

нач

цел

мае

В [ 1 : Р ] ,

А[1:П,

1:Т];

цел

X,

i ,

j , Т,

П,

Р;

библ

('ВВОДЗ',

'Г,

А);

М О :

j : = l ;

В [ Х ] : — a [ i , j ] ;

МЗ:

J : = j + 1 ;

если

j = T

то

на

M l ;

если

a[i,

j ] = l

то

на

М2;

на

МЗ;

М2:

Х : = Х + 1 ;

В [ Х ] : = а[1,]];_на

МЗ;

M l :

если

i = n

то

на

МЕТ;

i : = i + l ;

Х : = Х + 1 ;

на

МО;

МЕТ:

библ

('ВЫВОДГ,

'Г, В);

кон;

Глава VIII

П Е Р С П Е К Т И В Ы И С П О Л Ь З О В А Н И Я

Т Е О Р ИИ ГРАФОВ

13. Заказ 4230.

193

дугами.

Пусть Ау

и Аи — конечные алфавиты, соответствующие мно­

жеству

значений вершин и

меток

дуг графа. Тогда граф G над

Ау и Ам

будет определяться

как G (N, V, F ) , где N — конечное

множество

вершин;

V: N—*Ау—

функция,

задающая значение

каждой

вершине; F^NxAMXN—

множество

дуг и соответствую­

щих им меток.

Если

(п,

a, m)^F,

то это дуга с меткой а из вершины п в вер­

ветственно NG,

VG, F G .

Если Ay и Ам — алфавиты, то

G\(AV,

AM)

= {G\G — граф над Ау

и

Ам).

Если

Ау

и

Ам

известны,

будем

писать

просто

G1 вместо G1

{Ау, Ам).

Графовый язык над Ау и Ам

— это последовательность графов

вида G1 (Ау,

Ам).

Графы

G и Я,

являющиеся

элементами

G1, эквивалентны

(G==H)

с точностью до изоморфизма, если

существует такая фун­

кция ф, что

1) v „ e / V G ,

VG(n)

=

VH{4>(n)),

2) (п,

а,

т)

е= F G ,

когда

(ф(п),

а, ф(т))

^

F H

•

1)

N B { \ N K = 0 ,

NQ =

-NH\)NK;

2)

Vn^NH,

VH(n)

= VG(n)

и Y,n^NK,

VK(m) = VG(m);

3)

FH={(n,

a,

m)

<= FG\n,

m e= N H }

;

4)

FK={(n,

a,

m)^FG\n,

m<=NK} •

Графовой

грамматикой

будем

называть

совокупность

(AN,

АТ, Ам,

S,

P),

где AN

— конечное множество нетерминальных

сим­

волов;

АТ

— конечное множество

терминальных

символов;

Ам —

конечное множество

меток

дуг; S^AN — начальный нетерминаль­

ный символ; Р — конечное множество правил грамматики.

Каждое правило

грамматики представляет собой совокупность

вида Г= (G, Я, I , О), в которой

G e G l

(AN,

Ам),

и имеет

только

единственную изолированную вершину.

HeGl(AN\j

Ат,

Ам)

и

NH^0-

/ е Л ' н — входная вершина;

0^NH

— выходная вершина.

Г=

(G, Я, I , О)

можно

записать

Коротко правило грамматики

в виде

Л - + Я <

,

где Л—нетерминальный

символ,

соответствующий

значению

одной из вершин графа G.

Каждое правило определяет возможное преобразование вер­

шины, являющейся нетерминальным

символом.

Будем говорить, что граф Я непосредственно порождается из

графа

G в грамматике Г—G

=> Я, если существует такое

правило

Р = ( # , К,

/, О), что

G'

и G",

G'=R

1)

G может быть частью

графов

где

включает

NQ , содержащее только одну вершину —

n s

;

2)

Я может быть частью графов Н'

и Я", если

а)

H"==.G"

,

б)

Н'

=К .

в)

FH

= FH,

U FH»[}{(m,

а,

/ ) | (m,

a,

n Q ) e / 7

G ,

т = ^ " 0 }

U{(О,

а,

/п) | ( я s

,

a,

m)<=FG,

тфп

J

U ((.О,

а,

/ ) | ( л а

,

а,

ftjefo}

•

Таким

образом, получение

Я

из

G,

следуя правилу

Л—>К1 о,

С О С Т О И Т

в

подстановке в граф

G вместо

вершины

значения

Л

из графа /С. При этом дуги,

входящие

в

« s

,

заменяются

дугами,

ведущими в /, дуги, выходящие

из n s , дугами, выходящими из

О,

любая петля в вершине п 8

заменяется

дугой из О в /.

грамма-

Будем

говорить, что граф

Я

выводится

из

графа

G в

тике

*

такая

последовательность

хи

Г — G=> Н, если существует

Х2,---,хп,

г

каждое x^Gl

(AN[}AT,

Ам).

что

При

этом

G = x j ,

Я = д ; п и Xj=>

для t'= 1,2

п — 1.

г

Г,

есть множество

графов

Язык L , определенный грамматикой

вида

*

L r = {Ge=Gl(AT,

AM)\Sr

=>

G,

г

13*

195