Page 105 - 4496

Визначите операцію над графами, що описують переходи
блоків системи, результатом якої є граф переходів системи.

3.19 Декомпозиція графів

Завдання декомпозиції формулюється так: задано граф,
для якого необхідно визначити, чи є він добутком двох графів.
У випадку позитивної відповіді потрібно знайти графи -
співмножники.
Семантика завдання. Описана система, що функціонує
в часі. Необхідно визначити, чи можливо її представити у
вигляді системи із двох незалежних блоків, як описано вище.
У цьому випадку систему можна описати набагато простіше.
Так, якщо система має 100 станів, то при позитивному
розв'язку вона буде описуватися як два блоки, кожний з яких
має тільки десять станів.
У попередньому розділі було показано, що якщо граф
представимо добутком, то його матриця буде мати вигляд
правильної клітинної матриці.
Розглянемо ще раз приклад, наведений у попередньому
розділі в табл. 3.5. Припустимо, що в системі стани
пронумеровані в такий спосіб: 1=(1a), 2=(1b), 3=(3b), 4=(2b),
5=(3a), 6=(2a), тобто 3-тю і 6-ю вершини поміняємо місцями.
Тоді таблиця прийме вигляд і отримаємо табл. 3.6.

Таблиця 3.6 – Граф системи
1 2 3 4 5 6
1 1
2 1 1
3 1 1
4 1 1
5 1
6 1

Ця таблиця вже не буде правильною клітинною
матрицею, хоча вона описує граф, що збігається з вихідним з
точністю до назв вершин.
Отже, якщо матриця графа не є правильною
клітинною матрицею, але може бути отримана з неї
102