Задачи преследования и поиска на графах тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

Список обозначений

Введение

1 Дискретные программы

1.1 Постановка задачи поиска.

1.2 Почти дискретные программы.

1.3 Дискретные программы.

1.4 Поиск на деревьях.

1.5 Пример. Остов тетраэдра.

2 Задача поиска с двумя преследователями

2.1 Обобщение одного результата H.H. Петрова.G

2.2 Связь задачи поиска с почти гамильтоновыми внешне-планарными цепями.

2.3 Модельные задачи

3 Дискретная задача поиска с одним преследователем

3.1 Постановка задачи.

3.2 Ширина ленты.

3.3 Монотонная задача поиска.

Неослабевающий интерес к разнообразным задачам преследования и поиска объясняется тем, что эти задачи возникают во многих областях человеческой деятельности. Ознакомиться с различными подходами к этим проблемам можно в работах [2, 3, 20, 21, 31, 33, 38, 40] и в литературе, указанной в этих работах. Достаточно подробный обзор литературы имеется в [20].

Среди многочисленных задач поиска и преследования важное место занимают задачи, связанные с поиском (преследованием) некоторого объекта, в дальнейшем именуемого убегающим, группой других объектов (возможно, состоящей из одного объекта), в дальнейшем именуемых преследователями, на различных множествах при различных правилах поведения игроков (преследователей и убегающего) и различных условиях успешного завершения поиска (преследования). Круг этих задач весьма широк. Сюда, например, относятся разнообразные дифференциальные игры (см. работы [2, 20, 21, 38, 40]), дискретные задачи поиска (преследования) и многие другие задачи.

Изучаемые в диссертации задачи поиска лежат на стыке нескольких разделов математики: теории конфликтного управления, теории графов и компьютерной математики (Computer Science). Поэтому не удивительно, что исследование этих задач привлекает многих ученых из различных областей науки.

Одна из классических задач конфликтного управления — проблема "Принцесса и Чудовище" рассматривалась Айзексом в монографии [2]. Чудовище хочет поймать Принцессу. Оба находятся в абсолютно темном помещении, формы которого им известны. Чудовище ловит принцессу, если ему удается приблизиться к ней на заданное расстояние. Платой в данной игре является время поимки. В качестве nepBofo шага в решении проблемы, Айзеке предложил рассмотреть случай, когда оба игрока движутся по окружности. Эта задача для случая, когда скорости игроков равны, была, решена М.И. Зеликиным в работе [18]. Некоторые дальнейшие результаты для графов были получены в работах [44, 81, 8С]. Задачи подобного типа на графах рассматривались JI.A. Петросяном и А.Ю. Гарнаевым в [31].

В отличие от игры "Принцесса и Чудовище" в задачах, изучаемых в диссертации, убегающий располагает полной информацией о всех действиях преследователей. Следовательно, преследователи должны успешно завершить поиск даже при самом "худшем" для них поведении убегающего. Общая теория таких задач практически отсутствует.

Такие задачи для случая поиска на двумерных множествах рассматривались Ф.Л. Черноусько в работах [39, 41]. Некоторые результаты для двумерных множеств имеются и в [31].

Как оказалось, в двумерном случае содержательные рез}'льтаты можно получить только для сравнительно простых множеств. Поэтому естественным является рассмотрение этих задач на одномерных множествах, в частности, на топологических графах.

Приступим к обзору литературы, имеющей непосредственное отношение к результатам диссертации. Авторами первых статей, давших толчок к появлению многочисленных публикаций, посвященных задачам поиска на графах, являются Т.Д. Парсонс [133] и H.H. Петров [23, 25].

Прежде чем приступить к описанию результатов H.H. Петрова и Т.Д. Парсонса, определим некоторые понятия, которые будут использоваться во введении и в самой диссертации.

Граф Г определяется множеством вершин VT, множеством ребер ET и отношением инцидентности, которое каждому ребру сопоставляет одну или две вершины, называемые его концами. Заметим, что определяемый таким образом граф может иметь петли (ребра, концами которых является одна вершина) и кратные ребра (различные ребра с одинаковыми вершинами). При этом мы будем, как правило, рассматривать только связные графы. При необходимости рассмотреть граф без петель и кратных ребер или несвязный граф это будет оговариваться отдельно. В диссертации рассматриваются только конечные графы.

Будем говорить, что Г — топологический граф (см. [19]), если вершины Г суть точки в R3, а ребра — непересекающиеся конечнозвенныс ломаные с концами в соответствующих вершинах.

Задача поиска с ограничением скорости. В начале 80-х годов H.H. Петров в работе [23] поставил следующую задачу поиска.

На связном топологическом графе Г находятся п преследователей Pi,., Рп и убегающий Е. Предполагается, что преследователи и убегающий обладают в R3 (граф вложен в R3) простыми движениями:

Pi) : x¡ = u¡, IIг/,-II < v, i e 1,71, (E) : y = u0, H'Uoü < v0, причем Г является для игроков фазовым ограничением. Для простоты считается, что допустимыми управлениями игроков являются кусочно-постоянные функции, заданные на произвольных промежутках [0,Г]. Таким образом, допустимыми траекториями будут кусочно аффинные вектор-функции со значениями в Г.

Убегающий Е считается пойманным преследователем P¿ в момент i 6 [0,Т], если х¡(i) = y(t). Совокупность траекторий преследователей, заданных на промежутке [О, Т], называется программой преследователей, заданной на промежутке [0,Т]. Программа п преследователей Ща^,., хп), заданная на [0, Т], называется выигрывающей, если для любой траектории убегающего у, заданной на [0,Т], существуют t 6 [0, Г] и i Е 1, п такие, что x¡(t) = y(t).

Был поставлен вопрос о нахождении наименьшего натурального числа п такого, что у п преследователей существует выигрывающая программа, заданная на некотором промежутке [0, Т]. Понятно, что эта величина зависит только от графа Г и отношения ¡i = будем обозначать ее через Г).

Назовем данную задачу поиска задачей с ограничением на скорости. Итак, целью в задаче с ограничением на скорости является нахождение минимального числа преследователей, которое может гарантировать поимку убегающего вне зависимости от выбора им своей траектории.

В работе [23] H.H. Петровым были получены некоторые оценки величины 5ДГ) в зависимости от Г и ß. Было показано, что если в графе Г имеется вершина степени > 3, то S^T) > 2 для всякого /i. > 0. Также было доказано, что на всяком топологическом графе двое преследователей обладают выигрывающей программой при достаточно малом положительном ¡i. В работе [34] этот рез.ультат был обобщен. Будем говорить, что граф Ti изоморфен графу Г-2, если существует биекция ip: ЕГi —► ЕГ2, сохраняющая смежность, кратности ребер и петли (ребра и, v Е ЕГi смежны тогда и только тогда, когда смежны ребра ip(u),<p(v) £ ЕГ%, ребра и, v 6 ET 1 являются кратными тогда и только тогда, когда кратны ребра ¡¿{и),<р(у) 6 ЕГ2, и ребро и 6 ЕГ\ является петлей тогда и только тогда, когда ребро <р(и) £ ЕГ2 — петля). Было показано, что для всякого топологического графа Г найдется такое ß > 0, что двое преследователей обладают выигрывающей программой на всяком топологическом графе изоморфном Г.

H.H. Петровым также было отмечено (см. [23]) любопытное свойство задачи поиска, аналог которого в вариационном исчислении называется эффектом Лаврентьева. А именно, "небольшим расширением" пространства допустимых управлений можно добиться уменьшения числа преследователей, достаточного для существования выигрывающей программы. Обозначим через Vc(t) е-окрестность точки t 6 [О, Т]. Определим U — класс функций и, заданных на промежутке [0,Т], |и| < и, для которых существует конечное число моментов ¿1,., tk таких, что для всякого б > 0 на интервалах t 6 [0,Т] \ (Ui=lV((ti)) функция u(t) кусочно-постоянна. При расширении класса допустимых управлений до U число преследователей может уменьшиться. В частности, было показано, что если допустимыми управлениями преследователей являются функции из U, то на всяком топологическом графе один преследователь может успешно осуществить поиск при малых /л > 0.

В ¡заботе [1] приведены некоторые оценки числа ц достаточного для осуществления поимки одним преследователем в классе таких управлений.

Исчерпывающее исследование поведения 5^(Г) для всех ^ допускают лишь некоторые графы, имеющие сравнительно простую структуру. Так, например, для графа Г гомеоморфного отрезку Sfl(Г) = 1 для всех ß 6 [0, оо). Для графа Г гомеоморфного окружности:

Г 1, если ¡л < 1, \ 2, если ¡л>1.

Некоторые модельные задачи рассматривались в [23, 25]. Например, для графа Ä', состоящего из всех ребер куба, была сформулиs,(T) рована следующая гипотеза:

5, если ß > 1, 4, если ,7 в 1), S,t(K)= 3, если € l2^^),

2, если/г€(0,ЬаШ),

1, если = 0.

Для графа Л*4, состоящего из ребер тетраэдра, предполагалось, что

14, если ¡1 > 1, 3, если // G 1), 2, если ^ (0,1], 1, если fi = 0.

Поисковое число. Случай, когда ц бесконечно велико, то есть скорости игроков могут быть произвольными, изучался H.H. Петровым в [25]. Наименьшее число преследователей, необходимое для успешного завершения поиска на графе Г в этом случае, будем обозначать через $(Г) и называть поисковым числом (search number) графа Г. Ясно, что поисковое число не зависит от длин ребер и является инвариантом, зависящим только от комбинаторной схемы графа.

