Page 106 - 4496

шляхом перейменування вершин, то такий граф буде
результатом добутку графів.
Є ще один критерій того, що граф не є добутком.
Якщо Q=<C,T>, G=<A,R>, H=<B,S>, і Q=Gxh, то має місце
умова: |C|=|A||B|. Отже, якщо число вершин n графа є просте
число, то він не може бути представлений добутком графів.
Якщо n не просте й може бути виражене як n=kr, де k і
r більше за 1, то можна ставити завдання перевірки цього
графа на можливість представити його у вигляді добутку.
Якщо граф містить n вершин, то для перевірки його необхідно
у загальному випадку провести n! перейменувань. Уже для
n=6 це число складе 720, для n=8 уже більше 40000. Тому
виникає необхідність скорочення обсягу обчислень.
Можливість скорочення заснована на наступному
твердженні.
Якщо граф представлений у вигляді правильної
клітинної матриці, то при перейменуванні вершин, пов'язаних
з перейменуванням вершин в одному графі-співмножнику,
матриця залишиться правильною клітинною матрицею. Точно
так само, якщо матриця не є правильною клітинною, то
перестановка імен, пов'язана зі зміною імен в одному графі-
співмножнику, її правильною не зробить. Це значить, що
якщо n=kr, то необхідний перебір варіантів можна скоротити
в k!r! раз. Наприклад, перебір для n=6 скоротиться до 60
(6=23, скорочення в 2!(3!=12 раз).
Алгоритм декомпозиції
Розглянемо ще раз операцію добутку. Якщо вершина а
в першому графі-співмножнику має ступінь заходу d a, а
вершина b у другому графі має ступінь заходу d b, у
результуючому графові вершина (a,b) буде мати ступінь
заходу (d ad b). Те ж саме можна сказати й про ступінь
результату результуючого графа.
Алгоритм заснований на тому, що для кожної i –тієї
вершини графа визначаються всі можливі розкладання її
ступенів заходу si=r it i, тобто передбачається, що якщо
завдання вирішується й цій вершині зіставлена пара (х,у), то ці
вершини мають ступені заходу r i і t i відповідно. Те ж саме
стосується ступеня результату вершини i: t i=p iq i.

103