WWW.DISSERS.RU

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

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

Pages:     | 1 || 3 |

В первом и втором разделах главы 1 излагаются используемые во всей работе понятия и обозначения, формулируется уточненное понятие граничного класса и описываются два известных класса графов, граничность которых была доказана для нескольких классических задач на графах5,6,7.

Напомним, что наследственным называется класс графов, замкнутый относительно удаления вершин. Известно, что любой такой класс X может быть задан множеством запрещенных порожденных подграфов F, при этом принята запись X = F ree(F). Минимальное по включению множество с данным свойством существует, единственно и обозначается через F orb(X). Если F orb(X) конечно, то X называется конечно определенным.

Пусть произвольная NP-полная задача на графах. Наследственный класс называется -простым, если задача для графов из этого класса полиномиально разрешима, и -сложным в противном случае. Наследственный класс графов X называется -предельным, если существует такая бесконечная последовательность X1 X2... -сложных классов графов, что X = Xi. Минимальный по включению i=-предельный класс называется -граничным.

Значение понятия граничного класса графов состоит в том, что произвольный конечно определенный класс является -сложным тогда и только тогда, когда он содержит некоторый -граничный класс5,6,7. В тех же работах в качестве граничных фигурировали два класса графов. Одним из них является класс T класс графов, каждая компонента связности которых является деревом с не более чем 3 листьями.

Иными словами, данный класс состоит из всевозможных графов, у которых каждая компонента связности либо простой путь, либо триод. Под триодом Ti,j,k понимается дерево, имеющее ровно одну вершину степени 3 и ровно три листа, отстоящих от вершины степени 3 на расстояниях i, j, k соответственно. Другой такой класс класс D, состоящий из всех графов, являющихся графами ребер графов из T.

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

Теорема 1.3. -предельный класс A является -граничным тогда и только тогда, когда для каждого G A существует такое конечное множество графов X F orb(A), что класс F ree(X {G}) является -простым.

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

Пусть Deg(3) класс графов, степень каждой из вершин которых не превосходит Bodlaender H. L. Dynamic programming on graphs with bounded treewidth // Automata, Languages and Programming (Tampere, 11–15 July 1988). Proc. in Lecture Notes in Computer Science. 1988. V. 317. P. 105–118.

3, TW(3, t) множество графов из Deg(3), древесная ширина которых не превосходит t, L(TW(3, t)) совокупность графов, являющихся графами ребер графов из TW(3, t).

Лемма 1.7. Если класс T является -предельным и для любого t задача полиномиально разрешима в классе TW(3, t) F ree({C3}), то класс T является -граничным. Если класс D является -предельным и для любого t задача полиномиально разрешима в классе L(TW(3, t)) Deg(3), то класс D является граничным.

Пятый и шестой разделы главы 1 посвящены выявлению новых случаев граничности классов T и D. Так, в пятом разделе рассматриваются некоторые частные случаи общей задачи о наибольшем подграфе. Наиболее интересными из них являются задачи о вершинно наибольшем X-подграфе (называемая далее ВНП[X]), о реберно наибольшем X-подграфе (называемая далее РНП[X]). Задача РНП[X] состоит в том, чтобы для заданных графа G и числа k определить, содержит ли этот граф подграф из класса X, число ребер которого не менее k. Задача ВНП[X] состоит в том, чтобы для заданных графа G и числа k определить, содержит ли этот граф порожденный подграф из класса X, число вершин которого не менее k.

Пусть Planar класс планарных графов, Bipartite класс двудольных графов, Perfect класс совершенных графов, Path класс простых путей, Cycle класс простых циклов, TO класс транзитивно ориентируемых графов.

Теорема 1.6. Класс T является РНП[Planar]-граничным, РНП[Bipartite]граничным, РНП[Perfect]-граничным и РНП[TO]-граничным.

Теорема 1.9. Класс T является граничным для задач ВНП[Planar], ВНП[Bipartite], ВНП[Perfect], а класс D является граничным для задач ВНП[Planar], ВНП[Perfect], ВНП[Path] и ВНП[Cycle].