Назовем эту задачу задачей о поисковом числе.

Впоследствии выяснилось, что ранее подобная задача рассматривалась Парсонсом в работах [133, 134]. Парсонс писал, что на подобные исследования его натолкнула работа [53], в которой обсуждалась следующая проблема. В некоторой пещере, представляемой системой туннелей, потерялся незадачливый исследователь, которого мы должны спасти. В нашем распоряжении имеется карта туннелей (граф), но число спасателей, отправляемых на поиск, ограничено. Требуется разработать план поиска, гарантирующий спасение исследователя. Задача решается просто (достаточно одного спасателя), если незадачливый исследователь стоит на месте. Но мы не можем быть уверены в том, что он стоит, и должны приложить все усилия, чтобы случайно с ним не разминуться.

В постановках задач Петрова и Парсонса имелись некоторые различия: Парсонс определял граф как одномерный CW-комплекс и предполагал траектории игроков непрерывными (в топологии графа) функциями. Но, как позднее было доказано П.А. Головачем в [4], эти две задачи эквивалентны.

При сравнении упомянутых задач поиска возникает естественный вопрос: при каких //. выполняется равенство 5ДГ) = «(Г)? Единственный известный ответ на этот вопрос принадлежит П.А. Головачу, доказавшему в [8], что если ¡.i > где I — длина (по евклидовой норме) кратчайшего ребра топологического графа Г, а L — сумма длин всех ребер Г, то 5М(Г) = а(Г). Для некоторых графов оценки П.А. Головача на // могут быть сильно улучшены. Например, если граф Г является деревом, то равенство £>ДГ) = s(T) выполняется для всякого // > 1 (см. [35]).

Независимо друг от друга, Парсонс в [133] и H.H. Петров в [25] показали, что для всякого дерева Т и целого числа к > 1 неравенство > к + 1 выполняется тогда и только тогда, когда в Т имеется вершина и, инцидентная по крайней мере трем ветвям с поисковыми числами > к (дерево Т1 является ветвью дерева Т, инцидентной вершине v, если степень вершины v в дереве Т" равна единице, и Т" есть максимальный подграф, удовлетворяющий этому свойству).

Как было упомянуто Парсонсом в [134] (доказательство этого утверждения приводится П.А. Головачем в [5]), задача о поисковом числе эквивалентна следующей дискретной задаче. В дискретной версии действия преследователей описываются последовательностью ходов. Каждым ходом преследователь может быть

• поставлен на вершину,

• удален с вершины,

• передвинут из вершины в вершину вдоль ребра.

Отметим, что в дискретном варианте преследователи могут покидать граф. Дискретная задача трактуется как задача очистки ребер графа от "диффузированного" убегающего (например, от газа или от пыли). Первоначально все ребра графа предполагаются загрязненными. Ребро е с концами {х,у} становится очищенным, если либо один из преследователей стоит в х, а второй идет по е из х в /у, либо все инцидентные х ребра, за исключением е, очищены, и преследователь идет по е из х в у. Очищенное ребро е может быть опять загрязнено в момент удаления или передвижения преследователя, если в этот момент существует не содержащий преследователей путь, соединяющий е с каким-то загрязненным ребром. Требуется найти минимальное число преследователей, необходимое для очистки всего графа.

С понятием очистки графа связана интересная трактовка задач поиска, приводимая Биенстоком в обзоре [50]. Рассмотрим поведение в сети компьютерного вируса. Получая информацию о наличии в сети вируса, мы не знаем масштабы заражения. Предполагая худшее, мы должны подозревать, что заражена вся сеть, а потому все узлы должны быть систематически проверены и очищены. Предположим, что у нас имеется всего несколько копий вакцинных программ, и невозможно, а может быть непрактично, изготовление большего числа копий. Тогда стратегия очистки должна разрабатываться с учетом ограниченного числа копий. С другой стороны, плохо разработанная стратегия может стать причиной повторного заражения узла. Таким образом, ставится задача разработки стратегии очистки, использующей наименьшее число копий вакцинных программ.

Дискретный вариант задачи о поисковом числе графа привлек внимание специалистов по вычислительной сложности из-за похожести этой задачи на изучаемые достаточно продолжительное время игры в камни (pebble games). Эти задачи имеют отношение к задачам рационального использования памяти ЭВМ. С различными применениями игр в камни можно ознакомиться в [72, 96, 112, 123, 158, 162]. Обычно игры в камни принадлежат классу PSPACE (см. [16] стр. 349, [131] стр. 487), но для поискового числа доказан более тонкий результат.

Следующий шаг в исследовании поискового числа графов был сделан ЛаПо в техническом отчете [109]. ЛаПо было доказано, что для изучения поискового числа достаточно ограничиться рассмотрением монотонных стратегий. Точнее, монотонная стратегия — это такая последовательность ходов игроков, что никакое из уже очищенных ребер графа не может загрязняться повторно. ЛаПо показала, что если п игроков могут очистить граф, то п игроков хватает и для существования монотонной стратегии, очищающей граф. Журнальная версия этой работы появилась лишь спустя десять лет в [110], и за это время было опубликовано более короткое и элегантное доказательство теоремы ЛаПо [51, 52]. Из теоремы ЛаПо непосредственно вытекает, что задача о поисковом числе принадлежит классу NP.

В работе [117] коллективом авторов, среди которых такие видные специалисты по вопросам сложности как Гэри, Джонсон, Папади

Нвсдсп iir митриу, было показано, что для произвольного графа задача вычисления ого поискового числа является NP-трудной. Таким образом, соответствующая задача распознавания: УСЛОВИЕ: Заданы граф Г и целое число к. ВОПРОС: Верно ли, что «(Г) < fc? является NP-полной.

Несмотря на то, что в общем случае задача нахождения поискового числа NP-трудна, для некоторых графов найдены полиномиальные алгоритмы. Используя хараитеризацию Парсонса-Петрова для поискового числа деревьев, Мегиддо et al. построили в [117] полиномиальный алгоритм вычисления поискового числа деревьев. Полиномиальные алгоритмы для решеток особого вида обсуждаются в [168].

В работе [117] охарактеризованы графы с поисковым числом равным 1, 2, 3. Аналогичные результаты были получены в [27].

Линейные укладки. Связь задачи о поисковом числе с проблемой, на первый взгляд не имеющей ничего общего с поиском, обнаружили Македон и Садбороу [116]. Понятие ширины разреза (cutwidth) первоначально появилось в теории сверхбольших интегральных схем (СБИС) и связано с проектированием линейных укладок СБИС. Формально линейной укладкой (linear layout) графа Г называется биекдия

L:{l,.,n} VT.

Обозначим через w(L,i), г Е 1,п, число ребер {и, и} графа Г, для которых L~l(u) < i < L~l(v). Другими словами, если вершины Г "уложить" на прямой в порядке, задаваемом L, то w(L,i) обозначает число ребер, пересекающих "пространство" между г и г + 1. Пусть w(L) = max{w;(L, г): г G 1, тг}, тогда ширина разреза графа Г, обозначаемая сш(Г), определяется как минимум w(L), взятый по всевозможным линейным укладкам графа Г. Более подробную информацию о ширине разреза графа можно найти в работах [70, 73, 107, 120, 122]. Известно, что эта задача NP-трудна [16], но для деревьев найден полиномиальный алгоритм [174].

Македон и Садбороу показали, что для всякого графа Г выполнены неравенства я(Г) < сги(Г) < • (*(Г) - 1) + 1, здесь за Д(Г) обозначена максимальная степень вершины графа Г. В частности, для графов с максимальной степенью вершины, не превосходящей трех, поисковое число совпадает с шириной разреза. Данный результат позволяет уточнить сложность задачи о поисковом числе. В работе1 [115] показано, что задача нахождения ширины разреза остается NP-трудной для планарных графов с вершинами, имеющими степени, не превосходящие трех, а потому аналогичный факт верен и для поискового числа. Некоторые интересные оценки ширины разреза графа, а соответственно и его поискового числа, полученные при помощи собственных чисел матриц Лапласа, приведены в работах [93, 94, 124].

Связь задачи поиска с еще одним важным инвариантом графов была установлена Македоном, Садбороу и Пападимитриу в работе [114]. Данный инвариант является обобщением ширины ленты графа. Ширина ленты графа Г, соответствующая линейной укладке L, обозначаемая через b(T,L), определяется как max{|L-1 (u) - L~l(v)\: {u, v) G £Т}, а шириной ленты (bandwidth1) графа Г, обозначаемой через Ъ{Г), называется тт{Ь(Г, L): L линейная укладка Г}.

