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

Представления графов

Определение операций склейки

Суперпозиции графов

Порождающие базисы

Структура и способы порождения
H – замкнутых классов графов

Примеры конструктивных описаний

Классы всех графов и мультиграфов

Обыкновенные графы

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

Планарные графы

Влияние внешних ограничений

Эйлеровы графы

Двудольные графы

Гамильтоновы графы

Избыточность конструктивных описаний

Вершинная и реберная избыточность

Вершинная избыточность эйлеровых графов

Реберная избыточность гамильтоновых
планарных графов

Обратные задачи

Конструктивные описания и характеристические свойства
для классов связных графов

Конструктивные описания и характеристические свойства
для классов графов, допускающих различное число компонент связности

Приложения конструктивных описаний

I. Экономное кодирование графов

Кодирование помеченных (r,s) - деревьев

Декодирование помеченных (r,s) - деревьев

Оценка длины кода помеченного (r,s) - дерева

Кодирование непомеченных (r,s) - деревьев

Декодирование непомеченных (r,s) - деревьев

Оценка длины кода непомеченного (r,s) - дерева

Примеры кодирования помеченного и непомеченного (3,1)- дерева с 9 вершинами

Кодирование помеченных s - деревьев

Декодирование помеченных s - деревьев

Кодирование непомеченных s - деревьев

Декодирование непомеченных s - деревьев

II. Оптимальные нумерации вершин

Свойства минимальных нумераций
вершин деревьев

Выбор суперпозиций

Алгоритм построения минимальной
плоской нумерации

Эффективность алгоритма

Пример минимальной и минимальной плоской нумераций