Неявный граф
При изучении графовых алгоритмов неявное представление графа (или, проще говоря, неявный граф ) — это граф или ребра которого , вершины не представлены как явные объекты в памяти компьютера, а скорее определяются алгоритмически на основе некоторых других входных данных, например вычислимых функция .
Представительства соседей
[ редактировать ]Понятие неявного графа распространено в различных алгоритмах поиска , которые описываются в терминах графов. В этом контексте неявный граф может быть определен как набор правил для определения всех соседей для любой указанной вершины. [1] Этот тип неявного представления графа аналогичен списку смежности , поскольку он обеспечивает легкий доступ к соседям каждой вершины. Например, при поиске решения такой головоломки, как кубик Рубика , можно определить неявный граф, в котором каждая вершина представляет одно из возможных состояний куба, а каждое ребро представляет собой переход из одного состояния в другое. Генерировать соседей любой вершины несложно, перепробовав все возможные ходы головоломки и определив состояния, в которых достигается каждый из этих ходов; однако неявное представление необходимо, поскольку пространство состояний кубика Рубика слишком велико, чтобы алгоритм мог перечислить все его состояния. [2]
В теории сложности вычислений было определено несколько классов сложности в связи с неявными графами, определяемыми, как указано выше, правилом или алгоритмом составления списка соседей вершины. Например, PPA — это класс задач, в которых в качестве входных данных дается неориентированный неявный граф (в котором вершины представляют собой n -битные двоичные строки с алгоритмом полиномиального времени для составления списка соседей любой вершины) и вершина нечетной степени. в графе и должен найти вторую вершину нечетной степени. По лемме о согласовании такая вершина существует; найти его — проблема в NP , но проблемы, которые можно определить таким образом, не обязательно могут быть NP-полными , поскольку неизвестно, будет ли PPA = NP. PPAD — аналогичный класс, определенный на неявно ориентированных графах , который привлек внимание в алгоритмической теории игр, поскольку содержит задачу вычисления равновесия по Нэшу . [3] Задача проверки достижимости одной вершины до другой в неявном графе может также использоваться для характеристики ограниченных в пространстве недетерминированных классов сложности, включая NL (класс задач, которые могут характеризоваться достижимостью в неявных ориентированных графах, вершины которых равны O(log n ) -битовые строки), SL (аналогичный класс для неориентированных графов) и PSPACE (класс задач, которые можно охарактеризовать достижимостью в неявных графах с битовыми строками полиномиальной длины). В этом контексте теории сложности вершины неявного графа могут представлять состояния недетерминированной машины Тьюринга , а ребра могут представлять возможные переходы состояний, но неявные графы также могут использоваться для представления многих других типов комбинаторных структур. [4] PLS , еще один класс сложности, отражает сложность поиска локальных оптимумов в неявном графе. [5]
Модели неявных графов также использовались как форма релятивизации для доказательства более сильного разделения между классами сложности, чем известные разделения для нерелятивизированных моделей. Например, Чайлдс и др. использовали представления окрестностей неявных графов, чтобы определить задачу обхода графа, которую можно решить за полиномиальное время на квантовом компьютере , но для решения которой на любом классическом компьютере требуется экспоненциальное время. [6]
Схемы маркировки смежности
[ редактировать ]В контексте эффективных представлений графов Дж. Мюллер определил локальную структуру или схему разметки смежности для графа G в заданном семействе графов F как присвоение O (log n ) -битного идентификатора каждой вершине G , вместе с алгоритмом (который может зависеть от F, но не зависит от отдельного графа G являются ли они конечными точками ребра в G. ), который принимает в качестве входных данных два идентификатора вершин и определяет , То есть этот тип неявного представления аналогичен матрице смежности : проверить, являются ли две вершины соседними, несложно, но для поиска соседей любой вершины может потребоваться циклический просмотр всех вершин и проверка того, какие из них являются соседями. [7]
Семейства графов со схемами разметки смежности включают:
- Графы ограниченных степеней
- Если каждая вершина в G имеет не более d соседей, можно пронумеровать вершины G от 1 до n и позволить идентификатору вершины быть ( d + 1) -кортеж ее собственного номера и номеров ее соседей. Две вершины являются смежными, если первые числа их идентификаторов появляются позже в идентификаторе другой вершины. В более общем смысле, тот же подход можно использовать для обеспечения неявного представления графов с ограниченной древесностью или ограниченной вырожденностью , включая планарные графы и графы в любом минорно-замкнутом семействе графов . [8] [9]
- Графики пересечений
- Граф интервалов — это граф пересечений набора отрезков реальной линии . Может быть задана схема разметки смежности, в которой точки, являющиеся концами отрезков, пронумерованы от 1 до 2 n , а каждая вершина графа представлена номерами двух концов соответствующего интервала. С помощью этого представления можно проверить, являются ли две вершины смежными, сравнивая числа, которые их представляют, и проверяя, что эти числа определяют перекрывающиеся интервалы. Тот же подход работает для других геометрических графов пересечений, включая графы ограниченной коробчатости и круговые графы , а также подсемейства этих семейств, такие как дистанционно-наследственные графы и кографы . [8] [10] Однако представление геометрического графа пересечений не всегда подразумевает существование схемы маркировки смежности, поскольку для определения каждого геометрического объекта может потребоваться больше, чем логарифмическое количество битов. Например, представление графа в виде единичного дискового графа может потребовать экспоненциально много битов для координат центров дисков. [11]
- Графики малой размерности сравнимости
- Граф сравнимости имеет частично упорядоченного набора вершину для каждого элемента набора и ребро между двумя элементами набора, связанными частичным порядком. Порядковая размерность частичного порядка — это минимальное количество линейных порядков, пересечение которых является данным частичным порядком. Если частичный порядок имеет ограниченную размерность порядка, то схема маркировки смежности для вершин в его графе сравнимости может быть определена путем маркировки каждой вершины ее положением в каждом из определяющих линейных порядков и определения того, что две вершины являются смежными, если каждая соответствующая пара чисел в их метках имеют то же отношение порядка, что и каждая другая пара. В частности, это позволяет использовать схему маркировки смежности для хордальных графов сравнимости , которые происходят из частичных порядков размерности не более четырех. [12] [13]
Гипотеза о неявном графе
[ редактировать ]Не все семейства графов имеют локальные структуры. Для некоторых семейств простой аргумент подсчета доказывает, что схемы разметки смежности не существуют: только O ( n log n ) битов могут использоваться для представления всего графа, поэтому представление этого типа может существовать только тогда, когда количество n -вершин графов в данном семействе F не превосходит 2 О ( нлогн n) . Семейства графов, которые имеют большее количество графов, чем это, например, двудольные графы или графы без треугольников , не имеют схем маркировки смежности. [8] [10] Однако даже семейства графов, в которых количество графов в семействе невелико, могут не иметь схемы разметки смежности; например, семейство графов с меньшим количеством ребер, чем вершин, имеет 2 О ( нлогн n) n- вершинные графы, но не имеют схемы маркировки смежности, поскольку можно преобразовать любой данный граф в более крупный граф в этом семействе, добавив новую изолированную вершину для каждого ребра, не меняя его маркировки. [7] [10] Каннан и др. спросили, есть ли характеристика запрещенного подграфа и не более 2 О ( нлогн n) n- вершинных графов вместе достаточно, чтобы гарантировать существование схемы маркировки смежности; этот вопрос, который Спинрад вновь сформулировал как гипотезу, остается открытым. [8] [10] К числу семейств графов, удовлетворяющих условиям гипотезы и для которых не известна схема разметки смежности, относятся семейство дисковых графов и графов пересечения отрезков.
Схемы разметки и индуцированные универсальные графы
[ редактировать ]Если семейство графов F имеет схему разметки смежности, то графы с n -вершинами в F могут быть представлены как индуцированные подграфы общего индуцированного универсального графа полиномиального размера, состоящего из всех возможных идентификаторов вершин. И наоборот, если можно построить индуцированный универсальный граф этого типа, то тождества его вершин можно использовать в качестве меток в схеме разметки смежности. [8] Для такого применения неявных представлений графов важно, чтобы метки использовали как можно меньше битов, поскольку количество битов в метках напрямую преобразуется в количество вершин в индуцированном универсальном графе. Альструп и Рауэ показали, что любое дерево имеет схему разметки смежности с log 2 n + O ( log * n ) битов на метку, из чего следует, что любой граф с древесностью k имеет схему с k log 2 n + O ( log * n ) бит на метку и универсальный граф с n к 2 О ( лог * п ) вершины. В частности, плоские графы имеют древесность не более трех, поэтому они представляют собой универсальные графы с почти кубическим числом вершин. [14] Эта граница была улучшена Гавуалем и Лабурелем, которые показали, что плоские графы и семейства малозамкнутых графов имеют схему маркировки с 2 log 2 n + O (log log n ) битами на метку, и что графы ограниченной древовидной ширины имеют схему маркировки с log 2 n + O (log log n ) бит на метку. [15] Оценка для планарных графов была снова улучшена Бонами, Гавуалом и Пиличуком, которые показали, что планарные графы имеют схему разметки с (4/3+o(1))log 2 n битов на метку. [16] Наконец, Дуймович и др. показали, что планарные графы имеют схему разметки с (1+o(1))log 2 n битами на метку, что дает универсальный граф с n 1+о(1) вершины. [17]
Уклончивость
[ редактировать ]Гипотеза Андераа -Карпа-Розенберга касается неявных графов, заданных как набор помеченных вершин с правилом черного ящика для определения того, являются ли какие-либо две вершины смежными. Это определение отличается от схемы разметки смежности тем, что правило может быть специфичным для конкретного графа, а не быть общим правилом, применимым ко всем графам в семействе. Из-за этого различия каждый граф имеет неявное представление. Например, правилом может быть поиск пары вершин в отдельной матрице смежности. Однако алгоритм, которому на входе предоставляется неявный граф этого типа, должен работать с ним только посредством неявного теста смежности, без ссылки на то, как этот тест реализован.
— Свойство графа это вопрос о том, принадлежит ли граф данному семейству графов; ответ должен оставаться инвариантным при любых перемаркировках вершин. В этом контексте вопрос, который необходимо определить, заключается в том, сколько пар вершин должно быть проверено на смежность, в худшем случае, прежде чем интересующее свойство может быть определено как истинное или ложное для данного неявного графа. Ривест и Вийемен доказали, что любой детерминированный алгоритм для любого нетривиального свойства графа должен проверять квадратичное число пар вершин. [18] Полная гипотеза Андераа-Карпа-Розенберга состоит в том, что любой детерминированный алгоритм для свойства монотонного графа (который остается верным, если к графу с этим свойством добавляется больше ребер) должен в некоторых случаях проверять каждую возможную пару вершин. Несколько случаев гипотезы оказались верными, например, известно, что она верна для графов с простым числом вершин. [19] — но полная гипотеза остается открытой. Также изучались варианты задачи для рандомизированных алгоритмов и квантовых алгоритмов.
Бендер и Рон показали, что в той же модели, которая использовалась для гипотезы об уклончивости, можно только за постоянное время отличить ориентированные ациклические графы от графов, которые очень далеки от ацикличности. Напротив, такое быстрое время невозможно в моделях неявных графов на основе окрестностей. [20]
См. также
[ редактировать ]- Группа черного ящика , неявная модель теоретико-групповых алгоритмов.
- Matroid oracle , неявная модель для матроида алгоритмов
Ссылки
[ редактировать ]- ^ Корф, Ричард Э. (2008), «Неявный поиск по диску в линейном времени», Журнал ACM , 55 (6), статья 26, 40 стр., doi : 10.1145/1455248.1455250 , MR 2477486 , S2CID 13969607 .
- ^ Корф, Ричард Э. (2008), «Минимизация дискового ввода-вывода при двухбитном поиске в ширину» (PDF) , Proc. 23-я конференция AAAI. по искусственному интеллекту , стр. 317–324,
Стандартный кубик Рубика 3 × 3 × 3 содержит 4,3252 × 10. 19 штатов, и слишком велик для исчерпывающего поиска.
- ^ Пападимитриу, Христос (1994), «О сложности аргумента четности и других неэффективных доказательствах существования» (PDF) , Journal of Computer and System Sciences , 48 (3): 498–532, doi : 10.1016/S0022-0000( 05)80063-7 , заархивировано из оригинала (PDF) 4 марта 2016 г. , получено 12 июля 2011 г.
- ^ Иммерман, Нил (1999), «Упражнение 3.7 (Все является графом)» , «Описательная сложность » , Тексты для выпускников по информатике, Springer-Verlag, стр. 48, ISBN 978-0-387-98600-5 .
- ^ Яннакакис, Михалис (2009), «Равновесия, фиксированные точки и классы сложности», Computer Science Review , 3 (2): 71–85, arXiv : 0802.2831 , doi : 10.1016/j.cosrev.2009.03.004 .
- ^ Чайлдс, Эндрю М.; Клив, Ричард; Деотто, Энрико; Фархи, Эдвард; Гутманн, Сэм; Спилман, Дэниел А. (2003), «Экспоненциальное алгоритмическое ускорение за счет квантового блуждания», Труды тридцать пятого ежегодного симпозиума ACM по теории вычислений , Нью-Йорк: ACM, стр. 59–68, arXiv : quant-ph/ 0209131 , doi : 10.1145/780542.780552 , MR 2121062 , S2CID 308884 .
- ^ Jump up to: а б Мюллер, Джон Гарольд (1988), Локальная структура в классах графов , доктор философии. диссертация, Технологический институт Джорджии .
- ^ Jump up to: а б с д и Каннан, Сампат; Наор, Мони ; Рудич, Стивен (1992), «Неявное представление графов», SIAM Journal on Discrete Mathematics , 5 (4): 596–603, doi : 10.1137/0405049 , MR 1186827 .
- ^ Хробак, Марек; Эппштейн, Дэвид (1991), «Плоские ориентации с низкой исходящей степенью и уплотнением матриц смежности» (PDF) , Theoretical Computer Science , 86 (2): 243–266, doi : 10.1016/0304-3975(91)90020- 3 .
- ^ Jump up to: а б с д Спинрад, Джереми П. (2003), «2. Неявное представление графа», Эффективные представления графов , Американская математическая общество, стр. 17–30, ISBN 0-8218-2815-0 .
- ^ Канг, Росс Дж.; Мюллер, Тобиас (2011), Представления графиков в сфере и скалярном произведении (PDF) , заархивировано из оригинала (PDF) 16 марта 2012 г. , получено 12 июля 2011 г.
- ^ Ма, Цзе Хэн; Спинрад, Джереми П. (1991), «Безцикловые частичные порядки и хордальные графы сравнимости», Order , 8 (1): 49–61, doi : 10.1007/BF00385814 , MR 1129614 , S2CID 120479154 .
- ^ Кертис, Эндрю Р.; Изурьета, Клементе; Джорис, Бенсон; Лундберг, Скотт; МакКоннелл, Росс М. (2010), «Неявное представление хордальных графов сравнимости в линейном времени», Discrete Applied Mathematics , 158 (8): 869–875, doi : 10.1016/j.dam.2010.01.005 , MR 2602811 .
- ^ Альструп, Стивен; Рауэ, Тайс (2002), «Малые индуцированные универсальные графы и компактные неявные представления графов» (PDF) , Труды 43-го ежегодного симпозиума IEEE по основам информатики , стр. 53–62, doi : 10.1109/SFCS.2002.1181882 , S2CID 1820524 , заархивировано из оригинала (PDF) 27 сентября 2011 г. , получено 13 июля 2011 г.
- ^ Арно, Лабурель; Гавуай, Сирил (2007), «Краткое неявное представление плоских графов и графов с ограниченной древовидной шириной» (PDF) , Труды 15-го ежегодного Европейского симпозиума по алгоритмам , стр. 582–593, doi : 10.1007/978-3-540-75520 -3_52 .
- ^ Бонами, Марта; Гавуа, Сирил; Пилипчук, Михал (2020), «Краткие схемы разметки для планарных графов», Труды симпозиума ACM-SIAM 2020 по дискретным алгоритмам , стр. 446–462, arXiv : 1908.03341 , doi : 10.1007/978-3-540-75520- 3_52 .
- ^ Дуймович, Вида ; Эспере, Луи; Жоре, Гвенаэль; Гавуа, Сирил; Мичек, Петр; Морин, Пэт (2020), «Разметка смежности для планарных графов (и не только)», 61-й ежегодный симпозиум IEEE по основам информатики , стр. 577–588, arXiv : 2003.04280 , doi : 10.1007/978-3-540-75520 -3_52 .
- ^ Ривест, Рональд Л .; Виймен, Жан (1975), «Обобщение и доказательство гипотезы Андераа-Розенберга», Proc. 7-й симпозиум ACM по теории вычислений , Альбукерке, Нью-Мексико, США, стр. 6–11, CiteSeerX 10.1.1.309.7236 , doi : 10.1145/800116.803747 , S2CID 16220596
{{citation}}: CS1 maint: отсутствует местоположение издателя ( ссылка ) . - ^ Кан, Джефф; Сакс, Майкл ; Стертевант, Дин (1983), «Топологический подход к уклончивости», Симпозиум по основам информатики , Лос-Аламитос, Калифорния, США: Компьютерное общество IEEE, стр. 31–33, номер документа : 10.1109/SFCS.1983.4 .
- ^ Бендер, Майкл А.; Рон, Дана (2000), «Тестирование ацикличности ориентированных графов в сублинейное время», Автоматы, языки и программирование (Женева, 2000) , Конспекты лекций по вычислительной технике. наук., вып. 1853, Берлин: Springer, стр. 809–820, номер документа : 10.1007/3-540-45022-X_68 , MR 1795937 .