Конструктивное описание графов

Рассматриваются процессы построения графов с помощью операций объединения с пересечением (операции склейки). Изучается структура замкнутых классов системы (Q,C), где Q-множество всех графов, С — суперпозиция операций склейки. Установлено, что каждый замкнутый класс графов имеет единственный базис; существуют классы со счетными базисами; мощность множества всех замкнутых классов графов континуальна. Таким образом, система (Q, С) занимает промежуточное положение по структуре замкнутых классов между системами ( ,С) и ( ,C), где — множество всех функций алгебры логики, Рk — множество всех функций k-значной логики, к ≥ 3. Выделены конечные базисы классов всех графов, мультиграфов и простых графов.

Введение…………………………………………………………………………………………………………3
Глава 1. Конструктивное описание графов: елементный и операционный базисы, структура и способы порождения замкнутых классов графов
§ 1. Определения основных понятий и обозначения……………………4

§ 2. Свойства операций склейки……….…………………………………6

§ 3. Структура замкнутых и if-замкнутых классов графов.…………….8

§ 4. Базисы классов всех графов, мультиграфов и обыкновенных графов…………………………………………………………………………...9
Глава 2. Условия наследования графов
§1. Условия наследования триангулированности графов......................11

§2. Условия наследования планарности графов…………………..…...12

§ 3. Условие наследования планарности максимальных графов………………………………………………………………………....15
Заключение……………………………………………………………………

ЛИТЕРАТУРА…………………………………………………………….….27