Первоначально задача о ширине ленты возникла в теории матриц. Пусть А = {aij^j-i — некоторая разряженная матрица, то есть матрица, большинство элементов которой является нулями. Ставится следующая задача: с помощью одновременных перестановок столбцов и строк (если меняются местами г-й и j-й столбцы, то меняются местами и г-я и j-я строки) привести матрицу А к такому виду, чтобы все ненулевые элементы находились на диагоналях матрицы, ближайших к главной. Таким образом, минимизируется ширина ленты матрицы. Минимизировать ширину ленты матрицы часто бывает важно при решении вычислительных задач.

Легко видеть, что если Г — граф, множество вершин которого {1,., п}, и вершины г и j смежны тогда и только тогда, когда либо (iij ф 0, либо (iji ф 0, г, j 6 1, п, то задача минимизации ширины ленты графа эквивалентна задаче, сформулированной в предыдущем абзаце.

Эта задача возникает и в электронике. Здесь бывает важно расположить несколько связанных между собой узлов в ряд так, чтобы длина связей между узлами была минимальной. Ширине ленты иногда переводится как ширина связи или просто ширина

Be< t)t u ш

13 посвящено огромное количество работ. Достаточно полный обзор литературы приведен в [71, 74].

Македон, Садбороу и Пападимитриу рассматривали топологическую ширину ленты (topological bandwidth) графа. Граф Г' называется гомеоморфным образом графа Г, если изоморфный графу Г' граф может быть получен из графа Г помещением на ребра Г некоторого числа вершин степени два. Топологическая ширина ленты графа Г определяется как ЩГ) — шш{Ь(Г'): Г' гомеоморфный образ Г}. В этой работе был установлен ряд соотношений между поисковым числом и топологической шириной ленты. Так, например, оказалось, что если Г — граф степени три, то s(T) — 1 < tb(Г) < s(T).

Связь поискового числа с другим инвариантом — величиной вершинного разделения (vertex separation number) — была установлена в [77] Э л лисом, Садбороу и Турнероы (работа [78] является пересмотренным и дополненным вариантом [77]). Сепаратором (разделителем) графа (см. [17], стр. 145) называется множество вершин (в случае вершинного сепаратора) или множество ребер (в случае реберного), удаление которых увеличивает число компонент связности графа. Задачи о разделении графа интересуют исследователей как с чисто теоретической (см. например теорему Менгера в [37] на стр. 64), так и с практической точек зрения. В частности, малые сепараторы, разделяющие граф на примерно равные компоненты, были использованы в [111] для описания хороших укладок СБИС и для описания некоторых алгоритмов типа «разделяй и властвуй»[113].

Ленгауер в [112] рассмотрел «динамический» вариант сепаратора, связанный с линейными укладками графов. Определим для произвольного подмножества вершин U графа Г, |УГ| = 7?,, множество dU = {и: и Е U и существует вершина v € V\U, смежная it}. Пусть L — линейная укладка графа Г. Обозначим через 5г-(Г, L) множество {г;: v Е V, L~l{v) < г} при всех г € 1, п. Величиной вершинного разделения графа Г называется величина i?s(r) = min£ maxiej^zi |55г(Г, L)|, где минимум берется по всевозможным нумерациям вершин графа. Эллис, Садбороу и Турнер доказали, что для всякого графа Г vs(T) < s(T) < vs(T) + 2.

Вершинно-поисковое число. В работе [102] Кироузис и Панадимитриу рассмотрели новую версию дискретной задачи о поисковом числе. В отличие от задачи о поисковом числе, называемой ими задачей реберного поиска (edge-searching), они назвали свою задачу задачей вершинного поиска (node-searching), а минимальное число преследователей, необходимое для успешного завершения поиска нертинпо-поисковым числом (node-search number). В задаче вершинного поиска на каждом шаге преследователи могут быть поставлены и удалены с вершин графа, но не могут быть передвинуты вдоль ребра. Загрязненное ребро становится очищенным, если обе его вершины заняты преследователями (убегающий, находящийся на ребре с, считается пойманным, когда обе вершины ребра е содержат преследователей). Если обозначить за п«(Г) вершинно-поисковое число графа Г, то нетрудно убедиться в том, что |ns(r) — s(T)| < 1. Далее, обозначая за Н граф, получаемый из графа Г заменой каждого ребра путем из трех ребер (помещением на каждое ребро двух вершин степени два), а за L — граф, получаемый из графа Г заменой каждого ребра тремя параллельными ребрами, Кироузис и Пападимитриу показали, что пя(Г) = s(H) и я(Г) = ns(L). Учитывая эти факты, нетрудно убедиться, что результат ЛаПо влечет существование монотонной стратегии и для задачи вершинного поиска.

В этой же работе была установлена интересная связь задачи поиска с играми в камни. Эти игры являются играми с одним участником, и действие их происходит на ориентированном графе без циклов. Кироузис и Пападимитриу рассмотрели два варианта игры в камни: игра в черные (black pebble game) и игра в черные и белые (black and white pebble game) камни.

В игре в черные камни игрок может:

1. Поставить камень на вершину v, если на началах всех дуг, входящих в г;, стоят камни. (Если в вершину не входит ни одной дуги, то камень на нее можно поставить всегда.)

2. Снять камень с вершины.

В черных и белых камнях игрок может:

1. Поставить камень на вершину г>, если на началах всех дуг, входящих в v, стоят камни (безразлично белые или черные).

2. Поставить на вершину белый камень.

3. Снять черный камень с вершины.

4. Поменять цвет камня, стоящего в вершине и, с белого на черный,

Внсдспис если на началах всех дуг входящих в v, стоят камни (безразлично белые или черные).

Первоначально на вершинах графа нет камней. Игра заканчивается, когда все вершины графа окажутся пройдены игроком (на каждую из вершин на некотором ходе игрок ставил камень). Необходим,остью в черных камнях (black pebble demand) графа Г и, соответственно, необходимостью в черных и белых камнях (black and white pebble demands) называется минимум по всевозможным стратегиям максимального числа камней, находящихся одновременно на графе в соответствующей игре. Можно рассматривать монотонные версии этих игр, когда камень на вершину можно ставить только по одному разу.

Для неориентированного графа Г множеством ориентации Г называется множество всех ориентированных графов без циклов, получаемых из Г заданием ориентаций для ребер Г.

Кироузис и Пападимитриу [102] доказали следующее утверждение:

Для всякого неориентированного графа Г следующие параметры равны:

1. Минимальная необходимость в черных камнях в монотонной игре, где минимум ищется на множестве ориентаций графа Г.

2. Минимальная необходимость в черных и белых камнях в монотонной игре, где минимум ищется на множестве ориентаций графа Г.

3. Вершинно-поисковое число графаТ.

В этой же работе было доказано еще одно важное утверждение: Для всякого графа его вершинно-поисковое число совпадает с величиной вершинного разделения плюс один.

Линейные алгоритмы нахождения вершинно-поискового числа деревьев представлены в [77] и [159, 160].

Графы пересечений. Графом пересечений [37] называется граф, каждая вершина которого ассоциируется с одним из объектов некоторого пространства, причем вершины графа смежны тогда и только тогда, когда соответствующие объекты пересекаются.

Важный класс графов пересечений составляют реберные графы. Для произвольного графа Г реберный граф L(T) определяется следующими двумя условиями:

1. VL(T) = ЕГ,

2. Вершины e\ и e2 смежны в ¿(Г) тогда и только тогда, когда ребра е\ и e-j смежны в Г.

П.А. Головачем в работе [11] доказано, что для графа с вершинами степени три, ширина разреза (поисковое число) совпадает с величиной вершинного разделения его реберного графа (вершинно-поиско-вым числом +1).

Другим классом графов пересечений являются графы интервалов. Графом интервалов (см. [37] стр. 35) называется граф, множество вершин которого совпадает с некоторым набором интервалов вещественной прямой, и две вершины графа смежны тогда и только тогда, когда соответс твующие интервалы пересекаются. Клыковым числом (плотностью) графа Г [19] называется число вершин наибольшего полного подграфа (наибольшей клики) в Г, иными словами, наибольшее количество попарно смежных вершин. Важной особенностью графов интервалов является то, что их кликовое число равно максимальному числу интервалов, имеющих общую точку. Кироузис и Пападимитхшу в [101] обнаружили важную связь между задачей вершинного поиска и графами интервалов.

Кироузис и Пападимитриу определили в [101] интервальную ширину (interval-width) произвольного графа Г, обозначаемую через м/;(Г), как минимум кликового числа графа Л", где минимум берется по всем графам интервалов Н, содержащими качестве подграфа граф Г. Выл доказан следующий результат: для всякого графа Г его интервальная ширина Г совпадает с гав(Г).

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

Еще одним важным классом графов пересечений являются хор-дальные (или триангулированные) графы. Классическое определение таково (см. [17]): граф называется хордальным, если ни один из его порожденных подграфов не является простым циклом длины > 4. Другими словами, всякий простой цикл длины > 4 содержит хорду. Известен следующий факт [88]: граф Г является хордальным тогда и только тогда, когда существует дерево Т, такое, что каждой вершине v Е Г соответствует некоторое поддерево Tv в графе Т\ причем вершины u,v Е VT смежны тогда и только тогда, когда VTv П VTU ф 0. Связь хордальных графов с одним из вариантов задачи поиска будет отмечена чуть позже.

Путевая и древесная ширина графа. Изложим кратко основные результаты теории миноров. Граф Н = (W,F) является минором графа G = {V,E), если граф Н может быть получен из G последовательностью удалений вершин, ребер и стягиваний ребер (в произвольном порядке), где стягиванием ребра называется операция замены двух смежных вершин и и v на вершину, смежную вершинам, которые были смежными для и и v.

Робертсон и Сеймур получили следующие глубокие результаты в серии работ [136]-[157].

Первое из утверждений было ранее известно как гипотеза Вагнера [172].

Теорема 1 [Робертсон и Сеймур] Для всякого замкнутого относительно операции взятия минора класса графов G, существует конечное множество графов, ob(G), называемое запрещенным для G множеством (obstruction set), такое, что граф G принадлежит G тогда и только тогда, когда ни один из графов Н Е ob(G) не является минором G.

Например, запрещенным множеством для планарных графов являются графы A"s и А'з^.

Запрещенное множество для деревьев с заданным поисковым числом было найдено независимо Парсонсом [133] и H.H. Петровым [24]( запрещенные графы для деревьев с поисковым числом < к - 1 H.H. Петров назвал fc-минимальными деревьями).

Описание Ä-минимальных деревьев в задаче вершинного поиска и, соответственно, характеризация деревьев с заданным вершинно-поисковым числом, было дано Головачем П.А. [10], Эллисом et al. [77] (в терминах вершинного разделения), Шеффлер [159] (для интервальной ширины) и в работах [160, 169] (в терминах путевой ширины).

Задачи перечисления минимальных деревьев с заданными поисковыми и вершинно-поисковыми числами решаются Головачем в работах [9, 10].

Теорема 2 [Робертсон и Сеймур] Для всякого графа Н существует полиномиальный (по числу вершин) алгоритм, проверяющий для данного графа G, является ли Н минором G.

Из первой и второй теорем Робертсона-Сеймура вытекает, что всякий замкнутый относительно взя тия минора класс графов распознаваем за полиномиальное время (достаточно проверить на содержание минора запрещенное множество). С другими результатами теории Робертсона-Сеймура и их применением можно ознакомится в обзорах [58, 140]. Мы же остановимся на результатах этой теории, имеющих непосредственное отношение к задачам поиска. Два понятия играют особую роль в этой теории — путевая ширина и древесная ширина (pathwidth и treewidth) графа. Первое понятие связано с содержанием в качестве минора леса (говоря неформально, чем больше путевая ширина графа, тем больше лес, содержащийся в качестве минора в данном графе). Древесная ширина, в свою очередь, связана с содержанием в качестве минора планарно-го графа. Оказалось, что эти параметры имеют прямое отношение к задачам поиска.

Путевой декомпозицией (path decomposition2) графа Г, обозначаемой через (Хг-,/), называются множества Xf- С VT, г£/ = {1,.,г}, удовлетворяющие свойствам:

Pi) U€IXi = vr.

Р2) Для каждого ребра (и, v) Е ЕГ найдется номер i (Е / такой, что u, v 6 X,.

РЗ) Для всех г, j, k G /, г < j < к, XГ,- П X* С Xj.

