Задачи гарантированного поиска на графах тема диссертации и автореферата по ВАК РФ 01.01.09, кандидат физико-математических наук Абрамовская, Татьяна Викторовна

• Абрамовская, Татьяна Викторовна
• кандидат физико-математических наук
• 2012

Оглавление диссертации кандидат физико-математических наук Абрамовская, Татьяна Викторовна

Введение.

Глава 1. Проблема гарантированного поиска на деревьях.

1.1. Задача г-поиска. Функция Головача и ее свойства.

1.2. Двойственная задача и скачок функции Головача.

1.3. Технические замечания и дополнительные определения

1.4. Лемма о трёх ветвях.

1.5. Задача поиска на деревьях с малым числом преследователей

1.6. Достаточное условие невырожденности функции Головача для деревьев.

1.7. Проблема малых изменений длин рёбер.

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

2.1. Невырожденность функции Головача для деревьев с малым числом рёбер.

2.2. Минимальное по числу рёбер дерево с вырожденной функцией Головача.

2.3. Неединичный скачок функции Головача в условиях ограничения на степень вершин.

2.4. Нетривиальный скачок для минимальных деревьев с рёберно-поис-ковым числом п.

2.5. Сколь угодно большой скачок функции Головача на деревьях

Глава 3. Некоторые проблемы теории ^-поиска.

3.1. Монотонность ^-поискового числа.

3.2. Полный подграф и почти полный граф.

3.3. Проблема реализуемости функции, обладающей свойствами функции Головача

Введение диссертации (часть автореферата) на тему «Задачи гарантированного поиска на графах»

Круг проблем, изучаемых в настоящем диссертационном исследовании, очерчивается идеей гарантированного поиска, выделяющей их в отдельный класс задач. Задачи подобного рода существенно отличаются от дифференци-1 ь альных игр преследования-уклонения с неполной информацией, рассмотренных Р. Айзексом в [8], хотя именно в указанной монографии ставится проблема «Принцесса и Чудовище» ([8], раздел 12.4), безусловно, оказавшая влияние на развитие теории гарантированного поиска и заключающаяся в следующем. В абсолютно тёмном помещении, форма и границы которого известны, Чудовище ловит Принцессу, если ему удаётся приблизиться к ней на заданное расстояние. При этом ограничений на скорость Принцессы не накладывается, а плата в указанной игре поиска — время поимки. Эта проблема была решена М. И. Зеликиным [21] в случае, если ареной поиска является окружность, и в дальнейшем широко изучена, в том числе на некоторых графах специального вида [35, 45, 46, 60, 61].

В основу задач гарантированного поиска положен «минимаксный принцип», не использующий вероятностного описания поведения игроков. Типичная задача гарантированного поиска на графах, на неформальном уровне, может быть сформулирована следующим образом. На графе группа игроков-преследователей ловит (в том или ином смысле) невидимого для них убегающего. Цель команды преследователей — построить «программу» действий, которая обеспечивала бы им поимку убегающего при любом его поведении. Иными словами, поимка должна быть гарантирована даже в том случае, когда выбранная преследователями программа становится известной убегающему «до начала поиска». В каждой формализации задачи поиска фиксируются динамические возможности участников, условие успешного завершения поиска (условие поимки), арена поиска (комбинаторный или топологический граф), и ставится следующая задача: найти наименьшее число преследователей, необходимое для успешного завершения поиска.

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

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

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

Под графом понимается конечный связный топологический граф, вершины которого - точки в Ж3, рёбра — конечнозвенные ломаные, соединяющие две вершины и пересекающиеся только в вершинах.

На графе введена метрика р — длина кратчайшего (по евклидовой норме) пути, соединяющего две точки и полностью лежащего в графе.

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

Преследователи): х, = щ, I е {1,2,., к}, (Убегающий): у = щ.

Допустимые управления — кусочно постоянные вектор-функции, заданные на произвольных замкнутых временных отрезках [0, г].

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

