Неявный граф - Implicit graph

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

Представления соседства

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

В теории сложности вычислений несколько классов сложности были определены в связи с неявными графами, определенными, как указано выше, правилом или алгоритмом для перечисления соседей вершины. Например, PPA - это класс задач, в которых на входе задается неориентированный неявный граф (в котором вершины представляют собой n- битные двоичные строки с полиномиальным временным алгоритмом для перечисления соседей любой вершины) и вершиной нечетной степени в графе, и должен найти вторую вершину нечетной степени. По лемме о рукопожатии такая вершина существует; найти один - проблема в NP , но проблемы, которые могут быть определены таким образом, не обязательно могут быть NP-полными , поскольку неизвестно, является ли PPA = NP. PPAD - аналогичный класс, определенный на неявных ориентированных графах , который привлек внимание в алгоритмической теории игр, поскольку он содержит проблему вычисления равновесия по Нэшу . Проблема проверки достижимости одной вершины к другой в неявном графе также может быть использована для характеристики ограниченных пространством классов недетерминированной сложности, включая NL (класс проблем, который может характеризоваться достижимостью в неявных ориентированных графах, вершины которых равны O (log n ) -битовые цепочки битов), SL (аналогичный класс для неориентированных графов) и PSPACE (класс задач, которые могут характеризоваться достижимостью в неявных графах с битовыми цепочками полиномиальной длины). В этом теоретико-сложном контексте вершины неявного графа могут представлять состояния недетерминированной машины Тьюринга , а ребра могут представлять возможные переходы состояний, но неявные графы также могут использоваться для представления многих других типов комбинаторной структуры. PLS , еще один класс сложности, отражает сложность поиска локальных оптимумов в неявном графе.

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

Схемы маркировки смежности

В контексте эффективных представлений графов Дж. Х. Мюллер определил локальную структуру или схему разметки смежности для графа G в данном семействе графов F как присвоение O (log n ) -битового идентификатора каждой вершине G , вместе с алгоритмом (что может зависеть от F , но не зависит от индивидуального графа G ) , который принимает в качестве входных данных два идентификаторов вершин и определяет , являются ли они концами ребра в G . То есть этот тип неявного представления аналогичен матрице смежности : просто проверить, являются ли две вершины смежными, но поиск соседей любой вершины может включать в себя перебор всех вершин и проверку того, какие из них являются соседями.

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

Графы ограниченной степени

Если каждая вершина в G имеет не более d соседей, можно пронумеровать вершины G от 1 до n и позволить идентификатору вершины быть ( d + 1) -набором ее собственного номера и номеров ее соседей. Две вершины являются смежными, если первые числа в их идентификаторах появляются позже в идентификаторе другой вершины. В более общем смысле, тот же подход может использоваться для обеспечения неявного представления для графов с ограниченной древовидностью или ограниченным вырождением , включая плоские графы и графы в любом семействе минорно-замкнутых графов .

Графики пересечений

Граф интервалов является графом пересечений из множества отрезков , в реальной линии . Может быть дана схема маркировки смежности, в которой точки, которые являются конечными точками отрезков линии, пронумерованы от 1 до 2 n, и каждая вершина графа представлена ​​номерами двух конечных точек соответствующего ей интервала. С помощью этого представления можно проверить, являются ли две вершины смежными, сравнив числа, которые их представляют, и убедившись, что эти числа определяют перекрывающиеся интервалы. Тот же подход работает для других геометрических графов пересечений, включая графы ограниченной прямоугольности и круговые графы , а также подсемейства этих семейств, таких как дистанционно-наследственные графы и кографы . Однако представление геометрического графа пересечений не всегда подразумевает наличие схемы маркировки смежности, поскольку для определения каждого геометрического объекта может потребоваться больше логарифмического числа битов. Например, представление графа в виде графа единичного диска может потребовать экспоненциально много битов для координат центров дисков.

Графики сопоставимости малой размерности

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

Гипотеза неявного графа

