Исследование количественных и сложностных характеристик наследственных классов графов

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

Оглавление
Введение
1. Наследственные классы
1.1. Терминология
1.2. Определение и примеры наследственных классов
1.3. Энтропия
2. Критические классы
2.1. к-дольные графы и ранг
2.2. Лемма о матрицах
2.3. Энтропия и ранг
2.4. Критические классы
2.5. Примеры и следствия
3. Классы ранга
3.1. Слои и ярусы
3.2. Константный ярус
3.3. Полиномиальный ярус
3.4. Экспоненциальный ярус
3.5 Факториальный ярус
4. Независимые множества
4.1. Простые и сложные классы
4.2. Операции над классами графов
4.3. Сильно наследственные а-простые классы
4.4. Граничные классы
5. Некоторые а-простые классы
5.1. Область эффективности переборной стратегии
5.2. Класс Сгее(Г,Л8)
5.3. Класс Сгее(С)
5.4. Классы Егее(Р$) и Ргее^Р^ + Р3)
6. Кодирование графов
6.1. Универсальное кодирование
6.2. Оценки трудоемкости
Литература

Введение
Изучение тех или иных классов графов (деревьев, планарных графов, совершенных графов и т.д.) составляет содержание значительной части работ по теории графов и ее приложениям. В последние десятилетия заметен интерес к рассмотрению не отдельных классов, а семейств классов. Среди фундаментальных проблем, сама постановка которых выводит на такой уровень общности, можно отметить две: анализ сложности задач на графах и экономное представление графов.
Развитие теории сложности вычислений способствовало укоренению пессимистического взгляда на возможность существования эффективных алгоритмов для многих представляющих практический интерес задач на графах. Один из возможных выходов - сужение задачи, наложение дополнительных ограничений на класс рассматриваемых графов. Иногда учет этих ограничений, т.е. принадлежности графа некоторому классу, приводит к созданию полиномиального алгоритма для решения задачи. В других случаях удается доказать, что задача для графов из того или иного класса остается ИР- трудной. К настоящему времени накоплено огромное количество фактов того и иного рода. Придать этому процессу целенаправленность и систематичность можно, переходя от рассмотрения отдельных классов к рассмотрению представительных семейств классов. В идеале можно надеяться на исчерпывающую характеризацию «простых» и «сложных» классов из некоторого семейства и один из результатов настоящей работы показывает, что этот идеал иногда достижим.
Похоже обстоит дело с проблемой экономного представления графов. Если принять в качестве стандарта кодирование графов словами двухбуквенного алфавита, то любой (обыкновенный) граф с п вершинами может быть представлен словом длины п(п - 1) / 2. При отсутствии какой-либо априорной информации о кодируемых графах такое представление оптимально по длине слова, если же мы имеем дело с графами из некоторого более узкого класса, чем класс всех графов, то, вообще говоря, их можно закодировать более короткими словами. Возможность сжатия определяется
(последнее неравенство следует из того, что 5(п) > 2 при всех

Из (2.7) следует, что Н(Х) < - н а при любых

достаточно больших т и /, удовлетворяющих условиям леммы 2.1. Устремим т к бесконечности. Как видно из условий леммы 2.1, ? можно выбрать так, чтобы было
/ = о(т). Тогда #(—]-» 0 , поэтому а —» 0 и в пределе

получаем И(Х)<

При к = 1 вместо (2.6) получается более простое неравенство
1У | | у х^пта + р(п)
лп ^ Ия-тг ’
итерируя которое и переходя затем к пределу при т ->со, получаем И(Х) = 0. □
2.4. Критические классы
Пополнение к -дольного графа назовем правильным, если каждая доля порождает в этом пополнении пустой или полный подграф.
Лемма 2.3. Для любого к -дольного графа М существует такой к -дольный граф М, что в любом