Программой команды преследователей называется совокупность траекторий {х\(0,Х2(0> • • •»хк(0, * £ [0, г]}. Если при любой траектории убегающего у выбранная программа гарантирует поимку убегающего, то такая программа называется выигрывающей.

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

Задача е-поиска состоит в определении минимальной численности бе{(У) команды преследователей, обладающей выигрывающей программой с радиусом поимки е.

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

Поточечная поимка, т. е. случай £ = 0, приводит к оригинальной задаче гарантированного поиска на графах, поставленной в [73] и [25]. Несмотря на некоторые различия формализаций Парсонса и Петрова, Головачом в [11] доказана их эквивалентность между собой, а также эквивалентность некоторой дискретной задаче на соответствующем комбинаторном графе ([10]). Таким образом, в случае поточечной помки на графе С рассматриваемую задачу называют задачей Парсонса-Петрова, искомое в ней минимальное число преследователей еБ(С) — рёберно-поисковым числом (в каждой формализации задачи гарантированного поиска ищется то или иное поисковое число, для их различения образуют соответсвующее составное слово).

Упомянутая выше дискретная задача, поставленная на комбинаторном графе, формулируется следующим образом.

Движение каждого преследователя описывается последовательностью ходов. Каждым ходом преследователь может быть а) поставлен в вершину, б) снят с вершины, с) передвинут из вершины в вершину вдоль ребра.

Дискретная задача трактуется как задача очистки графа. Первоначально все рёбра предполагаются загрязнёнными. Ребро е с концами х,у становится очищенным в двух случаях:

1. либо один преследователь стоит в х, а другой переходит из х в у вдоль ребра е,

2. либо все рёбра, инцидентные х, за исключением е, очищены, и преследователь переходит из х в у вдоль ребра е.

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

В работах [73] и [25] решена задача Парсонса-Петрова для деревьев, в частности, Н. Н. Петров показал, что рёберно-поисковое число дерева совпадает с его степенью ветвления — топологическим инвариантом, который эффективно вычисляется.

Возможность очистки произвольного графа С без повторного загрязнения его рёбер командой преследователей, состоящей из к = еБ(С) преследователей, замечена А. ЛаПо и доказана в [66] (альтернативное доказательство приведено в [47]). Таким образом, множество программ преследователей, необходимых к рассмотрению в задаче Парсонса-Петрова на графе С, существенно сужается. Понятия очищенного и загрязнённого множеств естественным образом могут быть перенесены на общий случай е-поиска, но указанное свойство для положительных е принципиально не выполняется.

В работе [72] доказано, что задача вычисления рёберно-поискового числа графа в общем случае является А^Р-полной. На основе результатов Парсонса-Петрова, авторы работы [72] построили полиномиальный алгоритм для вычисления рёберно-поискового числа дерева. В той же работе [72] охарактеризованы графы с рёберно-поисковым числом, не превосходящим 3. Аналогичные результаты были получены в [29].

Известны работы, в которых рассматриваются бинарные операции над графами (см. [22] стр. 18). Например, в работе [80] рёберно-поисковое число декартова произведения непересекающихся графов выражается через рё-берно-поисковые числа операндов. Для соединения графов задача Парсонса-Петрова решена в [13]. Там же строится рёберно-поисковое число для всех полных п-дольных графов, определяемых как соединение п пустых графов.

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

Множество приложений задачи ГТарсонса-Петрова возникает в связи с поисковым числом ещё одной дискретной задачи гарантированного поиска. В работе Кироузиса и Пападимитриу [64] впервые была рассмотрена задача о вершинно-поисковом числе. В этой задаче движение каждого преследователя также описывается последовательностью ходов, но правила игры более простые. Каждым ходом либо преследователь ставится в вершину, либо один из преследователей, находящихся на графе, снимается. Ребро считается очищенным, если его концы заняты преследователями. Повторное загрязнение ребра определяется так же, как и в задаче о рёберно-поисковом числе. Вер-шинно-поисковое число графа для каждого графа G получило стандартное обозначение ns(G). Рёберно- и вершинно-поисковые числа (комбинаторного) графа G связывает очевидное соотношение ns(G) - es(G)\ < 1.

В [64] доказано, что рёберно-поисковое число графа, полученного из G помещением на каждое ребро двух вершин степени 2, совпадает с вершинно-поис-ковым числом G. Там же показано, что задача нахождения вершинно-поиско-вого числа в общем случае является TVP-полной, для деревьев, как и в задаче Парсонса-Петрова, разработаны линейные алгоритмы [54, 74, 75].

Топологические инварианты графов, о которых далее пойдёт речь, определяются при помощи нумераций вершин графов. Линейной укладкой (linear layout) графа G называется биекция

L : {1G,n = \VG\. Множество всех линейных укладок графа G обозначим через £(G).

Положим cw(G, L) := max {(и, v) e EG : L \u) < i, L~\v) > ill el,и 11 и cw(G) := min cw(G, L).

LeJXG)