В том же пятом разделе указывается континуальное семейство различных задач на графах, для каждой из которых T и D являются граничными одновременно. Каждая из этих задач задача о вершинно наибольшем порожденном X-подграфе, где X некоторое расширение класса планарных графов. В шестом разделе показывается (теорема 1.11), что класс T является граничным для задач о покрытии полными двудольными графами, о разбиении графа, о лесе с ограниченными компонентами, о независимом реберном доминирующем множестве, о непересекающихся путях, а класс D является граничным для задач о разбиении на клики и o разобщенном множестве.

Наконец, в седьмом разделе приводятся первые примеры задач на графах с граничными классами co(T) = {G : G T} и co(D) = {G : G D}. Именно доказывается, что класс co(T) граничный для задачи о наибольшей клике и для задачи об ахроматическом числе графа, а класс co(D) граничный для задачи о вершинной раскраске. Результаты главы 1 опубликованы в работах [2, 5, 9, 13].

В главе 2 вводится понятие относительного граничного класса и исследуется вопрос о полном описании множества граничных классов для задачи о независимом множестве (задачи НМ) относительно класса планарных графов.

Первый раздел начинается с формулировки некоторой гипотезы о структуре НМ-граничных классов графов, принадлежащей В. Е. Алексееву5. Именно, в этой работе было доказано, что класс T является граничным для задачи НМ и выдвинуто предположение об его единственности, как НМ-граничного. Там же показано, что доказательство этого предположения эквивалентно доказательству того факта, что для любого G T класс F ree({G}) НМ-простой. К настоящему времени это доказано лишь для нескольких случаев (наиболее важные из них, когда G = P411 и G = T1,1,212) и остается открытым сложностной статус задачи НМ в классах F ree({P5}) и F ree({T1,2,2}).

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

Пусть Y какой-нибудь -сложный класс. Наследственный класс графов X называется -граничным относительно класса Y, если существует такая последовательность X1 X2... -сложных подклассов класса Y, что Xi = X.

i=Минимальный по включению -предельный относительно Y класс называется граничным относительно Y классом.

Класс T является граничным относительно класса Planar и его единственность эквивалентна тому, что любого G T класс Planar F ree({G}) НМ-простой.

Во втором разделе показывается, что при любом фиксированном k задача НМ в классе Planar F ree({Pk}) полиномиально разрешима (следствие из леммы 2.1).

В третьем разделе двумя способами (как следствие из леммы 2.4 и в теореме 2.1) доказывается, что при любом фиксированном i класс Planar F ree({T1,1,i}) является НМ-простым.

Четвертый раздел содержит важный результат (лемма 2.10) о сведении задачи о независимом множестве в классе Planar F ree({Si}) к задаче НМ для графов из того же класса, степени вершин которых не превосходят 16i2 - 1 (звезда Si граф, получаемый подразбиением каждого ребра графа K1,i). На его основе доказана следующая Corneil D. G., Perl Y., Stewart L. K. A linear recognition algorithm for cographs // SIAM J. Comput. 1985. V. 14.

P. 926–934.

Алексеев В. Е. Полиномиальный алгоритм для нахождения наибольших независимых множеств в графах без вилок // Дискретный анализ и исследование операций. Серия 1. 1999. Т.6, №4. Стр. 3–19.

Теорема 2.2. При любом фиксированном k класс PlanarF ree({T1,2,k}) является НМ-простым.

Пятый раздел посвящен доказательству самого важного утверждения всей главы.

Здесь рассматриваются яблоки, где яблоко Ak граф, получаемый соединением ребром изолированной вершины и цикла Ck. Основным результатом второй главы является Теорема 2.3. Для любого фиксированного k 3 задача НМ в классе Planar F ree({Ak, Ak+1,...}) полиномиально разрешима.

Из теоремы 2.3 легко следует, что при любых фиксированных i, j класс Planar F ree({T1,i,j}) является НМ-простым (для этого достаточно положить k = i + j + 1 и заметить, что F ree({T1,i,j}) F ree({Ak, Ak+1,...})). Результаты главы 2 опубликованы в работах [1, 3, 4, 6, 15, 16].

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

Первый раздел посвящен, в основном, мотивации обращения к количественным вопросам. Это вызвано результатом (с неконструктивным доказательством) о существовании 5 граничных классов в задаче о вершинной 3-раскраске и гипотезой о существовании задачи на графах с бесконечным множеством таких классов7.

Второй раздел посвящен конструктивному доказательству указанного предположения.