Не все семейства графов имеют локальную структуру. Для некоторых семейств простой аргумент подсчета доказывает, что схемы маркировки смежности не существуют: для представления всего графа можно использовать только O ( n log n ) бит, поэтому представление этого типа может существовать только тогда, когда количество n -вершин графов в данном семействе F не превосходит 2 ^{O ( n log n )} . Семейства графов, которые имеют большее количество графов, чем это, например, двудольные графы или графы без треугольников , не имеют схем разметки смежности. Однако даже семейства графов, в которых количество графов в семействе невелико, могут не иметь схемы разметки смежности; например, семейство графов с меньшим количеством ребер, чем вершин, имеет 2 ^{O ( n log n )} n -вершинных графов, но не имеет схемы разметки смежности, потому что можно преобразовать любой данный граф в больший граф в этом семействе, добавив новую изолированную вершину для каждого ребра без изменения ее разметки. Каннан и др. спросили, достаточно ли вместе иметь характеристику запрещенного подграфа и не более 2 ^{O ( n log n )} n -вершинных графов, чтобы гарантировать существование схемы разметки смежности; этот вопрос, который Спинрад сформулировал как гипотезу, остается открытым. Среди семейств графов, которые удовлетворяют условиям гипотезы и для которых нет известной схемы разметки смежности, есть семейство дисковых графов и графов пересечений отрезков прямой.

Схемы разметки и индуцированные универсальные графы

Если семейство графов F имеет схему разметки смежности, то графы с n вершинами в F могут быть представлены как индуцированные подграфы общего индуцированного универсального графа полиномиального размера, графа, состоящего из всех возможных идентификаторов вершин. И наоборот, если индуцированный универсальный граф этого типа может быть построен, то идентичности его вершин можно использовать в качестве меток в схеме разметки смежности. Для этого применения неявных представлений графа важно, чтобы метки использовали как можно меньше битов, потому что количество битов в метках транслируется непосредственно в количество вершин в индуцированном универсальном графе. Альструп и Раухе показали, что любое дерево имеет схему разметки смежности с log ₂ n + O ( log * n ) бит на метку, из чего следует, что любой граф с произвольностью k имеет схему с k log ₂ n + O ( log * n ) бит на метку и универсальный граф с n ^k 2 ^{O ( log * n )} вершинами. В частности, планарные графы имеют не более трех ветвей, поэтому у них есть универсальные графы с почти кубическим числом вершин. Эта граница была улучшена Гавуилем и Лабурелем, которые показали, что планарные графы и семейства второстепенных замкнутых графов имеют схему маркировки с 2 log ₂ n + O (log log n ) бит на метку, и что графы с ограниченной шириной дерева имеют схему маркировки с log ₂ n + O (log log n ) бит на метку. Граница для плоских графов была снова улучшена Бонами, Гавуилем и Пиличук, которые показали, что планарные графы имеют схему разметки с (4/3 + o (1)) log ₂ n битов на метку. Наконец, Дуймович и др. Показали, что планарные графы имеют схему разметки с (1 + o (1)) log ₂ n битов на метку, что дает универсальный граф с n ^{1 + o (1)} вершинами.

Уклончивость

Гипотеза Андераа – Карпа – Розенберга касается неявных графов, заданных как набор помеченных вершин, с правилом черного ящика для определения, являются ли любые две вершины смежными. Это определение отличается от схемы маркировки смежности тем, что правило может быть специфическим для конкретного графа, а не быть общим правилом, применимым ко всем графам в семействе. Из-за этой разницы каждый граф имеет неявное представление. Например, правилом может быть поиск пары вершин в отдельной матрице смежности. Однако алгоритм, который предоставляется в качестве входных данных для неявного графа этого типа, должен работать с ним только через тест неявной смежности, без ссылки на то, как этот тест реализован.

Свойство графа является вопрос о том, принадлежит ли граф к данному семейству графов; ответ должен оставаться неизменным при любом изменении названия вершин. В этом контексте необходимо определить вопрос, сколько пар вершин необходимо проверить на смежность в худшем случае, прежде чем интересующее свойство может быть определено как истинное или ложное для данного неявного графа. Ривест и Вуйлемин доказали, что любой детерминированный алгоритм для любого нетривиального свойства графа должен проверять квадратичное число пар вершин. Полная гипотеза Андераа – Карпа – Розенберга состоит в том, что любой детерминированный алгоритм для свойства монотонного графа (который остается верным, если к графу с этим свойством добавляется больше ребер) должен в некоторых случаях проверять каждую возможную пару вершин. Было доказано, что несколько случаев гипотезы верны - например, известно, что она верна для графов с простым числом вершин, - но полная гипотеза остается открытой. Также были изучены варианты задачи для рандомизированных алгоритмов и квантовых алгоритмов.

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

Смотрите также

• Группа черного ящика , неявная модель для теоретико-групповых алгоритмов
• Matroid oracle , неявная модель для алгоритмов матроидов

использованная литература