книги из ГПНТБ / Алферова, З. В. Математическое обеспечение экономических расчетов с использованием теории графов

;нач

цел

Б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

няется графом в соответствии с правилами

грамматики.

Процесс

преобразований продолжается до тех

пор, пока не останется ни

одной нетерминальной вершины.

Определим теперь парные грамматики. Под парной

граммати­

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

над одними и теми же

алфавитами вместе с соответствиями,

установленными

между

правилами этих грамматик и между

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

вершинами

в правилах.

Пусть заданы:

1)

алфавиты AN, Ат, Ам\

2)

графы G и Н из множества Gl

(AN,

Ат,

Ам);

3)

нетерминальные вершины графа G •—

Nl={ne=NG\VG{n)

е Л „ } ;

4)

нетерминальные вершины графа Н —

NH={n^NH\VH(n)^AN}

,

V „ e / V o .

VG(n)

= Vn(h(n))

•

Парная

грамматика

определяется

как Г=

(AN,

Ат, Ам,

S,

Q),

где

AN,

Ат,

Ам — соответственно

алфавиты нетерминальных, тер­

минальных

символов и

меток

дуг, S^AN

— начальный

символ, а

Q —конечное

множество

наборов

(/, q,

к).

В этих

наборах /, q —

правила

таких графовых грамматик,

что

если

/

есть

правило

А—^G'o

и q — правило А1—>HTV,

то А=А'

и h — нетерминальная

вершина спаренных графов G и Н.

Пусть Г— (AN, AT, AM, S,

Q) — парная

грамматика.

Если

q =

= (/, р, / i ) & Q , то / называется левым правилом

q,

а

р — правым

правилом q, h — спаренная нетерминальная вершина q.

вой

Графовая

грамматика Г=

(AN, Ат, Ам,

S,

Р)

называется

ле­

(правой)

грамматикой,

если

Р представляет

собой

множест­

во левых (правых) правил Q.

Г,

Язык,

порождаемый

левой

(правой)

грамматикой

называ­

ется левым

(правым) языком.

Язык, порождаемый парной грамматикой Г, состоит из упоря­

доченных пар графов левого и правого языков.

Парная грамматика определяет пары графов, получаемые из

одного и того же начального

графа параллельно. На

каждом

эта­

пе преобразований имеется пара графов,

каждый

из

которых

включает

несколько нетерминальных вершин и соответствия

меж­

ду

этими

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

вершинами. При каждом

преобразо­

вании пара

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

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

вершин,

по одной

из графа,

заменяется в соответствии

с правилами

парной

грамма-

Спаренный граф X над алфавитами AN,

Ат,

Ам

определяется

как

X=(G, Я, h), где G и H^Gl

(AN{jAT,

Ам),

a

h — нетерми­

нальная вершина спаренных графов G и Я.

AN, Ат,

Терминальный спаренный граф Z

над

алфавитами

Ам

— это спаренный граф вида

Z={G,

Я,

А), в котором все вер­

шины графов G и Я являются

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

В

этом

случае

можно записать как Z— (G,

Н).

Пусть задана парная грамматика r=(AN,

Ат, Ам,

S,

Q) и па­

ра графов X=(GX,

Нх, hx)

и У = (Gy,

Ну, hy)

над алфавитами

AN,

Ат, AM-

выводится из X,

сле­

Будем говорить, что У непосредственно

дуя грамматике Г X=> У, если существует

правило

(/,

р,

h)^P,

нетерминальная

вершина п

в графе

G и нетерминальная

вершина

Будем

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

У выводится

из

X,

следуя грамматике Г

#

X

г<=>У,

если

существует

такая

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

опарен-

ных

графов

2 Ь

Z2,...,Zn

над

алфавитом

(AN,

А-г, Ам),

что

Х =

— Z\,

y=Zn

и Zi

Z j + i

для

i=

1, 2, 3,...,

ft—

1.

Язык,

порождаемый

грамматикой

Г,

называется спаренным

языком, если он

определяется

как

L={X\X

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

спа-

*

ренный граф над алфавитами AN, АТ,

А

М И Sr

=> X).

Парная

грамматика

Г — однозначная,

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

грамматики,

принадлежащие

Г, — однозначны

и грамматика

Г не

Используя однозначную парную грамматику,

можно достаточ­

но легко

найти

элемент правого языка, соответствующий данному

элементу

левого

языка. Пусть Г — однозначная

парная граммати­

ка, левый

язык

которой — множество строк, а правый язык —мно-

ван следующим образом. Прежде всего для

строки X выполняется

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

левой грамматики, ре­

зультат которого представляется в виде вывода

S=> Zx=> Z 2 = ^ . . .=>Zn

= X •

После этого, используя правила правой

грамматики и

соответст­

вия парной грамматики, строку X преобразуют в граф X'. Процесс

преобразования начинается с графа 5,

содержащего

единствен­

ную вершину, и включает точно п шагов.

Таким образом, парные грамматики

дают формальный аппа­

Изучение парных грамматик является

перспективным

не толь­

ко с точки

зрения формализации процессов трансляции, но и в

связи с широким применением графов как

в теории программиро­

вания,

так

и в организации процессов обработки информации.

В

этой

связи рассмотрим следующее

расширение

графовой

над алфавитами Ау,

Ам;

3) Я , (AV,

Ам)

=G\(AV,

Л м ) — набор всех Я-графов

первого

уровня;

над алфавитами Л у, Ам

4) Я-граф

к-го

уровня

— это

граф над

Hi

(Лу, Ам), Ам, содержащий хотя бы одну вер­

шину Нк-\\

5) Нк (Av,

Ам)

= {Х\Х — это Я-граф/с-го уровня};

6) Н(Ау, Ам) =\Зк2(Ип — это множество всех Я-графов

над ал­

фавитами Av,

АМ-

Введем теперь для каждой терминальной вершины дополни­

тельный параметр — метку. Теперь каждая терминальная

вершина

одинаковыми метками разрешается производить только

в

одном

и том же графе в пределах иерархии. Таким образом,

не

могут

Я-графа, а также

вершины,

расположенные в различных графах

одного уровня.

Введение меток облегчает процесс компиляции из строчного

языка в язык графов. В этом случае метки вершин

выполняют

примерно те же функции, что и таблица

символов.

В заключение

приведем

пример

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

АЛГОЛ-про-

граммы (рис. 41)

в виде блок-схемного графа

(рис. 42) .получен­

ного в результате

преобразований по правилам

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

for

q.== I step 1 unti I m do

if

abs (af p, q.]) > у then

begin у : = abslafp, a])\i

.~p; k:~o end

etstg: = y

end

Рис. 41. Пример

АЛГОЛ-пропраммы

Следует особо подчеркнуть

перспективность

использования