Том 3, номер 4, 1996 г., Стр. 35-63

УДК 519.17 + 519.716.5
М. А. Иорданский
Конструктивные описания графов

Аннотация:
Рассматриваются процессы построения графов с помощью операций объединения с пересечением (операции склейки). Изучается структура замкнутых классов системы $(\mathscr G,C)$, где $\mathscr G$ – множество всех графов; $C$ – cуперпозиция операций склейки. Установлено, что каждый замкнутый класс графов имеет единственный базис; существуют классы со счетными базисами; мощность множества всех замкнутых классов графов континуальна. Выделены конечные базисы замкнутых классов всех графов, мультиграфов и простых графов. Найдены необходимые и достаточные условия наследования при выполнении операций склейки таких свойств графов, как триангулированность, планарность и максимальная планарность Получены элементные и операционные базисы соответствующих классов планарных графов.
Ил. 3, табл. 1, прилож. 1, библиогр. 10.

Иорданский М. А. ¹
1. Нижегородский государственный педагогический университет,
ул. Ульянова, 1, 603005 Нижний Новгород, Россия

Статья поступила 22 июня 1995 г.
Исправленный вариант — 18 июня 1996 г.