Файл: Горбатов В.А. Синтез композиции операционного и управляющего автоматов в вычислительной технике учеб. пособие.pdf
ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 05.08.2024
Просмотров: 64
Скачиваний: 1
совпадает с носителем модели, определяемой это |
событие, |
||||||
и (ѵі, Vj) взвешены отношением частоты |
их несовместного |
||||||
участия к частоте их совместного участия в событии |
|||||||
|
|
(fit |
~ ~ fit) |
+ (f l i — fl!) |
i . |
|
|
|
|
|
|
fit |
|
|
|
~ ~ |
(o„ |
ot) = |
Ml ~ ^ l + f a |
f |
(1-4) |
||
причем |
|
|
|
|
|
|
|
|
|
|
если |
(O', |
Vj) = oo; |
|
|
(v h V I) G |
U, |
если |
ÖG |
üj) |
является |
|
|
— — [vlt |
|
||||||
|
|
|
|
бо |
|
|
|
конечной величиной, отличной от нуля; V{='Vj, |
|
||||||
если і г ( Ѵ ь V j ) = |
°- |
|
|
|
|
|
|
Значение |
|
|
|
|
|
\ |
|
- |
f |
( » „ |
f tj |
+ |
|
|
|
|
öS |
|
|
|
|
|
|
называется значением производной на дуге ( v it Vj).
Производная-^- графа G по событию S характеризует
Рис. 1-1
степень неоднородности участия компонент графа G в собы тии 5 .
Проиллюстрируем понятие производной от графа по со бытию на двух примерах.
Пусть заданы граф (рис. 1-1) и событие 5 на нем: «об разование ребрами остова графа «G». Найти производную от графа G по событию 5 ,
7
Заданное событие определяет модель, матрица инцидент ности которой имеет следующий вид:
а |
ъ |
с |
d |
е |
1 |
1 |
0 |
1 |
0 |
1 |
1 |
0 |
0 |
1 |
1 |
0 |
1 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
1 |
0 |
0 |
1 |
1 |
0 |
1 |
1 |
1 |
0 |
0 |
1 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
1 |
В этой матрице каждому столбцу взаимно однозначно со ответствует ребро графа G (элемент, входящий в событие), строке — совокупность ребер, образующая остов графа (ус ловие, при котором заданное событие имеет место).
с
Частотная матрица отношений F, соответствующая этой матрице, представляет собой следующее:
|
Ь |
с |
d |
е |
|
2 |
2 |
3 |
3 |
F = ( ? X Q = |
5 |
2 |
3 |
|
2 |
4 |
2 |
|
|
|
3 |
2 |
5 |
|
|
3 |
2 |
2 |
|
8
dG |
u |
, |
, |
—— представляет собой граф, носитель которого есть |
а, о, |
||
до |
|
|
|
с, d, е , и пара вершин этого графа смежны, если значение производной на дуге, образующейся этими вершинами, от лично от нуля. Вычисляя значения производной на дугах гра-
,dG
d G |
/Q U \ __ /д а |
^ f a b -Ь f bb |
_ 5 - 2-2 + 5 |
= 3; |
||
dS |
K ' |
’ ~ |
f ab |
2 |
|
|
— (a, q) = |
fna- -■^ac + .^g- = |
5 —2-2 + 4 |
= |
2,5; |
||
|
|
|
|
f a c |
|
|
dG |
/у |
\ _ fdd —2/de 4- fee |
_ 5 2-2 + 5 _ g |
|||
ÖS |
K |
- |
fde |
2 |
|
|
|
|
i |
|
|
|
|
имеем граф |
(рис. 1-2). |
|
|
|
||
В качестве |
второго |
примера |
рассмотрим |
граф G |
||
(рис. 1-3 а), на котором задано событие -S: «образование реб
рами базисного цикла относительно остова (рис. 1-3, 6) гра фа». Вычислить производную от графа G по событию S.
Цикломатическое число графа равно 3
7 —5 + 1 = 3.
Следовательно» имеем три базисных цикла, при выборе которых заданное событие имеет место, другими словами,
\
9
при выборе которых данное событие истинно. Таким обра зом, заданное событие определяет модель вида
а |
ь |
с |
d |
е |
g |
h |
1 |
1 |
1 |
1 |
1 |
0. |
0 ' |
Q — ■0- |
0 |
1 |
1 |
1 |
1 |
0 |
0 |
0 |
1 |
1 |
0 |
0 |
1 |
Этой модели соответствует частотная матрица отношений вида
|
а |
b |
с |
d |
е |
g |
h |
|
1 |
1 |
1 |
1 |
1 |
0 |
0 |
|
1 |
1 |
1 |
1 1 |
1 |
0 |
0 |
F = |
1 |
1 |
3 |
3 |
2 |
1 |
1 |
Qt X Q = |
1 |
3 |
3 |
2 |
1 |
1 |
|
|
1 |
||||||
|
1 |
1 |
2 |
2 |
2 |
1 |
0 |
|
0 |
0 |
1 |
1 |
1 |
1 |
1 |
|
0 |
0 |
1 |
1 |
0 |
0 |
1 |
Вычисляя значение производной |
согласно определению |
производной от графа, получаем граф |
- (рис. 1-4). Анали- |
|
• ü u |
зируя граф ——, замечаем, например, что ребра с (а) и d (b)
до
одинаково интенсивно участвуют в заданном событии.
10