Файл: Зингер И.С. Обеспечение достоверности данных в автоматизированных системах управления производством.pdf

входящая в

вершину

графа,

что

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

этому

контуру).

Силой контрольной связи

(Ui,

Uj) (/ <i

i) графа

U по­

токов информации

назовем

величину,

показывающую,

во сколько

раз уменьшается

вероятность

выхода

досто­

Дадим некоторые определения.

1. Подграфом графа U, ограниченного вершинами Ux и

Uy,

называется граф, содержащий Bqe вершины Ui

гра­

фа

U, для которых индекс i удовлетворяет

неравенствам

х =gC i ^

у,

и все дуги графа U, соединяющие вершины,

вошедшие в подграф. Подграф графа U, ограниченный вер­

шинами Uх

и Uy,

будем обозначать через Uх, у .

Пример.

Подграф £73,7 графа

U (рис. 8) содержит

вер­

шины U3,

Uit Ub,

Uu,

U-, и дуги (U3, U^,

(Ui,

U3),

(UB,-'

Щ,

(U6, Un), (U7,

U6),

(U7, ив).

Подграф

U3,7

приведен

на

рис.

9.

2.

Циклической

Структурой Кху, ограниченной

вер­

шинами £/Л., Uv {х ^

у ) , будем называть подграф Ux,

у г Р а "

фа U,

в котором для каждой вершины имеется дуга, ис­

также является циклической структурой (/С?,?)-

Подгра-

.фы U-2,4 и £ / 0 ) 8 того же графа U не являются

циклическими

•структурами, так как

граф

Ui}i

содержит

вершину

U2,

которая не имеет ни входящей, ни исходящей дуги, а граф

•U6,s содержит

вершину

Us,

которая

не имеет

исходящей

из нее дуги. Графы £/6 ,7 ,

£ / 2 , 4 и С/6 ) 8

показаны на рис. 10.

3, Циклическая структура КХ}У

содержится

в цикли­

ческой структуре КХ',у',

если а: <

ж' и т/'^г/или

х^х'

и

•у'

<С У- (Кх,у

и

Kx'.v'

— подграфы одного и

того же гра­

фа U.) Например, циклическая структура Кй,ч содержит­

ся

в циклической структуре

i f 3 ) 7 .

4. Простой

циклической

структурой Кх,у

графа

U

называется циклическая структура, которая не содержит

внутри себя другой циклической структуры ни при какой

нумерации

вершин графа.

Циклическая структура Къ<-, графа U (рис. 8) имеет

два выхода

С75 и UB

(входные'дуги

{ U v Ub)

и

{ U 2 ,

UB))

и один выход Е/7. Циклическая структура КБ)7

не простая,

так как в ней содержится циклическая структура

KSt7,

^которая тоже

имеет два входа Ue

и

С/7.

верной информации на входах графа).

Рассмотрим

простую

циклическую структуру

К х > у

графа

U. Пусть вершина

Uv — контролирующая, верши­

на Ux

— входная, а дуга

( U v , U х ) — контрольная

обрат­

ная связь. Обозначим

вероятность того, что

информация

от входа в вершину

U х

до входа в вершину

Uy проходит

без искажений,

через

qa.

туре Кх,у искажена, то

в контролирующей вершине

с вероятностью qy = qKmp

это обнаруживается и по обрат­

образования

данных по контуру

Кх,у.

С вероятностью

Ру = 1 — qv

в контролирующей

вершине

Uy не обнару­

появляется

с вероятностью

(1 — qe),

и с

вероятностью

(1 — qa)-Py

эта информация

выдается

из

контура. С ве­

роятностью

(1 — q\)-qy

происходит

повторный

прогон

данных

по

контуру. С

вероятностью

(1 — <1г)-Ру

[(1 —

— 4z)-qy\

происходит искажение и выдача искаженной ин­

ностью [(1 — qa)'qy]2 происходит третий

прогон данных

•=*по контуру. С вероятностью (1 — qz)-Py

[(1 — qz)-qy\i

дачи искаженных данных

из контура КхУ

равна

(1 -

дг) • Ру

+ (1 - д.) • Pv • [(1 -

дг) • д„]

+

+ ( 1 - ? в ) . р 1 , . [ ( 1 - ? , ) . ? 1 / ] * +

1 — (! — 9г )-7и

Вероятность </ того, что в контуре Kxv

не произойдет

искаженпя информации,

равна

g u w -

1 _ { 1 _ ( ? г ) . 7 и - р И . ( 7 з . 9 ] у -

Вероятность того, что

информация за один проход по

контуру

KXtV

не будет

искажена,

обозначенная нами

искажена ни в какой вершине

подграфа Uх,у-г

графа U.

Отсюда,

учитывая, что искажение

информации в верши­

нах

происходит независимо,

получаем

дг =

g.x-g.t+i • • • qu-i=

П

Qi-

Таким образом,

х <

i < у

контуре

вероятность

д того, что в

Кх,ъ

не произойдет

искаженпя

информации,

равна

п

q i

Р у +

1 1

11

Если

разорвать

обратную

связь

контура Кх,у, то ве­

роятность того, что в контуре

Кх,у

не произойдет иска­

жения информации, равна дг

=

П

Отсюда получаем,

что

сила контрольной

связи

контура Кхл равна

1

Р

у +

П 0, "

к < i < V

упрощенно

й-а порядок

вычисле­

Укажем несколько

шины графа U. Сначала выбираем любой простой

контур

Кх,у

графа U и заменяем граф U на граф Г/'1', полученный

из графа U заменой простого контура

К^,,, на вершину

U'х,

из которой исходят все дуги, исходящие из контура

Кх>у

(из вершины иу), и в которую

входят все дуги,

входившие в контур Кх>и. Вершине

Uх

графа Uw

припи­

сывается вероятность достоверного

преобразования даи-