Там, где задача раскраски усложнена дополнительными условиями одноцветности вершин, эффективным может оказаться и подход, предполагающий ... - Большая Энциклопедия Нефти и Газа



Выдержка из книги Алексеев А.С. Исследования по прикладной теории графов


Там, где задача раскраски усложнена дополнительными условиями одноцветности вершин, эффективным может оказаться и подход, предполагающий нахождение наибольшего пустого или полного подграфа, а затем группирование около вершин, вошедших в этот подграф, остальных вершин заданного графа. С помощью этого подхода, как показано в [26], можно решить такие задачи, как минимизация длины кода состояний асинхронного автомата, сжатие таблицы переходов автомата ( по строкам и столбцам), параллельная декомпозиция автомата, упрощение системы булевых функций, описывающих асинхронный автомат. Точно так же можно решать и все остальные задачи, перечисленные выше. Из рассмотренных здесь подходов к решению задач логического проектирования данный подход единственно пригоден для решения таких задач абстрактного синтеза автоматов, как минимизация числа состояний синхронного автомата и его декомпозиция.

(cкачать страницу)

Смотреть книгу на libgen

Там,  где задача раскраски усложнена дополнительными условиями одноцветности вершин,  эффективным может оказаться и подход,  предполагающий нахождение наибольшего пустого или полного подграфа,  а затем группирование около вершин,  вошедших в этот подграф,  остальных вершин заданного графа.  С помощью этого подхода,  как показано в [26],  можно решить такие задачи,  как минимизация длины кода состояний асинхронного автомата,  сжатие таблицы переходов автомата ( по строкам и столбцам),  параллельная декомпозиция автомата,  упрощение системы булевых функций,  описывающих асинхронный автомат.  Точно так же можно решать и все остальные задачи,  перечисленные выше.  Из рассмотренных здесь подходов к решению задач логического проектирования данный подход единственно пригоден для решения таких задач абстрактного синтеза автоматов,  как минимизация числа состояний синхронного автомата и его декомпозиция.