Величина cw(G) называется шириной разреза (cut-width) графа G. Схожим образом определяются модифицированная ширина разреза (modified cut-width), величина вершинного разделения (vertex separation number) графа — все эти величины играют большую роль в теории сверхбольших интегральных схем при проектировании «линейных укладок» СБИС (см. обзор приложений в [7]). Типичная модель электронной микросхемы описывается графом G, в котором вершинами являются «переключатели», а рёбрами — «соединители». Если переключатели «укладываются» на прямой в порядке, задаваемой нумерацией L, то величины cw(G, L), mcw(G, L), vs(G, L) характеризуют «дефект» этой укладки, зависящий от рёберной структуры графа G.

Связь рёберно-поискового числа с указанными характеристиками графов описывается различными соотношениями, например, в [71 ] показано, что для всякого графа G справедливы следующие неравенства: es(G) < cw(G) < jA(G) es(G) - 1) + 1, где A(G) — максимальная степень вершины в графе G.

Изучению проблемы выражения рёберно-поискового числа через указанные инварианты посвящены работы [13, 54, 64, 71], исследования введённых характеристик и их применений в теории СБИС проводятся в [19, 67, 68, 81].

Посредством линейных укладок графов определяются также такие инварианты как ширина ленты (bandwidth) и топологическая ширина ленты (topological bandwidth) графа.

Пусть L е £(G), положим b(G, L) := max {|L~\u) - L-1(v)| : (и, v) e EG} и b(G) min b(G,L).

Le-C(G)

Величина b(G) называется шириной ленты графа G.

