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

• Автор: Иорданский, Михаил Анатольевич
• Шифр специальности: 01.01.09
• Научная степень: Докторская
• Год защиты: 2001
• Место защиты: Нижний Новгород
• Количество страниц: 141 с. : ил

СОДЕРЖАНИЕ
Аннотация
ВВЕДЕНИЕ

ГЛАВА 1. КОНСТРУКТИВНЫЙ ПОДХОД

К ПРЕДСТАВЛЕНИЮ ГРАФОВ

§1. Определения основных понятий и обозначения

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

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

§4. Базисы классов всех графов, мультиграфов и простых графов. ... 41 ГЛАВА 2. ДИНАМИЧЕСКАЯ СТРУКТУРНАЯ

ХАРАКТЕРИЗАЦИЯ ГРАФОВ

§1. Триангулированные графы

§2. Планарные графы
§3. Внешнепланарные графы
§4. Максимальные планарные и внешнепланарные графы
ГЛАВА 3. БАЗИСЫ ЗАМКНУТЫХ КЛАССОВ
ПЛАНАРНЫХ ГРАФОВ
§1. Класс всех планарных графов
§2. Внешнепланарные графы
§3. Триангулированные планарные графы
ГЛАВА 4. КАНОНИЧЕСКИЕ СУПЕРПОЗИЦИИ ГРАФОВ
§1. Достаточные условия реализуемости графов
каноническими Я-суперпозициями
§2. Экономное кодирование помеченных графов
§3. Экономное кодирование непомеченных графов
ГЛАВА 5. ОПТИМАЛЬНЫЕ ЛИНЕЙНЫЕ
РАЗМЕЩЕНИЯ ГРАФОВ
§1. Постановки задач и обзор результатов
§2. Свойства минимальных плоских нумераций
вершин деревьев
§3. Алгоритм построения минимальной плоской нумерации
вершин дерева
ГЛАВА 6.ПРИБЛИЖЕННЫЕ РЕШЕНИЯ ЗАДАЧИ ПОСТРОЕНИЯ МИНИМАЛЬНОЙ НУМЕРАЦИИ
ВЕРШИН ДЕРЕВА
§1. Верхняя оценка длины дерева при минимальной
плоской нумерации
§2. Асимптотика длины дерева при минимальной
плоской нумерации
§3. Об эффективности приближенных решений задачи
построения минимальной нумерации вершин дерева
Приложение - Диаграммы обыкновенных планарных графов, не реализуемых без использования операций < Н®е >-скпейки
заданных типов
Литература
Аннотация
Рассматривается функциональный подход к системе ”графы с операциями”, в рамках которого решены основные задачи, относящиеся к проблематике выразимости и полноты. Показано, что при использовании различных систем операций мощность множества замкнутых классов графов может быть континуальной, счетной или конечной. При этом реализуются все логические возможности для порождения замкнутых классов: существуют классы с конечными и счетными базисами а также классы, не имеющие базиса. Число базисов может быть счетным или конечным, включая наличие единственного базиса.
Приводится динамическая структурная характеризация ряда замкнутых классов графов - необходимые и достаточные условия наследования их свойств при выполнении над графами операций объединения с пересечением. Получены конечные конструктивные описания классов планарных графов, замкнутых относительно различных систем таких операций.
Даны приложения конструктивных описаний графов к задачам экономного кодирования и оптимального линейного размещения графов.

Доказательство проведем индукцией по г. Пусть і = 1. Покажем, что из графа ÿi = ((К1оК2)К0оС1)К0 можно получить любой граф, содержащий петли.
Вначале пострим граф, содержащий |П((?)| изолированных вершин, используя операции, реализующие графы вида (gogi)G, где g - текущий граф (вначале g = зх), G = (Сі о К2)К0.
Затем соединим изолированные вершины ребрами таким образом чтобы получить при этом граф, изоморфный подграфу графа G, не содержащему петель и изолированных вершин. Это делается с помощью операций, реализующих графы вида (д о g)G, где g - текущий граф, С — К2 и отождествляемые вершины смежны в д. Образующиеся при этом дополнительные петли и изолированные вершины склеиваются затем в одну петлю операциями унарной склейки текущего графа по С или К соответственно.
Эта петля может быть перенесена на любую вершину графа, инцидентную ребру, или сохранена в виде изолированной петли (результирующий граф G содержит хотя бы одну петлю). При наличии в графе G более одной петли все они добавляются с помощью операций, реализующих графы вида (g oC)Ki. Граф Ci можно построить из д с помощью операций унарной склейки.
Так как S(C1}C3,..., C2i-i) = S(C1} C3,..., C2i.3)US(C2i.i) и ді_г <*= (9і)К2, то для доказательства индуктивного перехода достаточно показать, что из графа ді — ((Кі о К2)К0 о С2і-і)Ко можно получить любой граф G, принадлежащий S{C2i-1).
Используя операции, реализующие графы вида (gogi)G, где g - текущий граф (вначале g = 3;) и G = (КіоС2і-і)Ко {К совпадает с изолированной вершиной в Зі), к графу дг добавляется столько изолированных ребер, сколько нетривиальных компонент связности содержит граф G.
Далее с помощью операций бинарной склейки по G = (К2оС2і-і)Ко, где одна вершина из К2 совпадает с изолированной вершиной в дг, для каждой