Конструктивная теория графов и еыо приложения.

Description

В основу настоящей книги положены результаты исследований автора за последние два десятилетия. Предлагаемая конструктивная теория графов основывается на методологии исследований принятой в математической кибернетике [37], предполагающей, совместное рассмотрение схемы и функции управляющей системы (УС). Рассматриваемый класс УС определяется множествами графов, обладающих заданными характеристическими свойствами. Схемы УС описывают процессы построения одних графов из других с помощью теоретико-множественных операций объединения и пересечения, называемых операциями склейки. На операции склейки накладываются ограничения, обеспечивающие сохранение заданного характеристического свойства графов. Результирующие графы выступают при этом в роли функций, реализуемых схемами УС. Конструктивный подход, рассматривающий графы как результаты некоторых процессов их построения, позволяет генерировать графы с требуемыми характеристическими свойствами, основываясь на алгоритмах их синтеза. Определяемая при этом динамическая структурная характеризация различных классов графов позволяет эффективно ре- тать прикладные задачи на графах.