Следующая величина называется топологической шириной ленты графа tb(G) := min {b{G')}, где минимум берётся по всем графам G', получаемых из G помещением на его рёбра конечного числа вершин степени 2.

Связь этих двух характеристик с поисковыми числами показана в [70]. В работе [65], располагающей подробной библиографией, приводятся описания приложений в линейной алгебре, теории СБИС, в параллельных вычислительных системах, в некоторых задачах в области Искуственного Интеллекта и Биологии. Связь ширины ленты графа с одной задачей поиска {helicopter search problem) установлена Ф. В. Фоминым [56, 57]. С многочисленными результатами, касающимися ширины ленты графа, можно познакомиться в обзорах [51, 52, 65].

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

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

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

Обозначим через S множество всех стратегий игрока, приводящих к «замощению» графа ö. Для каждой стратегии s е S введём в рассмотрение величину dem s, равную максимальному числу камней, одновременно находящихся на графе при использовании стратегии s. Определим величину dem G := mindern s, seS называемую демандом графа G.

Для произвольного (неориентированного) графа G через 0(G) обозначим множество всех ориентированных ациклических графов ö, полученных из G заданием ориентаций на всех его рёбрах.

Положим

Dem(G) := min dem G. eO(G)

Тогда, как показано в [64], для каждого графа G имеет место равенство

Dem(G) = ns(G).

Кироузис и Пападимитриу в [63] установили также связь между вершинно-поисковым числом и графами интервалов (см. [41], с. 35), которые, помимо самостоятельного интереса, привлекают внимание своими приложениями, например, в проблеме картирования человеческого генома [55].

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

Граф Н называется минором графа С, если Н получен стягиванием некоторых к рёбер (к > 0) одного из подграфов графа С.

Путевая ширина используется при изучении графов, имеющих в качестве минора лес. Говоря неформально, чем больше путевая ширина графа, тем «больше» лес, содержащийся в качестве минора этого графа. Древовидная ширина естественным образом возникает при исследовании структуры графов, имеющих в качестве минора планарный граф. Обзор многочисленных результатов Робертсона и Сеймура приведён в [48].

Более полная библиография и дальнейшие описания приложений о вер-шинно- и рёберно-поисковых числах приведены в [7, 39].

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

Некоторые черты ^-поискового числа существенно отличают задачу определения е-поискового числа от задач о рёберно- и вершинно-поисковых числах. Уже указывалась принципильная невозможность очищения некоторых графов без повторного загрязнения. Ещё одним свойством, которое чуждо перечисленным проблемам и существенно усложняет решение задачи е-поиска, является возможность роста е-поискового числа при переходе к подграфу. В общем случае может оказаться, что яЕ(Н) > для связного подграфа Н графа С и некоторого £ > 0.

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

20, 23, 31, 34], в которых были получены первые результаты, касающиеся поиска с противодействием.

Важной формализацией проблемы гарантированного поиска на топологических графах является задача, впервые поставленная Н. Н. Петровым в [26]. От задачи е-поиска её отличает поточечная поимка и введение ограничений на скорости игроков.

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

Преследователи): х{ = щ, ||м,|| <1, /6 1 ,п, (Убегающий): у = и о, ||ио11 ^ где ||. .|| — евклидова норма в К.3, а допустимые управления, как прежде, — кусочно постоянные вектор-функции, заданные на произвольных промежутках [0,т].

Ставится задача о нахождении наименьшей численности команды преследователей, обладающей выигрывающей программой. Искомая величина называется ¡1-поисковым числом графа С и обозначается

В работе [26] доказано, что если граф С имеет, по крайней мере, одну вершину степени большей 2, то > 2 для всех /л > 0, причём если ц достаточно мало, то = 2. Иначе говоря, на любом графе С двое преследователей всегда имеют выигрывающую программу, если их преимущество в скорости (т. е. число ¿Г1) достаточно велико.

В работах [26, 39, 69] исследуются ¿/-поисковые числа для одномерных остовов правильных многогранников и полных графов. Указанные классы графов часто становятся объектами исследования в задачах поиска, так как облегчают нахождение поискоых чисел наличием симметрии, однородностью и другими упрощающими моментами. В общей ситуации поисковые числа графов удаётся найти лишь в исключительных случаях.

Один из методов исследования //-поискового числа разработан Ф. В. Фоминым ([39, 40]) с использованием так называемых дискретных программ.

Программа П команды преследователей, заданная для / е [0, г], т — натуральное число, называется дискретной, если для любого к е (1,2,., т} на промежутке времени [к - 1 ,к] каждый из преследователей либо стоит в вершине графа, либо переходит из вершины в смежную вершину с максимальной скоростью.

Доказано, что если длины рёбер графа равны, а максимальная скорость убегающего равна 1, то из существования выигрывающей программы п преследователей следует наличие у них дискретной выигрывающей программы некоторого специального вида. Доказывается также, что таких программ конечное число. Таким образом, в рассматриваемом случае решение задачи сводится к конечному перебору. В общей ситуации такое сведение, по-видимому, невозможно.

Головачом в [13] доказано равенство ¿/-поискового и рёберно-поискового чисел для больших //: если // > 4 Ь-Г1, где / — длина кратчайшего ребра графа С,аЬ — сумма длин всех его рёбер, то ^(С) = е8(С).

Совпадение рёберно- и /¿-поисковых чисел отмечается Ф. В. Фоминым в [37] на деревьях: для всех // > 1 и произвольного дерева Т выполнено ^(Г) = е$(Г). Исследование //-поискового числа проводится также в [17, 38].

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

Пусть множество М, на котором ставится задача поиска, снабжено структурой топологического пространства, й — некоторая метрика на нём (вообще говоря, никак не связанная с этой структурой), е — неотрицательное число, характеризующее «радиус поимки». Путь у на М, т. е. непрерывное отображение [0,1] —» М, интерпретируется как «траектория» одного из участников поиска. Совокупность путей x¡,i = 1,.,«} называется выигрывающей программой для группы п преследователей, если для любого пути у («траектории убегающего») найдётся такой момент т е [0,1], что d(Xi(T),y(r)) < s для некоторого i € 1 ,п.

