WikiDer > График карты

Map graph
График карты (вверху), график коктейльной вечеринки K2,2,2,2, определяемый угловой смежностью восьми областей на плоскости (внизу слева), или как полуквадрат плоского двудольного графа (внизу справа, график ромбический додекаэдр)
В Четыре угла США. Несмотря на то, что эти четыре состояния встречаются в точке, а не разделяют границу ненулевой длины, они образуют смежные вершины в соответствующем графе карты.
В граф короля, карта-график квадратов шахматной доски. Шахматный король может перемещаться между любыми двумя соседними вершинами этого графа.

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

Комбинаторное представление

Графы карт могут быть комбинаторно представлены как «полуквадраты плоских двудольных графов». То есть пусть грамм = (U,V,E) быть плоским двудольный граф, с двудольным (U,V). В квадрат из грамм - другой граф на том же множестве вершин, в котором две вершины смежны в квадрате, когда они находятся на расстоянии не более двух шагов в грамм. Полуквадрат или двудольная половина это индуцированный подграф одной стороны двудольного (скажем, V) в квадратном графе: множество его вершин V и у него есть ребро между каждыми двумя вершинами в V это два шага друг от друга в грамм. Полуквадрат - это карта-граф. Его можно представить геометрически, найдя планарное вложение из грамм, и расширяя каждую вершину V и его смежные края в звездообразную область, так что эти области соприкасаются в вершинах U. И наоборот, каждый граф карты таким образом может быть представлен как полуквадрат.[1]

Вычислительная сложность

В 1998 г. Миккель Торуп утверждал, что графы карт можно распознать в полиномиальное время.[2] Однако высокая экспонента алгоритма, который он набросал, делает его непрактичным, и Торруп не опубликовал подробностей своего метода и его доказательства.[3]

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

Вариации и связанные концепции

А k-map graph - это граф карты, полученный из набора регионов, в которых не более k регионы встречаются в любой точке. Эквивалентно, это полуквадрат плоского двудольного графа, в котором множество вершин U (сторона двудольного разбиения, не использованная для создания полуквадрата) имеет максимум степень k. Граф с 3 отображениями - это планарный граф, и каждый планарный граф может быть представлен как граф с 3 картами. Каждый граф с четырьмя отображениями является 1-планарный граф, граф, который может быть нарисован не более чем с одним пересечением на ребро, и каждый оптимальный 1-планарный граф (граф, образованный из плоского четырехугольника путем добавления двух пересекающихся диагоналей к каждой четырехугольной грани) является графом с 4 картами. Однако некоторые другие 1-плоские графы не являются графами карт, потому что (в отличие от графов карт) они включают пересекающиеся ребра, которые не являются частью полного подграфа с четырьмя вершинами.[1]

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

  1. ^ а б c Чен, Чжи-Чжун; Гриньи, Микеланджело; Пападимитриу, Христос Х. (2002), «Карты-графики», Журнал ACM, 49 (2): 127–138, arXiv:cs / 9910013, Дои:10.1145/506147.506148, МИСТЕР 2147819.
  2. ^ Торуп, Миккель (1998), "Отображение графов за полиномиальное время", Материалы 39-го ежегодного симпозиума по основам информатики (FOCS 1998), стр. 396–405, Дои:10.1109 / SFCS.1998.743490, ISBN 978-0-8186-9172-0.
  3. ^ Бранденбург, Франц Дж. (Август 2018 г.), «Характеристика и распознавание четырехкарточных графов», Алгоритмика, Дои:10.1007 / s00453-018-0510-х
  4. ^ Чен, Чжи-Чжун (2001), "Алгоритмы приближения для независимых множеств в графах карт", Журнал алгоритмов, 41 (1): 20–40, Дои:10.1006 / jagm.2001.1178, МИСТЕР 1855346.
  5. ^ Демейн, Эрик Д.; Фомин, Федор В .; Хаджиагайи, Мохаммадтаги; Тиликос, Димитриос М. (2005), "Алгоритмы с фиксированными параметрами для (k,р)-центр в планарных графах и графах карт », ACM-транзакции на алгоритмах, 1 (1): 33–47, CiteSeerX 10.1.1.113.2070, Дои:10.1145/1077464.1077468, МИСТЕР 2163129.
  6. ^ Демейн, Эрик Д.; Хаджиагайи, Мохаммадтаги (2007), "Теория двумерности и ее алгоритмические приложения", Компьютерный журнал, 51 (3): 292–302, Дои:10.1093 / comjnl / bxm033, HDL:1721.1/33090.
  7. ^ Фомин, Федор В .; Локштанов Даниил; Саураб, Сакет (2012), «Двумерность и геометрические графы», Материалы двадцать третьего ежегодного симпозиума ACM-SIAM по дискретным алгоритмам (SODA 2012), стр. 1563–1575, arXiv:1107.2221, Дои:10.1137/1.9781611973099.124, ISBN 978-1-61197-210-8, МИСТЕР 3205314.