Шириной путевой декомпозиции (X,-,J) графа Г называется ш(Г, (Xi, /)) = ma XjG; |Xf-| —1, а путевая ширина граф а Г определяется следующим образом: pw(T) = min{</;(r, (X,;, I)): (X/, I) - путевая декомпозиция графа Г}.

Известно, (см. [95]), что граф Г является графом интервалов тогда и только тогда, когда существует его путевая декомпозиция (А',;, I) такая, что каждое из множеств Xг 6 I, является кликой в графе Г. Учитывая последнее, нетрудно убедиться, что путевая ширина графа равняется интервальной ширине графа +1.

Суммируя результаты о поисковом числе, вершинно-поисковом числе, величине вершинного разделения, путевой ширине, интер

2Иногда переводится как цепная композиция lift( ()( и иг

И) вальной ширине получаем, что для всякого графа Г выполнены равенства:

•ч(Г) - 1 < /¿«(Г) = ГА-(Г) - 1 = /'ir; Г) = ¡пи{Г) - 1 < «(Г) + 1.

Прямое доказательство равенства величины вершинного разделения и путевой ширины было дано Киннерсли в [99].

Интересный результат о структуре графов с заданной путевой шириной (величиной вершинного разделения, интервальной шириной, поисковыми числами) был получен работе [52]. Робертсон, Сеймур и Биенсток доказали, что для всякого леса F каждый граф с путевой шириной \VF\ — 1 имеет минор изоморфный F.

Древесная ширина графа является одним из фундаментальных понятий теории Робертсона-Сеймура. Дрсвеснал декомпозиции (tree decomposition) графа Г состоит из дерева Т, VT = I, и множеств (Xj.:i Е I), являющихся подмножествами VT и удовлетворяющих следующим свойствам:

TI) [JierXi =

Т2) Для каждого ребра (и, v) G ЕТ найдется вершина i дерева Т такая, что и, v £ X¿.

ТЗ) Для всех вершин г, j, к дерева Г, если j лежит на пути с концами г и к, то X¡ П Хк С Xj.

Шириной древесной декомпозиции графа Г является тах,-€/ |Xt| — 1, а древесная ширина графа Г есть минимальная ширина древесной декомпозиции, где минимум берется по всевозможным древесным декомпозициям.

Древесная ширина графа является предметом активного изучения большого числа ученых. Описания всех результатов, касающихся древесной ширины, выходит за рамки данного введения. Обзоры с обширным списком литературы по этой тематике написаны Бодлаендером (см. [58] и [62]). Некоторые результаты можно также найти в работах [42, 103, 104, 105, 106, 57, 65, 56, 60, 61, 66, 67, 63, 173]. Отметим лишь одну из основных причин столь активного интереса. Оказывается, многие NP-трудные задачи такие, как Независимое множество, Гамильтонов цикл, Дерево Штейнера и даже некоторые PSPACE-полные задачи, разрешимы за полиномиальное, а часто и за линейное время на графах с ограниченной древесной шириной [91].

Выяснилось, что древесная ширина связана с хордальными графами так же, как путевая ширина связана с графами интервалов. Робертсон и Сеймур в [142] доказали, что древесная ширина графа Г минус один равняется минимуму кликового числа графа Н, где минимум берется по всем хордальным графам Н, содержащим в качестве подграфа граф Г.

Теоретико-игровая интерпретация древесной ширины графа была представлена в [163] Томасом и Сеймуром. Они рассмотрели дискретную игру поиска очень похожую на задачу о вершинно-поисковом числе. В задаче поиска Томаса-Сеймура преследователи видят убегающего, передвигающегося сколь угодно быстро. Убегающий может перейти из вершины в вершину графа, если существует соединяющий эти вершины путь, в вершинах которого нет преследователей. Каждый из преследователей находится либо в вершине, либо на вертолете. Целью игрока, контролирующего действия преследователей, является посадка вертолета на вершину, в которой находится убегающий. Таким образом, отличие задачи Томаса-Сеймура от задачи Кироузиса-Пападимитриу заключается лишь в том, что на каждом ходу преследователи информируются о местоположении убегающего.

Выяснилось, что минимальное число преследователей, необходимое для успешного завершения поиска на графе, совпадает с древесной шириной г]зафа минус один. Учитывая, что вершинно-поисковое число графа равняется путевой ширине без единицы, мы получаем единый теоретико-игровой подход к древесной и путевой ширине графа. Задачи поиска Томаса-Сеймура и Кироузиса-Пападимитриу естественно трактовать как варианты одной задачи с одинаковыми законами движения преследователей и убегающего, и отличие этих вариантов заключается лишь в степени информированности преследователей.

Интересным является вопрос, для каких графов информированность преследователей не дает им преимущества при поимки убегающего, или другими словами, когда путевая ширина графа равняется его древесной ширине? Этот вопрос изучался в работах [67, 66, 132].

Другой теоретико-игровой подход к описанию путевой и древесной ширины графа предложен Дендрисом, Кироузисом и Тилико-сом в [76]. Они рассмотрели модификацию задачи о вершиннопоисковом числе, названную ими задачей поиска инерционного убегающего. В этой задаче убегающий может начать двигаться только в том случае, когда в вершину, в которой он находится, становится преследователь. В зависимости от скорости убегающего (скорость убегающего интерпретируется как число ребер, проходимых убегающим за один ход) возникают различные задачи. В этой работе было показано, что если убегающий обладает неограниченной скоростью, то наименьшее число преследователей, необходимое для успешного завершения поиска на графе, равно древесной ширине графа —1. Если же скорость убегающего равна единице, то число преследователей совпадает с другим параметром, называемым шириной (width) графа.

Описание ширины ленты графа и путевой ширины щт помощи «однотипных» задач поиска содержится и в третьей главе настоящей диссертации.

Применения, С задачей о путевой ширине графа (а, следовательно, и с остальными упоминавшимися задачами) связано еще несколько проблем. Первая из них — возникшая в теории СБИС задача о матричной укладке переключателей (gate matrix layout). Задача формулируется для матрицы переключателей-соединителей (net-gate matrix) М = столбцы которой представляют переключатели ., Gn, а строки — соединители N\,., Nm. Соединитель Ni соединяет все переключатели Gj, для которых выполняется равенство rriij = 1. Требуется найти соединение переключателей, минимизирующее число соединителей. Подробно эта задача и ее различные практические применения обсуждаются в работах [100, 125], мы же ограничимся формальным описанием задачи.

Для булевой матрицы М спрашивается, могут ли столбцы М быть переставлены таким образом, что при замене в каждой строке всех нулей, стоящих между первой и последней единицей, на единицы, сумма элементов каждого столбца не превосходила бы заданного числа к. Если ограничиться матрицами, в каждой колонке которых стоит по две единицы, то мы получаем матрицу инциден-ций графа, и аналогичная задача формулируется для графов (перестановка столбцов матрицы инциденций соответствует перестановке ребер графа). Стоимостью перестановки называется максимальная из сумм элементов столбцов получаемой матрицы, а стоимостью матричной укладки переключателей называется минимальная из стоимостей перестановок. Лангстоы и Феллоус показали [80], что стоимость матричной укладки переключателей графа равняется его путевой ширине.