В работах [30, 36] предполагалось, что M является замкнутым полигонально связным подмножеством евклидова пространства Е3 с топологией, ин-дуцированнои из Е3, а траектории преследователей и убегающего суть непрерывные функции времени со значениями в М.

Введём на M следующую метрику do. Пусть а и b — две различные точки M и L(a, b) — множество всех ломаных, лежащих в M и соединяющих точки а и Ь. Для каждой такой ломаной / через g(J) обозначим число её звеньев. Положим do(a, b) = min {g(l) : l e L(a, b)} и do(a, a) = 0.

В работе [30] получен следующий результат: если в множестве M существует «равносторонний» треугольник, сторона которого (в метрике do) не меньше 6 (т. е. множество M содержит три точки, попарно соединяемые ломаными с не менее чем шестью звеньями), то ß{M) > 2. Для множества М, являющегося деревом особого вида, это достаточное условие является также и необходимым. Некоторые достаточные условия равенства ß(M) = 1 получены Сузуки и Ямашито в [79].

Если M является решёткой (см., например, [41] с. 227), то, как показано в работах [77, 78], сформулированная выше задача связана с проблемами координации движений роботов.

В цикле работ [15, 16] вводится другое обобщение задачи о поисковом числе графа, существенное отличие которого от задачи о нахождении e-поискового числа заключается в ином определении метрики на графе.

Пусть G — топологический граф, введём метрику dа на графе. Положим а-{х,х) = 0 для любого д; 6 б. Если х,у е С, х Ф у, то йо-(х,у) совпадает с минимальным натуральным к, таким, что путь из х в у, полностью лежащий в графе, пересекает к рёбер.

Зафиксируем к е N. Убегающий считается пойманным, если в некоторый момент он сблизится с хотя бы одним из преследователей на расстояние к во введённой метрике с^. Минимальное число преследователей, необходимое для поимки убегающего в описанной задаче, называется к-поисковым числом и обозначается сг^(С). Следует отметить, что при к = 0 ¿-поисковое число совпадает с рёберно-поисковым числом, а при к = 1-е 1-поисковым числом, рассмотренным в работах [32, 33]. Заметим, что ¿-поисковое число является топологическим инвариантом графа. Как показано в [16], задача определения ¿-поискового числа сводится к дискретной задаче, и вследствие этого она может быть эффективно решена для некоторых классов графов.

Так в работе [16] задача нахождения ¿-поискового числа решена для графов интервалов, что позволяет также выписать точные формулы для полных графов, теоремы о ¿-поисковых числах графов правильных многогранников приведены в работах [16, 27].

Завершим обзор задач гарантированного поиска, отметив работу [59], содержащую достаточно полную библиографию по исследуемому вопросу, и перейдём к описанию результатов по теории ^-поиска.

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

Для произвольного графа е-поисковое число, как и рёберно-поисковое число, может быть вычислено с помощью конечной процедуры (см. [12, 13]). Приведём здесь результат [12], позволяющий при исследовании е-поисковых чисел ограничиться рассмотрением программ преследователей специального вида.

Пусть £ > О, я£(С) < п, п € N. Тогда существует выигрывающая программа П команды п преследователей на С такая, что в каждый момент времени из множества задания программы П на любом ребре графа С находятся не более двух преследователей.

Это утверждение можно усилить, если рассматривать достаточно малый радиус поимки.

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

Работа П. А. Головача [12] содержит фундаментальные результаты. В частности, показано, что 5В(С) как функция радиуса поимки — невозраста-ющая кусочно постоянная непрерывная справа функция.

Там же доказано совпадение рёберно- и е-поисковых чисел для радиусов поимки меньших четверти длины кратчайшего ребра, а для всех в, меньших половины длины кратчайшего ребра графа С, имеют место следующие неравенства: ея(С) - 1 < <

