WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

загрузка...
   Добро пожаловать!

Pages:     | 1 | 2 ||

В этом же разделе дается еще одна демонстрация отсутствия минимальных сложных элементов в решетке, образованной наследственными подклассами некоторого сложного класса. Именно, рассматривается задача о ленточной ширине графа (задача ЛШ, эквивалентная нахождению значения минимаксного критерия в задаче нумерации графа) и наследственное замыкание класса циклических 1-гусениц, т.е. графов, имеющих ровно один простой цикл, которому принадлежат все его нелистовые вершины. Показывается, что в любом ЛШ-сложном подклассе указанного замыкания существует меньший ЛШ-сложный класс.

В третьем разделе описывается строение определенных классов графов и доказывается ряд вспомогательных результатов о вычислительной сложности задач о списком ранжировании в этих классах и их собственных подклассах. Речь идет о следующих классах графов, являющихся наследственными замыканиями:

1. Comet множества деревьев, в которых существует вершина, инцидентная всем листьям, кроме одного.

2. Hammer графов ребер графов из Comet.

3. Star множества Si.

i=4. Sun графов ребер графов из Star.

Четвертый раздел начинается с установления связей между понятиями минимального сложного и граничного классов. Именно, доказывается, что -сложный граничный класс является минимальным сложным (теорема 4.3) и что в семействе конечно определенных классов эти понятия совпадают (теорема 4.4). Показывается, что Star и Sun конечно определенные классы графов (лемма 4.10), а также, что классы Comet и Hammer таким свойством не обладают (лемма 4.9). Одними из основных результатов всей диссертации являются Теорема 4.5. Класс Comet является как минимальным ВСР-сложным, так и минимальным РСР-сложным. Класс Hammer является минимальным ВСРсложным.

Теорема 4.6. Класс Star является минимальным ВСР-сложным и минимальным РСР-сложным, а класс Sun является минимальным ВСР-сложным.

Данные первые примеры минимальных сложных классов являются и граничными классами для соответствующих задач. Тем самым, конструктивно доказано предположение о существовании -сложных граничных классов7. Полученные в главе 4 результаты опубликованы в работах [11, 14].

ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ [1]. Алексеев В. Е., Малышев Д. С. Классы планарных графов с полиномиально разрешимой задачей о независимом множестве // Дискретный анализ и исследование операций. 2008. Том 15, №1. Стр. 3–10.

[2]. Алексеев В. Е., Малышев Д. С. Критерий граничности и его применения // Дискретный анализ и исследование операций. 2008. Том 15, №6. Стр. 3–11.

[3]. Малышев Д. С. Граничные классы для задачи о независимом множестве в классе планарных графов // Вестник Нижегородского университета им. Н. И.

Лобачевского. Раздел Математика. 2007. №2. Стр. 165–168.

[4]. Малышев Д. С. Граничные классы относительно класса планарных графов для задачи о независимом множестве // Материалы VI молодежной научной школы по дискретной математике и ее приложениям (Москва, 16–21 апреля 2007 г.), часть II.

Стр. 16–20.

[5]. Малышев Д. С. Граничные классы для задач на графах // Вестник Нижегородского университета им. Н. И. Лобачевского. Раздел Математическое моделирование и оптимальное управление. 2008. №6. Стр. 141–146.

[6]. Малышев Д. С. О единственности граничного класса для задачи о независимом множестве в классе планарных графов // Материалы XV международной конференции студентов, аспирантов и молодых ученых Ломоносов 2008 (Москва, 9–12 апреля г.), секция Вычислительная Математика и Кибернетика. Стр. 43–44.

[7]. Малышев Д. С. О бесконечности множества граничных классов для задачи о 3-раскраске // Тезисы докладов XV международной конференции Проблемы теоретической кибернетики (Казань, 2–7 июня 2008 г.). Стр. 79.

[8]. Малышев Д. С. О бесконечности множества граничных классов в задаче о реберной 3-раскраске // Дискретный анализ и исследование операций. 2009. Т.16, №1. Cтр. 37–43.

[9]. Малышев Д. С. Граничные классы графов для некоторых задач распознования // Дискретный анализ и исследование операций. 2009. Т.16, №2. Cтр. 85–94.

[10]. Малышев Д. С. Континуальные множества граничных классов графов для задач о раскраске // Дискретный анализ и исследование операций. 2009. Т.16, №5.

Стр. 41–51.

[11]. Малышев Д. С. О минимальных сложных классах графов // Дискретный анализ и исследование операций. 2009. Т.16, №6.

[12]. Малышев Д. С. О количестве граничных классов в задаче о 3-раскраске // Дискретная математика. 2009. Т. 21, №4.

[13]. Малышев Д. С. О недавних результатах в теории граничных классов графов // Материалы VIII международной конференции Дискретные модели в теории управляющих систем (Моск. обл., 6–9 апреля 2009 г.). Стр. 132–136.

[14]. Малышев Д. С. О минимальных сложных элементах решетки наследственных классов графов // Материалы VII молодежной научной школы по дискретной математике и ее приложениям (Москва, 18–23 мая 2009 г.).

[15]. Alekseev V. E., Lozin V. V., Malyshev D. S., Millanic M. The maximum independent set problem in planar graphs // Mathematical Foundations of Computer Science (Torun, 25–29 August 2008). Proc. in Lecture Notes in Computer Science. V. 5162.

P. 96–107.

[16]. Alekseev V. E., Malyshev D. S. Planar graph classes with the independent set problem solvable in polynomial time // (Russian) translation in Journal of Applied and Industrial Mathematics. 2009. V. 3, №1. P. 1–5.

Pages:     | 1 | 2 ||






© 2011 www.dissers.ru - «Бесплатная электронная библиотека»