WikiDer > Неявный граф

Implicit graph

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

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

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

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

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

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

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

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

Графы ограниченной степени
Если каждая вершина в грамм имеет самое большее d соседей, можно пронумеровать вершины грамм от 1 до п и пусть идентификатором вершины будет (d + 1)-набор собственного номера и номеров своих соседей. Две вершины являются смежными, если первые числа в их идентификаторах появляются позже в идентификаторе другой вершины. В более общем смысле, тот же подход может использоваться для неявного представления графов с ограниченными родословие или ограниченный вырождение, в том числе планарные графы и графики в любом семейство минорных замкнутых графов.[8][9]
Графики пересечений
An интервальный график это граф пересечений набора отрезки линии в реальная линия. Может быть задана схема маркировки смежности, в которой точки, которые являются конечными точками отрезков линии, пронумерованы от 1 до 2.п и каждая вершина графа представлена ​​номерами двух конечных точек соответствующего ей интервала. С помощью этого представления можно проверить, являются ли две вершины смежными, сравнив числа, которые их представляют, и убедившись, что эти числа определяют перекрывающиеся интервалы. Тот же подход работает для других геометрических графов пересечений, включая графы ограниченных коробочка и круговые графики, и подсемейства этих семейств, такие как дистанционно-наследственные графы и кографы.[8][10] Однако представление графа геометрических пересечений не всегда подразумевает наличие схемы маркировки смежности, поскольку для определения каждого геометрического объекта может потребоваться больше логарифмического числа битов. Например, представление графа как граф единичного диска может потребоваться экспоненциально много бит для координат центров диска.[11]
Графики сопоставимости малой размерности
В график сопоставимости для частично заказанный набор имеет вершину для каждого элемента набора и край между двумя элементами набора, которые связаны частичным порядком. В размер заказа частичного порядка - это минимальное количество линейных порядков, пересечение которых является данным частичным порядком. Если частичный порядок имеет размерность ограниченного порядка, то схема маркировки смежности для вершин в его графе сопоставимости может быть определена путем маркировки каждой вершины ее положением в каждом из определяющих линейных порядков и определения того, что две вершины являются смежными, если каждая соответствующая пара чисел в их метках имеет такое же отношение порядка, как и каждая другая пара. В частности, это позволяет использовать схему маркировки смежности для хордовый графики сопоставимости, которые происходят из частичных порядков размерности не более четырех.[12][13]

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

Вопрос, Web Fundamentals.svgНерешенная проблема в математике:
Каждый медленно растущий наследственное семейство графов иметь неявное представление?
(больше нерешенных задач по математике)

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

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

Если семейство графов F имеет схему маркировки смежности, то п-вершинные графы в F может быть представлен как индуцированные подграфы общего индуцированного универсальный граф полиномиального размера, граф, состоящий из всех возможных идентификаторов вершин. И наоборот, если индуцированный универсальный граф этого типа может быть построен, то тождества его вершин могут использоваться как метки в схеме разметки смежности.[8] Для этого применения неявных представлений графа важно, чтобы метки использовали как можно меньше битов, потому что количество бит в метках транслируется непосредственно в количество вершин в индуцированном универсальном графе. Альструп и Раухе показали, что любое дерево имеет схему разметки смежности с бревно2 п + О(бревно* п) бит на метку, из чего следует, что любой граф с родословие k имеет схему с k бревно2 п + О(бревно* п) бит на метку и универсальный график с пk2О(бревно* п) вершины. В частности, планарные графы имеют не более трех ветвей, поэтому у них есть универсальные графы с почти кубическим числом вершин.[14]Эта оценка была улучшена Гавуилем и Лабурелем, которые показали, что плоские графы и семейства минорно-замкнутых графов имеют схему разметки с 2 журнала2 п + О(журнал журнала п) бит на метку, и что графы ограниченного ширина дерева иметь схему маркировки с бревно2 п + О(журнал журнала п) бит на этикетку.[15]

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

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

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

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

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