Ещё одна оценка ^-поискового числа для радиуса поимки, меньшего длины кратчайшего ребра графа, опубликована в [28], для её описания нам понадобятся некоторые дополнительные определения.

Обозначим через С (у) подграф графа С, порождаемый множеством смежных с v вершин, а через у) — число компонент связности графа С (у) с ровно к вершинами. Определим величины оо и c(G) := min c(G, v). veVG

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

1. se(G) > c(G);

2. если для каждой вершины v е VG все коэффициенты v) с нечётными номерами к равны 0, то se(G) > c(G) + 1.

Приведённые выше утверждения позволили построить функции Головача для одномерных остовов тетраэдра, куба и октаэдра с рёбрами единичной длины (см. [17, 28, 58]). Решение задачи s-поиска для полных графов приводится в [17, 28]. Изучение рёберно-поискового числа для соответствующих графов икосаэдра и додекаэдра проводится в [18].

Перейдём к изложению основных результатов диссертации. Работа состоит из введения и трёх глав. Основные результаты настоящего исследования опубликованы в работах [1,2, 4-6, 44].

Список литературы диссертационного исследования кандидат физико-математических наук Абрамовская, Татьяна Викторовна, 2012 год

1. Абрамовская Т. В. Нетривиальные разрывы функции Головача для деревьев // Вестник СПбГУ. Сер. 1. 2010. № 3. С. 3-12.

2. Абрамовская Т. В. Проблема реализуемости функции со свойствами функции Головача // Вестник СПбГУ. Сер. 1. 2012. № 2. С. 3-10.

3. Абрамовская Т. В., Петров Н. Н. Геометрические проблемы теории поиска // Труды математического центра имени Н.И.Лобачевского: Материалы VIII научной школы-конференции Лобачевские чтения 2009. Казань: Казан. матем. об-во, 2009. Т. 39. С. 1-10.

4. Абрамовская Т. В., Петров Н. Н. О некоторых задачах гарантированного поиска на графах // Вестник СПбГУ. Сер. 1. 2010. № 2. С. 64-70.

5. Абрамовская Т. В., Петров Н. Н. О монотонности поискового числа в задаче Головача. Вестник СПбГУ // Вестник СПбГУ. Сер. 1. 2011. № 4. С. 3-9.

6. Абрамовская Т. В., Петров Н. Н. О сколь угодно больших скачках функции Головача для деревьев // Вестник СПбГУ. Сер. 1. 2011. № 1. С. 84-93.

7. Абрамовская Т. В., Петров Н. Н. Теория гарантированного поиска на графах // Дифференциальные уравнения и процессы управления. 2012. Т. 2. С. 9-65. URL: http://www.math.spbu.ru/diffjournal/RU/numbers/ 2012.2/article.165.html.

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

9. Ахо А. В., Хопкрофт Д., Ульман Д. Д. Структуры данных и алгоритмы. Москва: Вильяме, 2003.

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

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

12. Головач П. А. Об одной экстремальной задаче поиска на графах // Вестник ЛГУ. Сер. 1. 1990. Т. 15(№3). С. 16-21.

13. Головач П. А. Экстремальные задачи поиска на графах: Кандидатская диссертация/ЛГУ. 1990.

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

15. Головач П. А., Петров Н. Н. Некоторые обобщения задачи о поисковом числе графа//Вестник СПбГУ. Сер. 1. 1995. Т. 15(№3). С. 21-27.

16. Головач П. А., Петров Н. Н. /Г-поисковое число графов правильных многогранников//Вестник СПбГУ Сер. 1. 1995. Т. 22(№4). С. 8-13.

17. Головач П. А., Петров Н. Н., Фомин Ф. В. Поиск на графах // Труды института математики и механики УрО РАН. 2000. Т. 6(№1). С. 39-54.

18. Головач П. А., Фомин Ф. В. Поисковое и вершинно-поисковое число двой-, ственных графов // Вестник СыктГУ. Сер.1. 2001. № 4. С. 125-136.

19. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. Москва: Мир, 1982.