Корнай и Туза в [108] отметили, что в теории обработки естественных языков (natural language processing) графы зависимости предложений, кодирующие основные синтаксические отношения между словами, имеет путевую ширину не больше шести. Оказывается, путевая ширина близка к узости (narrowness) этих графов.

Задачи, связанные с нахождением определенных путевых декомпозиций, возникают и в биологии. Для картирования человеческого генома биологи обращаются к теории графов, в частности, графы интервалов (см. [22]) используются в качестве моделей перекрытий мутационных искажений. NP-полная комбинаторная задача Ин-тервализация Раскрашиваемых Графов (Internalizing Colored Graph) рассматривалась в [79] как приближенная модель для нахождения карт ДНК. Проблема заключается в следующем: для данного к-раскрашиваемого графа Г определить, содержится ли Г в качестве подграфа в некотором А>раскрашиваемом графе интервалов. Можно показать, что это эквивалентно нахождению путевой декомпозиции (Х,;,/), ширина которой не больше fc, и для всякого г 6 если щ v G Агг, и ф v, то и и v окрашены в разные цвета.

Различные обобщения задачи о поисковом числе. С момента выхода работ Н.Н. Петрова и Парсонса было рассмотрено несколько различных обобщений и вариантов задач поиска. Перейдем к обзору литературы по этим вопросам.

