Исследование границ эффективной разрешимости в семействе наследственных классов графов

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

Оглавление
Введение
1 Критерий граничности и его применения
1.1 Терминология и обозначения
1.1.1 Множества, графы и подграфы
1.1.2 Множества вершин и метрические характеристики
1.1.3 Классы графов
1.2 П-граничные классы графов
1.3 Критерий граничности
1.4 Условия граничности классов ТиО
1.4.1 Применение критерия граничности к рассматриваемым
классам графов
1.4.2 Понятие древесной ширины графа и доказательство достаточного условия граничности классов Т и Ю
1.5 Граничные классы для задачи о наибольшем подграфе
1.5.1 Задача о реберно наибольшем Х-подграфе
1.5.2 Задача о вершиино наибольшем Х-нодграфе
1.5.3 Задача о наибольшем связном подграфе
1.5.4 Некоторые замечания
1.6 Применение понятия древесной ширины к поиску новых случаев граничности классов Тий
1.6.1 Покрытия и разбиения
1.6.2 Множества вершин и ребер

1.6.3 Задача о непересекающихся путях
1.6.4 Новые случаи граиичности классов Т и О
1.7 О граиичности классов ео(Т) и со(Т))
2 НМ-граничные классы относительно класса планарных графов
2.1 Гипотеза В. Е. Алексеева и ее варианты
2.1.1 Относительные П-граничные классы
2.1.2 Рассматриваемый случай
2.2 О сложности задачи НМ в классе планарных графов, не содержащих длинных порожденных путей
2.3 Полиномиальный алгоритм решения задачи НМ в классе планарных графов без порожденного подграфа Тцд*
2.3.1 Некоторые определения и вспомогательные результаты
2.3.2 Эффективный алгоритм решения задачи НМ в рассматриваемом случае
2.4 О сложности задачи о независимом множестве в классе планарных графов без порожденного подграфа Т$,к
2.4.1 Планарные графы, не содержащие больших порожденных звезд
2.4.2 Планарные графы без порожденного подграфа Т,к
2.5 Полиномиальная разрешимость задачи НМ в классе планарных
графов, не содержащих больших порожденных яблок
2.5.1 Минорно безапексные графы большой древесной ширины
2.5.2 Доказательство основного результата
3 Оценки мощности множества граничных классов
3.1 Количественные аспекты теории граничных классов
3.2 Задачи с континуальным множеством граничных классов
3.2.1 Задача о вершинной 3-раскраскс

3.2.2 Задача о реберной 3-раскраске
3.2.3 Некоторые замечания
3.3 Новые случаи полного описания множества относительных граничных классов
4 Минимальные сложные классы графов
4.1 Вопросы существования минимальных сложных элементов решетки наследственных классов графов
4.2 О несуществовании минимальных сложных классов для некоторых задач теории графов
4.3 Вычислительная сложность задач о списковом ранжировании
в некоторых классах графов
4.4 Минимальные сложные классы графов для задач о списковом ранжировании
4.4.1 О связях между минимальными сложными и граничными классами
4.4.2 Наследственные замыкания комет и молотов
4.4.3 Наследственные замыкания звезд и солнц
Литература

ДОКАЗАТЕЛЬСТВО. Пусть С — наибольший порожденный цикл графа
О. Т.к. граф (7 отличен от цикла, то существует вершина х, не принадлежащая С и смежная хотя бы с одной вершиной цикла С. Если длина цикла С равна 3, то вершина х не может быть смежна сразу со всеми тремя его вершинами. Следовательно, граф С содержит порожденный подграф Р%. Далее будем считать, что длина С не менее чем 4. Вершина х не может быть смежна ровно с одной вершиной цикла С, т.к. иначе образовался бы порожденный подграф К'з и граф С не был бы реберным. Рассмотрим два возможных случая:
1. Вершина х смежна ровно с двумя вершинами цикла С. Эти вершины обязательно должны быть смежными, иначе снова образуется порожденный подграф АДз. Таким образом, вершина х сменена с двумя смежными вершинами «1 и V2 Но тогда граф О содержит путь длины псус1е, порожденный вершиной х и всеми вершинами С, кроме щ.
2. Вершина х смежна с тремя вершинами цикла С. Понятно,
что эти вершины обязательно должны быть последовательными, иначе снова образуется порожденный подграф Афз. Будем считать, что («1, па) С Е(С1) и (нг, Дз) £ Е{0). Пусть а и Ь — такие вершины цикла С, что а ф г>2, Ъ ф V2 и (а,гц) £ Е(С), (Ь,уз) £ Е{С1). Тогда вершины ж, ы, г?2, г?з, а, 6 образуют порожденный подграф графа С, не являющийся реберным |23], независимо от того, совпадают ли вершины а и Ь. Поэтому и сам граф С не является реберным. Лемма доказана.
Теорема 1.10. Класс Т являет,ся РНСПОС-граничным, а класс О является ВНСПОС-граничным.
ДОКАЗАТЕЛЬСТВО. Понятно, что пары задач РНСПОС и PHП[Deg(2)cJ, ВНСПОС и BHП[Deg(2)cj в классе графов Deg(3) являются парами полиномиально эквивалентных задач. Очевидно, что для любого