20. Зеленевская А. Б., Петров Н. Н. О некоторых задачах поиска на графах с противодействием // Вестник СПбГУ. Сер. 1. 2004. № 2. С. 23-33.

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

22. Зыков А. А. Основы теории графов. Москва: Вузовская книга, 2004.

23. Капилевич В. О., Петров Н. Н. Задачи поиска на графах с противодействием // Вестник СПбГУ. Сер. 1. 2003. № 3. С. 31-37.

24. Кнут Д. Э. Искусство программирования, том 1. Основные алгоритмы, 3-е изд. : Пер. с анг. Москва: Вильяме, 2001.

25. Петров Н. Н. Задачи преследования при отсутствии информации об убегающем // Дифференциальные уравнени. 1982. Т. 18(№8). С. 1345-1352.

26. Петров Н. Н. Некоторые экстремальные задачи поиска на графах // Дифференциальные уравнени. 1982. Т. 18(№5). С. 821-827.

27. Петров Н. Н. Задачи поиска на графах правильных многогранников // Дискретная математика. 1996. Т. 8(№2). С. 108-116.

28. Петров Н. Н. Преследование невидимого подвижного объекта // Дифференциальные уравнени. 1996. Т. 32(№8). С. 1563-1565, 1583.

29. Петров Н. Н., Старостина С. А. Минимальные графы с поисковым числом меньшим четырёх // Вестник СПбГУ. Сер. 1. 1989. № 3. С. 105-106.

30. Петров Н. Н., Старостина С. А. О некоторых задачах гарантированного поиска//Вестник СПбГУ. Сер. 1. 1994. № 1. С. 114-116.

31. Петров Н. Н., Тетерятникова М. А. О некоторых задачах поиска на графах с противодействием // Вестник СПбГУ. Сер. 1. 2004. № 3. С. 50-59.

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

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

34. Петров H. Н., Чуманова А. В. О некоторых проблемах поиска на графах с противодействием // Вестник СПбГУ. Сер. 1. 2003. № 4. С. 51-57.

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

36. Старостина С. А. Задачи преследования на графах при отсутствии информации об убегающем: Кандидатская диссертация / СПбГУ. 1993.

37. Фомин Ф. В. Задача поиска на деревьях // Вестник СПбГУ. Сер. 1. 1995. Т. 8(№2). С. 36-4\.

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

39. Фомин Ф. В. Задачи преследования и поиска на графах: Кандидатская диссертация / СПбГУ. 1996.

40. Фомин Ф. В., Петров H. Н. Дискретные программы поиска на графах // Вестник СПбГУ. Сер. 1. 1999. Т. 1(№1). С. 29-35.

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

42. Abramovskaya T. V., Petrov N. N. Graph searching games with a radius of capture // Game Theory and Management, Collected abstracts, Ed. by L. A. Petrosyan, N. A. Zenkevich. SPb.: Graduate School of Management, 2010. P. 12-13.

43. Abramovskaya T. V., Petrov N. N. Graph searching games with a radius of capture // Contributions to Game Theory and Management, Ed. by L. A. Pet-rosyan, N. A. Zenkevich. SPb.: Graduate School of Management, 2011. Vol. IV. P. 8-18.

44. Alpern S. The search game with mobile hider on the circle // Differential Games and Control Theory, In proceedings of Conference Board of the Mathematical Sciences, Kingston, Rhode Island, June 4-8, 1973. M. Dekker, 1974. P. 181-200.

45. Alpern S., Gal S. The theory of search games and rendezvous. Springer, 2003. Vol. 55 of International Series in Operations Research and Management Science.

46. Bienstock D., Seymour P. Monotonicity in graph searching // J. Algorithms. 1991. Vol. 12. P. 239-245.

47. Bodlaender H. L. A tourist guide through treewidth // Acta Cybernt. 1993. Vol. 11. P. 1-21.

48. Breisch R. An intuitive approach to speleotopology // Southwestern Cavers. 1972. Vol. VI. P. 72-78.

49. Breisch R. L. Lost in a Cave-applying graph theory to cave exploration. Huntsville, Alabama: National Speleological Society, 2012.