Пусть B граф, получаемый добавлением одной вершины к графу P5 и всех ребер, соединяющих эту вершину с вершинами данного пути, а B граф, получаемый из графа 2K3 добавлением двух ребер, соединяющих пары вершин степени 2 из разных треугольников.

Обозначим через T граф, имеющий счетно-бесконечное количество компонент связности, каждая из которых является счетно-бесконечным триодом, т.е. графом, получаемым соединением одной вершины графа K4 с тремя другими простыми путями счетно-бесконечной длины. Граф D граф ребер графа T.

Операция замены ребра e = (a, b) некоторого графа графом G состоит в удалении этого ребра c последующим отождествлением вершины a с одной вершиной степени 2 графа G и вершины b с другой вершиной степени 2 графа G. Считаем, что граф G содержит автоморфизм, переводящий вершины степени 2 друг в друга, поэтому получившийся граф не зависит от того, какая именно вершина степени 2 графа G отождествляется с вершиной a.

Для произвольной бинарной последовательности (Bin()-последовательности) = {1, 2,...} обозначим через T граф, получаемый из T заменами некоторых его ребер. Для каждой компоненты T и для любого натурального i все три ребра, отстоящие от вершины степени 3 на расстоянии 2i - 1, заменяются графом K4 - e, если i = 0, или графом B, если i = 1. Через D обозначим граф, получаемый из D заменой каждого ребра, не принадлежащего треугольникам. Любая такая операция состоит в замене трех ребер каждой компоненты связности, отстоящих от соответствующих вершин треугольника на расстоянии i - 1, графом K4 - e, если i = 0, или графом B, если i = 1. Граф D результат применения к графу T определенной процедуры.

Она состоит в том, что к каждой его вершине x, окрестность которой порождает пустой граф из трех вершин y1, y2, y3, применяются следующие действия:

1. Вершина x заменяется на три попарно смежные вершины x1, x2 и x3.

2. Добавляются ребра (x1, y1), (x2, y2), (x3, y3).

Пусть T множество конечных графов, являющихся порожденными в графе T. Аналогично вводятся классы D и D. Основными результатами главы 3 являются следующие утверждения.

Теорема 3.1. Для любой Bin()-последовательности класс D является 3ВР-граничным.

Теорема 3.2. Для произвольной Bin()-последовательности класс T и класс D являются 3-РР-граничными.

В замечаниях ко второму разделу показывается, что найденные в обоих теоремах семейства граничных классов не совпадают со всем множеством таких классов ни для одной из рассматриваемых задач. Здесь также показывается, что для произвольного подмножества {5, 6, 7,...} совокупность граничных классов для задачи ВНП[EColor(3) F ree({Ks : s })] континуальна (EColor(3) множество графов, не являющихся реберно 3-раскрашиваемыми).

Третий раздел посвящен случаям полного описания множества относительных граничных классов. Здесь дается обзор известных таких указаний и добавляется несколько новых. Результаты главы 3 опубликованы в работах [7, 8, 10, 12, 13].

В главе 4 вводится понятие минимального сложного класса графов и решается вопрос о существовании данных классов для некоторых задач на графах.

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

Задан граф G и список LV (G) = {LV (G)(v1), LV (G)(v2),..., LV (G)(vn)} (V (G) = {v1, v2,..., vn}). Множество LV (G)(vi) конечное множество номеров разрешенных цветов для вершины vi, при этом номер цвета отождествляется с самим цветом. LV (G)n раскраской называется такое отображение c : V (G) LV (G)(vi), что выполняются i=следующие два условия:

(1). Для любой вершины x число c(x) принадлежит множеству LV (G)(x).

(2). Каждый путь, соединяющий две одноцветные вершины u и v, содержит такую вершину w, что c(w) > c(u).

Задача о вершинном списковом ранжировании (задача ВСР) для данного графа G и множества LV (G) состоит в том, чтобы определить, имеет ли этот граф LV (G)раскраску. Смысл множества LE(G), понятия LE(G)-раскраски и задачи о реберном списковом ранжировании (задачи РСР) определяются по аналогии.

Во втором разделе рассматривается задача распознавания принадлежности классу графов X (задача РП[X]). Его основным результатом является следующая Теорема 4.1. Если X наследственный класс графов, то любой РП[X]-сложный класс не является минимальным.

Pages:     | 1 || 3 |






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