Рекомендации

  1. ^ Корф, Ричард Э. (2008), "Неявный поиск графа на основе диска с линейным временем", Журнал ACM, 55 (6), статья 26, 40 пп, Дои:10.1145/1455248.1455250, МИСТЕР 2477486.
  2. ^ Корф, Ричард Э. (2008), «Минимизация дискового ввода-вывода при двухбитном поиске в ширину», Proc. 23-я конференция AAAI Conf. по искусственному интеллекту (PDF), стр. 317–324, Стандартный кубик Рубика 3 × 3 × 3 содержит 4,3252 × 1019 состояний, и слишком велик для полного поиска.
  3. ^ Пападимитриу, Христос (1994), «О сложности аргумента о четности и других неэффективных доказательствах существования» (PDF), Журнал компьютерных и системных наук, 48 (3): 498–532, Дои:10.1016 / S0022-0000 (05) 80063-7, заархивировано из оригинал (PDF) на 2016-03-04, получено 2011-07-12
  4. ^ Иммерман, Нил (1999), «Упражнение 3.7 (Все является графиком)», Описательная сложность, Тексты для выпускников по информатике, Springer-Verlag, стр. 48, ISBN 978-0-387-98600-5.
  5. ^ Яннакакис, Михалис (2009), «Равновесия, неподвижные точки и классы сложности», Обзор компьютерных наук, 3 (2): 71–85, arXiv:0802.2831, Дои:10.1016 / j.cosrev.2009.03.004.
  6. ^ Чайлдс, Эндрю М .; Клив, Ричард; Деотто, Энрико; Фархи, Эдвард; Гутманн, Сэм; Спилман, Дэниел А. (2003), «Экспоненциальное алгоритмическое ускорение за счет квантового блуждания», Труды тридцать пятого ежегодного симпозиума ACM по теории вычислений, Нью-Йорк: ACM, стр. 59–68, arXiv:Quant-ph / 0209131, Дои:10.1145/780542.780552, МИСТЕР 2121062.
  7. ^ а б Мюллер, Джон Гарольд (1988), Локальная структура в классах графов, Кандидат наук. диссертация, Технологический институт Джорджии.
  8. ^ а б c d е Каннан, Сампатх; Наор, Мони; Рудич, Стивен (1992), «Неявное представление графов», Журнал SIAM по дискретной математике, 5 (4): 596–603, Дои:10.1137/0405049, МИСТЕР 1186827.
  9. ^ Хробак, Марек; Эппштейн, Дэвид (1991), «Планарные ориентации с низкой степенью выхода и уплотнением матриц смежности» (PDF), Теоретическая информатика, 86 (2): 243–266, Дои:10.1016/0304-3975(91)90020-3.
  10. ^ а б c d Спинрад, Джереми П. (2003), "2. Неявное представление графа", Эффективные графические представления, стр. 17–30, ISBN 0-8218-2815-0.
  11. ^ Канг, Росс Дж .; Мюллер, Тобиас (2011), Представления графов сферой и скалярным произведением (PDF), заархивировано из оригинал (PDF) на 2012-03-16, получено 2011-07-12.
  12. ^ Ма, Цзе Хэн; Спинрад, Джереми П. (1991), "Частичные порядки без цикла и графики хордовой сопоставимости", Заказ, 8 (1): 49–61, Дои:10.1007 / BF00385814, МИСТЕР 1129614.
  13. ^ Кертис, Эндрю Р .; Изуриета, Клементе; Джерис, Бенсон; Лундберг, Скотт; МакКоннелл, Росс М. (2010), "Неявное представление графиков хордовой сопоставимости за линейное время", Дискретная прикладная математика, 158 (8): 869–875, Дои:10.1016 / j.dam.2010.01.005, МИСТЕР 2602811.
  14. ^ Альструп, Стивен; Раухе, Тайс (2002), «Малые индуцированно-универсальные графы и компактные неявные представления графов» (PDF), Материалы 43-го ежегодного симпозиума IEEE по основам компьютерных наук: 53–62, Дои:10.1109 / SFCS.2002.1181882, заархивировано из оригинал (PDF) на 2011-09-27, получено 2011-07-13.
  15. ^ Арно, Лабурель; Гавой, Сирил (2007), «Укороченное неявное представление плоских графов и графов с ограниченной шириной дерева» (PDF), Материалы 15-го ежегодного европейского симпозиума по алгоритмам: 582–593, Дои:10.1007/978-3-540-75520-3_52.
  16. ^ Ривест, Рональд Л.; Вюймен, Жан (1975), "Обобщение и доказательство гипотезы Аандераа-Розенберга", Proc. 7-й симпозиум ACM по теории вычислений, Альбукерке, Нью-Мексико, США, стр. 6–11, Дои:10.1145/800116.803747.
  17. ^ Кан, Джефф; Сакс, Михаил; Стертевант, Дин (1983), "Топологический подход к уклончивости", Симпозиум по основам информатики, Лос-Аламитос, Калифорния, США: Компьютерное общество IEEE, стр. 31–33, Дои:10.1109 / SFCS.1983.4.
  18. ^ Бендер, Майкл А .; Рон, Дана (2000), «Проверка ацикличности ориентированных графов в сублинейном времени», Автоматы, языки и программирование (Женева, 2000 г.), Конспект лекций по вычисл. Наук, 1853, Берлин: Springer, стр. 809–820, Дои:10.1007 / 3-540-45022-X_68, МИСТЕР 1795937.