50. Chung F. R. K. Labelings of graphs // Selected Topics in Graph Theory. New York: Academic Press, 1988. Vol. III. P. 151-168.

51. Chung F. R. K., Seymour P. D. Graphs with small bandwidth and cutwidth // Discrete Math. 1989. Vol. 75. P. 113-119.

52. Ellis J. A., Sudborough I. H., Turner J. S. Graph separation and search number//Inform. and Comput. 1994. Vol. 113. P. 50-79.

53. Fomin F. V. Helicopter search problems, bandwidth and pathwidth // Discrete Appl. Math. 1998. Vol. 85. P. 59-70.

54. Fomin F. V. Note on a helicopter search problem on graphs // Discrete Appl. Math. 1999. Vol. 95. P. 241-249.

55. Fomin F. V., Golovach P. A., Petrov N. N. Search problems on 1-skeletons of regular polyhedrons // International Journal of Mathematics, Game Theory and Algebra. 1998. Vol. 7. P. 101-111.

56. Fomin F. V., Thilikos D. M. An annotated bibliography on guaranteed graph searching // Theoretical Computer Science. 2008. Vol. 399(№3). P. 236-245.

57. Gal S. Search Games. New York: Academic Press, 1980.

58. Garnaev A. Y. A remark on the Princess and Monster search game // International journal of Game Theory. 1991. Vol. 20. P. 269-276.

59. Hopcroft J., Paul W. J., Valiant L. On time versus space // Journal of the ACM. 1980. Vol. 24. P. 332-337.

60. Kirousis L. M., Papadimitriou C. H. Interval graphs and searching // Discrete Math. 1985. Vol. 55. P. 181-184.

61. Kirousis L. M., Papadimitriou C. H. Searching and pebbling // Theoret. Com-put. Sci. 1986. Vol. 47. P. 205—218.

62. Lai Y. L., Williams K. A survey of solved problems and applications on bandwidth, edgesum, and profile of graphs // Journal of Graph Theory. 1999. Vol. 31(2). P. 75-94.

63. LaPaugh A. Recontamination does not help to the search a graph // Journal of ACM. 1993. Vol. 40. P. 224-245.

64. Lipton R. J., Tarjan R. E. Applications of a planar separator theorem // SIAM J. Comput. 615-627. Vol. 3. P. 1980.

65. Makedon F. S., Papadimitriou C. H., Sudborough I. H. Topological bandwidth // SIAM J. Algebraic Discrete Methods. 1985. Vol. 6. P. 418—444.

66. Makedon F. S., Sudborough I. H. Min Cut is NP-complete for edge weighted trees // Theor. Computer Sci. 1988. Vol. 58. P. 209-229.

67. Megiddo N., Hakimi S. L., Garey M. R. et al. The complexity of searching a graph // J. Assoc. Comput. Mach. 1988. Vol. 35. P. 18-44.

68. Parsons T. D. Pursuit-evasion in a graph // Theory and Applications of Graphs. Y. Alavi and D. R. Lick, eds, Springer-Verlag. 1978. Vol. 642. P. 426^41.

69. Scheffler P. A linear algorithm for the pathwidth of trees // Topics in combinatorics and graph theory, In Collection. Heidelberg: Physica-Verlag, 1990. P. 613—620.

70. 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. 1992. Vol. 51. P. 287-291.

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

72. Sugihara H., Suzuki I. On pursuit-evasion problem related to motion coordination of mobile robots // System Sciences, In proceedings of 21st International Conference on, Kailua-Kona, Hawaii, 1987 / Ed. by G. M. Glasford, K. Jab-bour. 1988. P. 218-226.

73. Suzuki I., Yamashita M. Searching for a mobile intruder in a polygonal region // SIAM J. Comput. 1992. Vol. 21. P. 863-888.

74. Tosic R. Search number of the cartesian product of graphs // Zbornik Radova Prirodno-matematickog fakulteta Univerziteta u Novom Sadu, Serija za matem-atiku. 1987. Vol. 17(№1). P. 239-243.

75. Yannakakis M. A polyminal algorithm for the min-cut lineal arrangement of trees//J. of ACM. 1985. Vol. 32. P. 950-988.