Спецглавы математики и их приложения к задачам электромеханики и теории управления. Катрахова А.А., Купцов В.С

Радиус графа равен 1, диаметр равен 2. Центр графа – вершина x2; медиана графа – вершина x2.

Задача 2. Найти сильные компоненты графа на рис. 6.12.

x1 x2 x3

Рис. 6.12. Граф к задаче 2

Решение

Для данного графа матрицы R, Q и S имеют вид:

250

В соответствии с матрицей S сильные компоненты графа: х1,х2,х6,х7 – первая сильная компонента; х3,х4,х5 - вторая сильная компонента.

Задача 3. Найти кратчайшие пути на графе методом динамического программирования (алгоритм Беллмана-Форда).

Программа для решения. uses crt;

const nv=6;n=4;k=1;m=100; w:array[1..nv,1..nv] of integer=

((0,5,m,m,m,9),

(5,0,7,m,9,m),

(m,7,0,5,m,10),

(m,m,5,0,2,m),

(m,9,m,2,0,11),

(9,m,10,m,11,0)); var

mv: array[1..nv] of integer; P:array[1..nv,1..nv] of integer;

i,j,r,b,z,d:integer; C:array[1..nv,1..nv] of integer;

begin clrscr;

251

for i:=1 to nv do begin for j:=1 to nv do write(' ',w[i,j]:5); writeln;

end;

writeln;

for i:=1 to nv do P[1,i]:=w[i,k]; for z:=2 to nv-1 do

for i:=1 to nv do begin d:=2*m;

for j:=1 to nv do begin r:=w[i,j]+P[z-1,j];

if r<d then begin d:=r; b:=j;end; end;

P[z,i]:=d; C[z,i]:=b; end;

mv[1]:=n; mv[nv]:=k; z:=nv-1;

while z>1 do begin mv[nv-z+1]:=C[z,mv[nv-z]]; z:=z-1;

end;

for i:=1 to nv do write(' ',mv[i]); writeln; writeln;

for i:=1 to nv do write(' ',P[nv-1,i]); readln;

end.

6.8. Применение теории графов для анализа устройств автоматики

Рассмотрим Т-триггер – автомат Мили.

252

Из аналитического описания Т-триггера, следует, что z(t) x(t),y(t) , то есть можно составить одну таблицу для z(t), значения которой будут одновременно содержать как z(t) так и y(t), табл. 6.1.

Таблица 6.1

Из таблицы видно, что если триггер находился, например, в состоянии z(t-1)={00} и на вход поступил сигнал x(t)=1, то триггер перейдёт в состояние z(t)={11}, которому соответ-

ствуют x(t)=1 и y(t)=1.

Граф Т-триггера, соответствующий его состояниям, показан на рис. 6.13.

x0/y0

Рис. 6.13. Графическое описание Т-триггера как автомата

Пусть задан автомат и его исходное состояние, тогда можно сформулировать три задачи его анализа.

1. Для известной последовательности входных сигналов найти соответствующую последовательность состояний автомата и его выходных сигналов.

2. Для данной последовательности выходных сигналов или состояний автомата найти соответствующую последовательность входных сигналов.

253

3. Найти последовательность входных сигналов, безусловно переводящую автомат из произвольного состояния в заданное.

Рассмотрим методы решения этих задач на примере логического устройства с памятью, представленного на рис. 6.14.

Рис. 6.14. Схема электрическая принципиальная логического устройства с памятью

Для описания автомата необходимо описать все его компоненты. Внутренняя структура используемого RS-триггера с инверсными входами представлена на рис. 6.15, а сокращённая и полная таблицы его состояний в табл. 6.2 и 6.3.

S

& Q

Рис. 6.15. Внутренняя структура RS-триггера с инверсными входами

254

Таблица 6.2 Сокращённая таблица состояний RS-триггера

Сокращённая таблица состояний неудобна для составления аналитического описания работы RS-триггера. Составим полную таблицу истинности всех входных и выходных сигналов триггера (табл. 6.3).

Таблица 6.3 Таблица истинности сигналов RS-триггера

В соответствии с табл. 6.3 выпишем СДНФ для сигнала

Q(t):

Q(t) S(t)R(t)Q(t 1) S(t)R(t)Q(t 1) S(t)R(t)Q(t 1)

S(t)R(t)Q(t 1) S(t)R(t)Q(t 1);

или после минимизации

255

Q(t) S(t)R(t) S(t)Q(t 1) S(t)Q(t 1) S(t)R(t) R(t)Q(t 1)

S(t) R(t)Q(t 1).

Перейдём к описанию автомата в виде последовательно связанной цепочки уравнений, позволяющих после соответствующей подстановки получить значение любого сигнала:

y1(t) S1(t) R1(t)y1(t 1);

y2(t) S2(t) R2(t)y2(t 1) y1(t) R2(t)y2(t 1);

S1(t) R1(t)x1(t) ;

R1(t) x1(t); R2 (t) x1(t)x2(t).

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

y1(t) x1(t)[x2(t) y1(t 1)];

y2(t) x1(t)[x2(t) y1(t 1)] y2(t 1)x1(t)x2(t).

Из выражений для y1 и y2 следует, что z(t)={y1(t),y2(t)}; y(t)={y1(t),y2(t)}; x(t)={x1(t),x2(t)}.

Поскольку y(t) = z(t), то анализируемое устройство является автоматом Мура.

Составим полную таблицу состояний (табл. 6.4).

Состояние z3={10} в устройстве никогда не возникает. Граф автомата представлен на рис. 6.16.

256

х1

Рис. 6.16. Граф логического устройства

Пользуясь полученными выше описаниями автомата, составим матрицу переходов (табл. 6.5).

Таблица 6.5 Матрица переходов логического устройства

Перейдём к анализу автомата.

Первая задача анализа: задана последовательность входных сигналов, то есть входное событие, например

х=х0 х1 х2 х0 х1 х3,

и исходное состояние автомата z0.

По графу (рис. 6.16) или матрице переходов (табл. 6.5) определяем последовательность выходных состояний:

z= z0 z0 z2 z1 z1 z2 z0.

Вторая задача: пусть задана требуемая последовательность состояний: z= z0 z2 z2 z1 z1 z0, найти соответствующее входное событие.

С помощью графа получаем: х=х1 (х0 х1) х2 (х0 х2) х3.

257

Третья задача анализа: найти входные события, безусловно переводящие автомат в заданное состояние z0, z1 или z2 из произвольного состояния.

Воспользуемся матрицей переходов (табл. 6.5).

В состояние z0 можно перейти из любого состояния, подав на вход автомата сигнал х3. В этом можно убедиться и на графе (рис. 6.16).

Аналогично в состояние z2 можно перейти из любого состояния, подав на вход автомата сигнал х1.

Состояние z1 недоступно непосредственно из z0, однако в z1 с помощью сигнала х2 можно прийти из состояния z2, которое, в свою очередь, всегда доступно из любого состояния по команде х1. Таким образом, безусловный переход в состояние z1 возможен в результате подачи на вход автомата последовательности х=х1 х2. Анализ графа подтверждает полученный результат.

Отметим, что задача безусловного перехода не всегда имеет решение в полном объёме.

258

Задачи для самостоятельного решения

Описать электрическую схему устройства графом и провести анализ работы схемы. Варианты задач приведены ниже.

259