В работах [28, 32] задача о поисковом числе естественно обобщается на множества с более сложной структурой. Пусть множество М, на котором ставится задача поиска, снабжено структурой топологического пространства, d — некоторая метрика на нем (вообще говоря, никак не связанная с этой структурой), е — неотрицательное число, характеризующее "радиус захвата". Путь <р на М, то есть непрерывное отображение [0,1] М, интерпретируется как "траектория" одного из преследователей. Совокупность путей {у?,-, г — 1,. ,п} называется выигрывающей программой для группы п преследователей, если для любого пути (р ("траектории убегающего") найдется такой момент т 6 [0,1] и номер i G 1, и, что d{<pi{T),(p{r)) < £.

Предполагалось, что М является замкнутым полигонально связным подмножеством евклидова пространства R" с топологией, индуцированной из Rn, а траектории преследователей и убегающего суть кусочно непрерывные функции времени со значениями в М.

Ставится вопрос об определении наименьшей численности группы преследователей, имеющей выигрывающую программу. Отметим, что как задача о поисковом числе, так и большинство перечисляемых далее задач поиска вписываются в данную схему.

Введем на M следующую метрику (Iq. Пусть £ и 7] — две различные точки M и C(£,rj) — множество всех ломаных, лежащих в M и соединяющих точки £ и //. Для каждой ломаной /, не вырождающейся в точку, через g(l) обозначим число ее звеньев. Положим doit ri) = mm{g(l) : 1еЩ,т})}.

Рассмотрим теперь поставленную выше задачу при е = 1. Тогда условие с1ъ(ф1{т),(р(т)) < 1 означает, что отрезок с концами целиком лежит в М, то есть в момент т преследователь с номером i "видит" убегающего. Такие задачи называются иногда задачами "увидел — поймал".

Обозначим через а(М) наименьшую численность группы преследователей, обладающих выигрывающей программой в поставленной выше задаче поиска. Определить величину а(М) можно лишь в исключительных случаях. Некоторые достаточные условия равенства а(М) = 1 получены Сузуки и Ямашито в [167].

В работе [28] получен следующий результат: если в множестве M существует "равносторонний" треугольник, сторона которого (в метрике do) не меньше 6, то а(М) > 2. Для некоторых классов множеств это достаточное условие является также и необходимым.

Некоторые модификации задачи поиска типа "увидел — поймал" в случае, когда M является решеткой, рассматриваются в [75, 164, 165, 166]. Сугихара и Сузуки аргументировали рассмотрение таких задач связью с задачами о координации движений роботов. Координацией движений называется задача разработки плана для перевода некоторого числа роботов из начальной позиции в конечную, избегая при этом столкновения. Немного отличной от классической задачи координирования движения является задача координации движений роботов, в которой команда роботов должна перехватить движущуюся цель, например, робота не из команды. Сугихара и Сузуки рассмотрели два варианта задачи поиска. В первом варианте требовалось только обнаружить убегающего, причем преследователь обнаруживал убегающего, если находился с ним на одном отрезке, целиком принадлежащем решетке. Таким образом, первый вариант является типичным представителем класса задач "увидел поймал11. Во втором варианте, преследователи должны догнать убегающего, но предполагается, что преследователи могут видеть последнего, только если находятся с ним на одном отрезке решетки.

Задачей, имеющей "близкое отношение" к задаче о поисковом числе и задачам "увидел — поймал", является задача ^-поиска на графах, рассмотренная в [7, 8]. Эта задача отличается от задачи о поисковом числе только условием поимки убегающего. Убегающий считается пойманным, если он сблизится с одним из преследователей на расстояние, не превосходящее некоторого неотрицательного числа е во внутренней метрике графа.

Еще одно обобщение задачи о поисковом числе, называемое задачей ¿-поиска, рассматривалось в [14, 32]. Эта задача отличается от задачи о поисковом числе только условием поимки убегающего, которое формулируется аналогично условию поимки в задаче ¿-поиска. Отличие состоит в том, что используется другая метрика. Пусть Г — топологический гхэаф. Введем на нем целочисленную метрику с1. Если х,у — точки графа Г, то с/(х,у) = 0 при х = у, а если х ф у, то (1{х, у) равняется числу ребер кратчайшего (по числу ребер) пути в графе Г, на котором лежат х и у. Убегающий считается пойманным, если он сблизится с одним из преследователей на расстояние, не превосходящее некоторого неотрицательного целого числа к (в метрике й). Минимальное число преследователей, достаточное для успешного завершения поиска в этой задаче, называется ¿-поисковым числом. А;-поисковое число графа Г обозначается через 8к{0). Очевидно, что 0-поисковое число совпадает с поисковым числом. В работе [26] вычислены ¿-поисковые числа для графов всех правильных многогранников.

Нетрудно видеть, что ¿-поисковое число графа является комбинаторным инвариантом. В работе [14] доказывается, что для всякого натурального к задача вычисления ¿-поискового числа является КР-трудной. В этой же работе вычислены все ¿-поисковые числа для всех графов правильных многогранников и графов интервалов.

Задача перечисления деревьев, являющихся запрещенными для деревьев с заданным ¿-поисковым числом (минимальных деревьев),

В(1С()(и иг

25 решается б работе [32]. В --этой же работе доказан следующий результат. Оказывается, наименьшее число преследователей, необходимое для осуществления А>поимки на любом дереве, имеющем не более п ребер, равно числу цифр в троичной записи целой части числа ?±§£.

Задача ¿-поиска при положительных значениях к наиболее полно исследована при к = 1 (см., в частности, [29, 30]). Нетрудно видеть, что в этом случае мы имеем дело с задачей поиска типа "увидел — поймал". Преследователь, находящийся в вершине, "просматривает" инцидентные ей ребра и смежные вершины, а преследователь, находящийся на ребре, — само ребро и инцидентные ему вершины.

Обобщение задачи о вершинно-поисковом числе — игры подслушивания, В работе [85] обсуждается следующий подход к задачам сохранения секретности информации, передаваемой по электронным сетям с мобильными подслушивающими устройствами ("жучками"). В качестве модели рассматривается игра между Сетью и Противником. Каждый узел сети (вершина графа) является процессором, который делает вычисления, хранит и стирает информацию, и посылает сообщения в соседние узлы. Несколько подслушивающих жучков перемещаются по узлам сети, считывая содержание сообщений и хранящуюся информацию. Протокол работы сети известен обоим игрокам.'

Первый ход делает Противник, располагая жучков в некоторых вершинах. Сеть делает ход, выполняя раунд своих протоколов, после чего Противник отвечает, передвигая подслушивающие устройства. Целью Противника является сбор разбросанной по сети информации.

На протяжении раунда каждый узел Сети выполняет следующий протокол:

1. Получает сообщения из соседних вершин (за исключением первого раунда).

2. Определяет, используя некоторый вероятностный источник, кому из соседей будет послана информация.

3- Вычисляет, какие сообщения будут посланы.

4. Изменяет состояние памяти (часть информации сохраняется, часть стирается).

5. Посылает сообщения соседним вершинам (за исключением последнего раунда).

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

В ответ на раунд Сети Противник делает следующее (после пятого шага раз'нда и перед первым шагом следующего раунда):

1. Координирует действия жучков в соответствии с налагаемыми на движения ограничениями.

2. С началом нового раунда продолжает прослушивание сети.

Налагая на движения жучков различные ограничения, авторы р>аботы получают разнообразные игры подслушивания и соответственно различные задачи безопасной передачи информации.

Среди всевозможных ограничений на действия жучков выделяются три основных вида:

• Временные ограничения. Противник может передвигать жучков лишь через определенное число раундов (аналог скорости в задачах преследования).

• Параллельно-последовательные ограничения. Противник за один ход может передвигать произвольное количество жучков (параллельно), либо по одному жучку за ход (последовательно).

• Ограничения на передвижение. Жучки могут переставляться либо в произвольные вершины (прыгать), либо переставляться только в вершины смежные к занимаемым на данном ходе узлам (ползать).

Отметим, что если Противник передвигает жучков через каждые V раундов, где V — число узлов в Сети, то наименьшее число жучков, позволяющее Противнику собрать информацию при любом протоколе Сети, совпадает с вершинно-поисковым числом графа.

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

Родственные задачи. Аналоги задач о поисковом и вершинно-поисковом числе на ориентированных графах рассматривались Но-ваковски в [128].

Еще один вариант задачи о поисковом числе, называемый одно-шаговым поиском, рассматривался в [68, 69]. В задаче одношагового поиска каждый из преследователей может сделать только один шаг пройти ребро. Смешанный вариант задачи о поисковом числе и задачи о вершинно-поисковом числе изучался в работе [170].

Упомянем также задачу преследования с полной информацией — ''полицейские и грабитель" (cops and robber). Два игрока, полицейский и грабитель, играют на конечном связном неориентированном графе по следующим правилам: вначале, полицейский располагает п своих людей (преследователей) в вершинах графа, где п — некоторое заданное натуральное число. Затем выбирает вершину грабитель и ставит в нее своего человека (убегающего). Далее игроки ходят по очереди. Ход полицейского состоит в том, что он передвигает несколько своих людей в соседние вершины. Грабитель передвигает своего человека в соседнюю вершину или оставляет на месте. На протяжении игры оба игрока обладают полной информацией о местоположении преследователей и убегающего. Полицейский побеждает, если один из его людей оказывается в одной вершине с убегающим ("ловит" грабителя). Грабитель выигрывает, если ему удается ускользнуть от встречи. Наименьшее число преследователей, необходимое для выигрыша полицейского на графе Г, называется полицейским числом графа Г.

Эта игра изучалась многими авторами в работах [43, 45, 46, 48, 49, 83, 84, 89, 118, 127, 135, 171]. Айгнер и Фромм в [43] доказали, что полицейское число планарного графа не превосходит трех. Выяснилось также, что полицейское число связано с родом и обхватом графа. Некоторые вариации задачи о полицейском числе рассматриваются в работе [126].

Основные результаты диссертации

Перейдем теперь к изложению основных результатов диссертации.

Диссертация состоит из введения и трех глав. Основные результаты диссертации опубликованы в [34, 35, 36, 82].

1. Азамов А., Норжигитов X. О минимаксной динамической задаче поиска на графах. Узбекский математ. журнал 1991. №4 С.13-18.

2. Айзеке Р. Дифференциальные игры. М.: Мир, 1967.

3. Альсведе Р., Вегенер И. Задачи поиска, М.: Мир, 1982.

4. Головач П.А. Эквивалентность двух формализаций задачи поиска на графе. Вестник ЛГУ. Сер.1 1989 Вып.1 С.10-14.

5. Головач П.А. Об одном топологическом инварианте в задачах преследования. Дифф. уравнения 1989. т.25 №6 С.923-929.

6. Головач П.А. Вершинно-поисковое и поисковое число соединения графов. Вестник ЛГУ. Сер.1 1990 Вып.2 С.90-91.

7. Головач П.А. Об одной экстремальной задаче поиска на графах. Вестник ЛГУ. Сер.1 1990 Вып.З С.16-21.

8. Головач П.А. Экстремальные задачи поиска на графах. Диссертация на соискание ученой степени к.ф.-м.н. ЛГУ, 1990.

9. Головач П.А. Минимальные деревья с данным поисковым числом. Кибернетика и системный анализ 1992 Вып. 4.

10. Головач П.А. Минимальные деревья с данным вершинно-поисковым числом. Дискр. Математика 1992 Т.4. Вып. 2 С.52-60.

11. Головач П.А. Ширина разреза графа и величина вершинного разделения реберного графа. Дискретная математика том 5, вып. 3 1993 С.76-80.

12. Головач П.А. Ширина разреза графа и величина вершинного разделения гиперграфов и их кениговых представлений. Дискретная математика том 7, вып. 2 1996 С.88-94.

13. Головач П.А., Петров H.H. Поисковое число полного графа. Вестник ЛГУ. С ер А 1986 Вып.4 С.57-60.1.. Головач П.А., Петров H.H. Некоторое обобщение задачи о поисковом числе графа. Вестник СП6ГУ. Сер.1 1995 Вып.З №15 С.21-27.

14. Головач П.А., Петров H.H. ^-поисковое число графов правильных многогранников. Вестник СП6ГУ. Сер.1 1995 Вып.4 №22 С.8-13.

15. Гэри М., Джонсон Д. Вычислительные машины и труднореша-емые задачи. М.: Мир, Í982.

16. Емеличев В.А., Мельников О.И., Сарванов В.И., Тышкевич Р.И. Лекции по теории графов. М.: Наука, 1990.

17. Зеликин М.И. Об одной дифференциальной игре с неполной информацией. Доклады АН СССР 1972. Т. 202, №5. С.998-1000.

18. Зыков A.A. Основы теории графов. М.: Наука, 1987.

19. Ким Д.П. Методы поиска и преследования подвижных объектов. М.: Наука, 1989.

20. Красовский H.H. Управление динамической системой: задача о минимуме гарантированного результата. М.: Наука, 1985.

21. Миркин Б.Г., Родин С.Н. Графы и гены. М.: Наука, 1977.

22. Петров H.H. Некоторые экстремальные задачи поиска на графах. Дифф. уравнения 1982. т.18 №5 С.821-827.

23. Петров H.H. Задачи преследования при отсуствии информации об убегающем. Дифф. уравнения 1982. т.18 №5 С.1345-1352.

24. Петров H.H. Задачи преследования на одномерном остове куба. Дифф. уравнения 1987. т.23 №5 С.908-911.

25. Петров H.H. Задачи поиска на графах правильных многогранников. Дискретная математика том 8, вып. 2 1996 С.108-116.

26. Петров H.H., Старостина С.А. Минимальные графы с поисковым числом меньшим четырех. Вестник ЛГУ. Сер.1 1989 Вып.З С.105-105.

27. Петров H.H., Старостина С.А. О некоторых задачах гарантированного поиска. Вестник СП6ГУ. Сер.1 1994 Вып.1 (№1) С.114-116.

28. Петров Н.Н., Туре И. Об одной задаче преследования на графе. Вестник ЛГУ. Сер.1 1990 Вып.4 С.12-18.

29. Петров Н.Н., Туре И. Определение минимальной численности группы поиска на графе. Вестник ЛГУ. Сер.1 1991 Вып.2 С.66-69.

30. Петросян Л.А., Гарнаев А.Ю. Игры поиска. С.-П.: СПбГУ, 1992.

31. Старостина С.А. Диссертация на соискание ученой степени к.ф.-м.н. СПбГУ, 1993.

32. Растригин А.А. Статистические методы поиска. М.: Наука, 1968.

33. Фомин Ф.В. Задача поиска на графах с ограничением скорости. Вестник СП6ГУ Сер.1 1994 Вып. 3 (№15) С.60-66.

34. Фомин Ф.В. Задача поиска'на деревьях. Вестник СПбГУ Сер.1 1995 Вып. 2 (Ш) С.36-41.

35. Фомин Ф.В. Поиск на 3-минимальных деревьях. Вестник СПбГУ Сер.1 1995 Вып. 3 (№15) С.67-72.

36. Харари Ф. Теория графов. М.: Мир, 1973.

37. Хеллман О. Введение в теорию оптимального поиска. М.: Наука, 1985.

38. Черноусько Ф.Л. Одна задача уклонения от многих преследователей. ПММ. 1976. Т.40, Вып.1. С.14-24.

39. Черноусько Ф.Л., Меликян А.А. Игровые задачи управления и поиска. М.: Наука, 1978.

40. Черноусько Ф.Л. Задачи поиска подвижных объектов. Всесоюзная конф. "Динамическое управление": тезисы докладов. Свердловск, 1979. С.285-286.

41. Abraliamson К., Fellows M. Finite automata, bounded treewidth and well-quasiordering. Collection: Grapli structure theory (Seattle, WA,1991), 539-563, Contemp. Math., 147, Amer. Math. Soc., Providence, RI, 1993.

42. Aigner M., Fromm M. A game of cops and robbers. Discr. Appl. Math., 8 (1984) 1-12.

43. Anderson E.J., Aramendia M. A linear programming approach to the search game on a network with mobile hider. SIAM J. Control and Optimization, 30(1992) 675-694.

44. Andreae T. Note on pursuit game played on a graph. Discr. Appl. Math., 9(1984) 111-115.

45. Andreae T. On a pursuit game played on graphs for which a minor is excluded. J. of Comb. Theory. Ser. B, 41(1986) 37-47.

46. Arnborg S., Lagergren, J., Seese D. Easy problems for tree-decomposable graphs. J. Algorithms, 12 (1991) 308-340.

47. Anstee R.P., Farber M. On a bridged graphs and cop-win graphs. J. of Comb. Theory. Ser. J3, 44 (1988) 27-28.

48. Beraducci A., Jntrigila B. On the cop number of a graph. Adv. in Appl. Math., 14(1993) 389-403.

49. Bienstock D. Graph searching, path-width, tree-width and relative problems (a survey). Reliability of computer and communication networks. Proc. workshop, New Brunswick, NJ/USA 1989, DIMACS Ser. Discrete Math. Theor. CompuL Sci5(1991) 33-49.

50. Bienstock D., Seymour P. Monotonicity in graph searching. J. Algorithms, 12(1991) 239 -245.

51. Biensctock D., Robertson N., Seymour P.D., Thomas R. Quickly excluding a forest. J. Comb. Theory Ser. B, 52(1991) 274-283.

52. Breisch R. An intuitive approach to speleotopology. SWCaves VI 5(1967) 72-78.

53. Bloom G.S., Golomb S.H. Application of numbered undirected graphs. Proc. IEEE 65 (1977) 562-570.

54. Bodlaender H.L. NC-algorithms for graphs with small treewidth. Collection: Graph-theoretic concepts in computer science (Amsterdam, 1988), 1-10 Lecture Notes in Comput. Sci., 344, Springer, Berlin, 1989.

55. Bodlaender H.L. Improved self-reduction algorithms for graphs with bounded treewidth. Collection: Graph-theoretic concepts in computer science (Kerkrade, 1989), 232-244, Lecture Notes in Comput. Sci., 411, Springer, Berlin, 1990.

56. Bodlander H.L. Approximating treewidth, pathwidth and minimum elimination tree height. Lecture Notes in Comput. Sci. 570, Springer, Berlin, 1992.

57. Bodlaender H.L. A tourist guide through treewidth. Acta Cybernet, 11(1993) 1-21.

58. Bodlaender H.L. Complexity of path-forming games. Theoret. Comput. SciM 110 (1993) 215-245.

59. Bodlaender H.L. Dynamic algorithms for graphs with treewidth 2. Collection: Graph-theoretic concepts in computer science (Utrecht, 1993), 112-124, Lecture Notes in Comput. Sci., 790, Springer, Berlin, 1994.

60. Bodlaender H.L. On reduction algorithms for graphs with small treewidth. Collection: Graph-theoretic concepts in computer science (Utrecht, 1993), 45-56, Lecture Notes in Comput. Sci., 790, Springer, Berlin, 1994.

61. Bodlaender H.L.A partial k-arboretum of graphs with bounded treewidth. Technical Report, Utrecht Univers., the Netherlands, 1996.

62. Bodlaender H.L., Fellows M.R. Two strikes against perfect phylogeny. Collection: Automata, languages and programming (Vienna, 1992), 273-283, Lecture Notes in Comput. Sci., 623, Springer, Berlin, 1992.

63. Bodlaender, H.L., Kloks T. Better algorithms for the pathwidth and treewidth of graphs. Collection: Automata, languages and programming (Madrid, 1991), 544-555. Lecture Notes in Comput. Sci., 510, Springer, Berlin, 1991.

64. Bodlaencler H., Kloks T., Kratscli D. Treewidth and pathwidtli of permutation graphs. Collection: Automata, languages and programming (Lund, 1993), 114-125, Lecture Notes in Comput. Sci., 700, Springer, Berlin, 1993.

65. Bodlaender H.L., Moliring R.H. The pathwidth and treewidth of cographs. SIAM J. Discrete Math. 6(1993) 181-188.

66. Chang R.S. Single step graph search problem. Inform. Process. Lett 40(1991) 107-111.

67. Chang R.S., Hsiao J.Y., Tang C.Y. Solving the single step graph searching problem by solving the maximum two-independent set problem. Inform. Process. Lett 40(1991) 283-287.

68. Chung F.R.K. On the cutwidth and the topological bandwidth of a tree. SIAM J.Alg.Disc.Meth. 6(1985) 268-277.

69. Chung F.R.K. Labelings of graphs, in: Selected Topics in Graph Theory 3 (Academic Press, New York, 1988) 151-168.

70. Chung F.R.K. Pebbling in hypercubes. SIAM J. Discrete-Math. 2 (1989) 467-472.

71. Chung F.R.K., Seymour P.D. Graphs with small bandwidth and cutwidth. Graph theory and combinatorics (Cambridge, 1988). Discrete Math. 75 (1989) 113-119.

72. Chinn P.Z., Chvatalova J., Dewdney A.K., Gibbs N.E. The bandwidth problem for graphs and matrices—a survey. J. Graph Theory 6(1982) 223-254.

73. Dawes R.D. Some pursuit-evasion problems on grids. Inform. Process. Lett 43(1992) 241-247.

74. Ellis J.A., Sudborough I.H., Turner J.S. Graph separation and search number. Proc. of Allerton Conf. on Communication, Control and Comput. (1983) 224-233.

75. Ellis J.A., Sudborough I.H., Turner J.S. The vertex separation and search number of a graph. Inform. and CompuL, 113(1994) 50-79.

76. Fellows M.R., Hallet M.T., Wareham H.T. DNA physical mapping: Three ways difficult. In T.Lengauer, ed., Proceedings of European Symposium on Algorithms (ESA'93), Lecture Notes in Comput. Sci., 726, 157-168. Springer, Berlin, 1993.

77. Fellows M.R., Langston M.A. On search, decision and the efficiency of polynomial-time algorithms. In Proceedings of the 21rd Annual Symposium on Theory of Computing, 501-512, 1989.

78. Fitzgerald C.H. The princess and monsters differential game. SIAM J. on Control and Optimization, 17(1979) 700-712.

79. Fomin F.V. The search problem on trees. In:RSCC'-95, 2-nd Russian-Swedish Control Conference, 197-201, St. Petersburg, 1995.

80. Frankl P. On a pursuit game on Cayley graphs. Combinatorica 7(1) (1987), 67-70.

81. Frankl P. Cops and robbers in graphs with large girth and Cayley graphs. Discr. Appl Math. 17 (1987) 301-305.

82. Franklin M., Galil Z., Yung M. Eavesdropping Games: A Graph-Theoretic Approach to Privacy in Distributed Systems. Proceedings 34th Annual Symposium on Foundations of Computer Science 1993, IEEE Computer Society Press 670-679.

83. Gal S. Search games with mobile and immobile hider. SIAM J. on Control and Optimization, 17(1979) 99-122.

84. Garey M.R., Graham R.L., Johnson D.S., Knuth D.E. Complexity results for bandwidth minimization. SIAM J.Appl. Math. 34(1978) 477-495.

85. Gavril F. The intersection graphs of subtrees are exactly the chorda! graphs. J. Comb. Theory Ser. B 16(1974) 47-56.

86. Goldstein A.S., Reingold E.M., The complexity of pursuit on a graph. Theoretical Computer Science 143(1995) 93-112.

87. Gustedt J., On the pathwidth of chorda! graphs. Discrete Appl. Math. 45 (1993) 233-248.

88. Gupta A., Nisliimura N. Characterizing the complexity of subgraph isomorphism for graphs of bounded path-width. In 13th Symp. Theoretical Aspects of Computer Science (STACS), 1996.

89. Heath L.M. Embedding outerplanar graphs in small books. SIAM J.Alg.Disc.Meth. 8(1987) 198-218.

90. Juvan M., Mohar B. Optimal linear labeling and eigenvalues of graphs. Discr. Appl Math. 36(1992) 153-168.

91. Juvan M., Mohar B. Laplace eigenvalues and bandwidth-type invariants of graph J. of Graph Theory 17 393-407.

92. Kashiwabara T., Fujisawa T. NP-completness of the problem of finding a minimum clique number interval graph containing a given graph as a subgraph, in: Proceedings ISCAS (1979) 657-660.

93. Kfoury A.J. The pebble game and logics of programs. Collection: Harvey Friedman's research on the foundations of mathematics, 317-329 Stud. Logic Foundations Math., 117, North-Holland, Amsterdam-New York, 1985.

94. Kim C.E., Langston M.A. Movement coordination for single-track robot system. J.Robotic systems, 4(1987) 49-62.

95. Kinnersley N.G. Immersion order obstruction sets. Proceedings of the Twenty-fourth Southeastern International Conference on Combinatorics, Graph Theory, and Computing (Boca Raton, FL, 1993). Congr.-Numer. 98(1993), 113-123.

96. Kinnersly N.G. The vertex separation number of a graph equals its path-width. Inform. Process. Lett 42(1992) 345-350.

97. Kinnersley N.G., Langston M.A. Obstruction set isolation for the Gate Matrix Layout problem. Discrete Appl Math. 54(1994) 169-213.

98. Kirousis L.M., Papadimitriou C.H. Interval graphs and searching. Discrete Mathematics 55(1985) 181-184.

99. Kirousis L.M., Papadimitriou C.H. Searching and pebbling. Theoretical Computer Science 47(1986) 205-218.

100. Ivloks, T. Treewidth of circle graphs. Collection: Algorithms and computation (Hong Kong, 1993), 108-117, Lecture Notes in Comput. Sci., 762, Springer, Berlin, 1993.

101. Kloks T., Bodlaender H.L., Muller H., Kratsch D. Computing treewidth and minimum fill-in: all you need are the minimal separators. Collection: Algorithms—ESA '93 (Bad Honnef, 1993), 260-271, Lecture Notes in Comput. Sei., 726, Springer, Berlin, 1993.

102. Kloks T., Bodlaender H. Approximating treewidth and pathwidth of some classes of perfect graphs. Collection: Algorithms and computation (Nagoya, 1992), 116-125, Lecture Notes in Comput. Sei., 650, Springer, Berlin, 1992.

103. Kloks T., Kratsch D. Treewidth of chordal bipartite graphs. Collection: STACS 93 (Wurzburg, 1993), 80-89, Lecture Notes in Comput. Sei., 665, Springer, Berlin, 1993.

104. Korach E., Solel N. Tree-width, path-width and cut-width. Discr. Appl Math. 43(1993) 97-101.

105. Kornai A., Tuza Z. Narrowness, pathwidth, and their application in natural language processing. Discrete Appl Math. 36 (1992) 87-92.

106. LaPaugh A. Recontamination does not help to search a graph. Technical Report EECS-335. Dept. Computer Science. Princeton Univ. Princeton, 1982.

107. LaPaugh A. Recontamination does not help to search a graph. J.of ACM. 40(1993) 224-245.

108. Leierson C.E. Area-efficient graph layouts for VLSI, in "Proceedings, 21st Annual Symposium on Foundations of Computer Science". (1980) 270-281.

109. Lengauer T., Black-white pebbles and graph separation, Acta Inform. 16(1981) 465-475.

110. Lipton R.J., Tarjan R.E. Applications of a planar separator theorem. SIAM J. Comput 3(1980) 615-627.

111. Makedon F.S., Papaclimitriou C.H., Sudborougli I.H. Topological bandwidth. SIAM J.Alg.Disc.Meth. 6(1985) 418-443.

112. Makedon F.S., Sudborough I.H. On minimizing width in linear layouts. Discr. Appl Math. 23(1989) 243-265.

113. Makedon F.S., Sudborough I.H. Min Cut is NP-complete for edge weighted trees. Theor. Computer Sei. 58(1988) 209-229.

114. Megiddo N., Hakimi S.L., Garey M.R., Johnson D.S., Papadimit-riou C.H. The complexity of searching a graph. J. of ACM. 35(1988)18 44.

115. Maamoun M., Meyniel H. On a game of policemen and robber. Discr. Appl Math., 17 (1987) 307-309.

116. Miller Z., A linear algorithm for topological bandwidth in degree-three trees. SIAM J. Comput17(1988) 1018-1035.

117. Miller Z., Sudborough I.H. A polynomial algorithm for recognizing small cutwidtli in hypergraphs. Collection: VLSI algorithms and architectures (Loutraki, 1986), 252-260, Lecture Notes in Comput. Sci., 227, Springer, Berlin, 1986.

118. Miller Z. Graph layouts. Collection: Applications of discrete mathematics, 365-393, McGraw-Hill, New York, 1991.

119. Miller Z., Sudborough I.H. A polynomial algorithm for recognizing bounded cutwidth in hypergraphs. Math. Systems Theory, 24(1991) 11-40.

120. Moews D. Pebbling graphs. J. Combin. Theory Ser. B, 55(1992) 244 252.

121. Mohar B. Laplace eigenvalues of graphs—a survey. Discrete Math., 109(1992) 171-185.

122. Mohring R.H. Graph problems related to gate matrix layout and PLA folding, in: G. Tinhofer et al., eds., Computional Graph Theory, Computing Supplementum, 7 (Springer, Wien, 1990) 17-51.

123. Nowakowski R.J. Winkler N.P. Vertex-to-vertex pursuit in a graph. Discrete Math. 43(1983) 325-329.

124. Nowakowski R.J. Search and sweep numbers of finite directed acyclic graphs. Discr. Appl. Math., 4(1993) 11-11.

125. Ohtsuki T., Mori H., Kuh E.S., Kashiwabaxa, Fujisawa. One-dimensional logic gate assignment and interval graphs, IEEE Trans. Curcuits and Systems 26(1979) 675-684.

126. Papadimitriou C.H. The NP-completness of the bandwidth minimization problem. Computing, 16(1976) 263-270.

127. Papadimitriou C.H. Computiona! complexity. Addison-Wesley Publ. Comp. 1994.

128. Parra A., Scheffler P. Treewidth equals bandwidth for AT-free claw-free graph. Technical Report 436 Department of Mathematics TU Berlin, 1995.

129. Parsons T.D. Pursuit-evasion in a graph. In Theory and Application of Graphs, Y.Alavi and D.R.Lick, Eds Springer-Verlag, 1976, 426-441.

130. Parsons T.D. The search number of a connected graph. In Proceedings of the 9th Southeastern Conference on Combinatorics, Graph Theory and Computing. Utilitas Mathematical Winnipeg, Canada, 1978 549-554.

131. Quilliot A. A short note about pursuit games played on a graph with a given genus. J. of Comb. Theory Ser. B, 38(1985) 89-92.

132. Robertson N., Seymour P.D. Graph minors. I. Excluding a forest. J. Comb. Theory Ser. B, 35 (1983) 39-61.

133. Robertson N. and Seymour P.D. Generalizing Kuratowskis theorem. Congressus Numerantium, 45(1984) 129-138.

134. Robertson N. and Seymour P.D. Graph minors. III. Planar tree-width. J. Comb. Theory Series B, 36(1984) 49-64.

135. Robertson N. and Seymour P.D. Graph width and well-quasi ordering: a survey. In J. A. Bondy and U. S. R. Murty, editors, Progress in Graph Theory, pages 399-406, Toronto, 1984. Academic Press.

136. Robertson N., Seymour P.D. Disjoint paths—a survey. SIAM J. Alg. Discr. Meth., 6(1985) 300-305.

137. Robertson N. and Seymour P.D. Graph minors — a survey. In I. Anderson, editor, Surveys in Combinatorics, pages 153-171. Cambridge Univ. Press, 1985.

138. Robertson N., Seymour P.D. Graph minors. II. Algoritmic aspect of tree-width. J. Algorithms, 7(1986) 309-322.

139. Robertson N. and Seymour P.D. Graph minors. V. Excluding a planar graph. J. Comb. Theory Series B, 41(1986) 92-114.

140. Robertson N. and Seymour P.D. Graph minors. VI. Disjoint paths across a disc. J. Comb. Theory Series 5, 41(1986) 115-138.

141. Robertson N. and Seymour P.D. Graph minors. VII. Disjoint paths oil a surface. J. Comb. Theory Series B, 45(1988) 212-254.

142. Robertson N. and Seymour P.D. Graph minors. IV. Tree-width and well-quasi-ordering. J. Comb. Theory Series B, 48(1990) 227-254.

143. Robertson N. and Seymour P.D. Graph minors. IX. Disjoint crossed paths. J. Comb. Theory Series B, 49(1990) 40-77.

144. Robertson N. and Seymour P.D. Graph minors. VIII. A Kuratowski theorem for general surfaces. J. Comb. Theory Series 5, 48(1990) 255-288.

145. Robertson N. and Seymour P.D. Graph minors. X. Obstructions to tree-decomposition. J. Comb. Theory Series 52(1991) 153-190.

146. Robertson N. and Seymour P.D. Graph minors. XL Distance on a surface. J. Comb. Theory Series B, 60(1994) 72-106.

147. Robertson N. and Seymour P.D. Graph minors. XII. Excluding a non-planar graph. J. Comb. Theory Series B, 64(1995) 240-272.

148. Robertson N. and Seymour P.D. Graph minors. XIII. The disjoint paths problem. J. Comb. Theory Series B, 63(1995) 65-110.

149. Robertson N. and Seymour P.D. Graph minors. XIV. Extending an embedding. J. Comb. Theory Series B, 65(1995) 23-50.

150. Robertson N., Seymour P.D., and Thomas R. Quickly excluding a planar graph. J. Comb. Theory Series B, 62(1994) 323-348.

151. Rosenberg A.L., Sudborough I.H. Bandwidth and pebbling. Computing, 31(1983) 115-139.

152. Scheffler P. Optimal embedding of a tree into an interval graph in linear time. Fourth Czechoslovakian Symposium on Combinatorics, Graphs and Complexity Ann. Discr. Math., North-Holland, Amsterdam, 1992, 287-291.

153. Scheffler P. A linear algorithm for the pathwidth of trees. Collection: Topics in combinatorics and graph theory (Oberwolfach, 1990), 613-620 Physica, Heidelberg, 1990.

154. Sethi R. Complete register allocation problems, SIAM J.Comput., 4(1975) 226-248.

155. Seymour P.D., Thomas R. Graph searching and a min-max theorem for tree-width. J. of Comb. Theory. Ser. B, 58(1993) 22-33.

156. Sugihara H., Suzuki I., Lee Y.C. Distributed algorithms for motion coordination of multiply objects, in Proc. 30st Midwest Symposium on Circuits and System, Syracuse, NY, 1987, 652-655.

157. Sugihara H., Suzuki I. On pursuit-evasion problem related to motion coordination of mobile robots, in Proc. 21st Hawaii Internat. Conf on System Sciences, Kailua-Ivona, Hawaii (1988) 218-226.

158. Sugihara H., Suzuki I. Optimal algorithms for a pursuit-evasion problem in grids. SIAM J.Discrete Math., 2(1989) 126-143.

159. Takahashi A., Ueno S., Kajitani Y. Mixed searching and proper-path-widtli. Theoretical Computer Science, 137(1995) 253-268.

160. Tosic R. On cops and robbers game. Studia Scientarurn Math. Hungarica, 23(1988) 225-229.

161. Wagner K. Uber eine Eigenshaft der ebenen Complexe. Math. Ann., 14(1937) 570-590.

162. Wiegers M. The A;-section of treewidth restricted graphs. Collection: Mathematical foundations of computer science (Banska Bystrica, 1990), 530-537, Lecture Notes in Comput. Sci., 452, Springer, Berlin, 1990.

163. Yannakakis M. A polyminal algorithm for the min-cut lineal arrangement of trees. J. of ACM, 32(1985) 950-988.