Page 104 - 4496

Матриця добутку може бути отримана за таким
правилом. Запишемо матрицю одного. зі співмножників,
потім у ній кожну клітку замінимо на матрицю, розмір якої
збігається з розміром матриці другого графа, а вміст дорівнює
порожній матриці, якщо відповідний елемент матриці
першого графа рівний 0, або збігається із вмістом матриці
другого графа, якщо елемент рівний 1. Такі матриці одержали
назву правильні клітинні матриці.

Таблица 3.5- Матриця суміжності графа добутку двох
графів
1a 1b 2a 2b 3a 3b
1a 1
1b 1 1
2a 1

2b 1 1
3a 1

3b 1 1

Семантика операції. Нехай є два блоки, що становлять
систему, що функціонує в загальному дискретному часі.
Кожний блок описаний графом, вершини якого зіставлені зі
станами блоку, дуга (i,j) визначає можливий перехід блоку зі
стану i у наступний момент часу. Блоки функціонують
незалежно й паралельно.
У цьому випадку можливі стани системи визначаються
станами блоків (декартовым добутком), а добутку відповідає
граф переходу системи в часі. Так, якщо в прикладі перший
блок перебуває в стані 1, другий у цей час перебуває в стані b,
те система перебуває в стані (1,b) і в наступний момент
можливі переходи в стан (3,a) або (3,b).
Завдання. Система складається із двох блоків, що
функціонують у загальному часі, і в кожний момент часу
змінює стан тільки один блок (послідовна робота блоків).

101