График карты
В теории графов , разделе математики, граф карты — это неориентированный граф, образованный как граф пересечений конечного числа односвязных и внутренне непересекающихся областей евклидовой плоскости . Графы карт включают в себя плоские графы , но они более общие. Любое количество регионов может встретиться в общем углу (как в « Четырех углах» Соединенных Штатов, где встречаются четыре штата), и когда это произойдет, граф карты будет содержать клику, соединяющую соответствующие вершины, в отличие от плоских графов, в которых наибольшие клика имеет только четыре вершины. [1] Другим примером графа карты является граф короля , граф карты клеток шахматной доски, соединяющий пары клеток, между которыми может перемещаться шахматный король.
Комбинаторное представление
[ редактировать ]Графы карт можно комбинаторно представить как «полуквадраты плоских двудольных графов». То есть, пусть G = ( U , V , E ) — плоский двудольный граф с двудольным разделением ( U , V ) . Квадрат графа в G в котором две вершины смежны в квадрате, когда они находятся на расстоянии не более двух шагов друг от друга G. — это другой граф на том же множестве вершин , Полуквадрат или двудольная половина — это индуцированный подграф одной стороны двураздела (скажем, V ) в квадратном графе: его набор вершин — это V и у него есть ребро между любыми двумя вершинами в V , которые находятся на расстоянии двух шагов друг от друга в G. , Полуквадрат — это граф карты. найдя плоское вложение G V и расширив каждую вершину U. ребра в звездообразную область так, чтобы эти области соприкасались в вершинах и прилегающие к ней Его можно представить геометрически , И наоборот, каждый граф карты может быть представлен таким образом в виде полуквадрата. [1]
Вычислительная сложность
[ редактировать ]В 1998 году Миккель Торуп заявил, что графы карт можно распознать за полиномиальное время . [2] Однако высокий показатель набросанного им алгоритма делает его непрактичным, и Торуп не опубликовал подробностей своего метода и его доказательства. [3]
Задача о максимальном независимом множестве имеет полиномиальное время схему аппроксимации графов карт за , а хроматическое число может быть аппроксимировано с точностью до двух раз за полиномиальное время. [4] Теория двумерности приводит ко многим другим алгоритмам аппроксимации и управляемым алгоритмам с фиксированным параметром для решения задач оптимизации на графах карт. [5] [6] [7]
Вариации и связанные концепции
[ редактировать ]Граф k -map — это граф карты, полученный из набора регионов, в которых не более k в любой точке встречается регионов. Эквивалентно, это полуквадрат плоского двудольного графа, в котором множество вершин U (сторона двудольного деления, не используемая для создания полуквадрата) имеет максимальную степень k . Граф с тремя картами — это планарный граф , и каждый планарный граф можно представить как граф с тремя картами. Каждый граф с 4 картами — это 1-планарный граф , граф, который можно нарисовать не более чем с одним пересечением на ребро, и каждый оптимальный 1-планарный граф (граф, образованный из плоского четырехугольника путем добавления двух пересекающихся диагоналей к каждой четырехугольной грани ) представляет собой граф с 4 картами. Однако некоторые другие 1-планарные графы не являются графами-картами, поскольку (в отличие от графов-карт) они включают пересекающиеся ребра, которые не являются частью полного подграфа с четырьмя вершинами. [1]
Ссылки
[ редактировать ]- ^ Перейти обратно: а б с Чен, Чжи-Чжун; Гриньи, Микеланджело; Пападимитриу, Христос Х. (2002), «Карта графиков», Журнал ACM , 49 (2): 127–138, arXiv : cs/9910013 , doi : 10.1145/506147.506148 , MR 2147819 , S2CID 2657838 .
- ^ Торуп, Миккель (1998), «Карта-графики в полиномиальное время», Труды 39-го ежегодного симпозиума по основам информатики (FOCS 1998) , стр. 396–405, doi : 10.1109/SFCS.1998.743490 , ISBN 978-0-8186-9172-0 , S2CID 36845908 .
- ^ Бранденбург, Франц Дж. (август 2018 г.), «Характеристика и распознавание графов с 4 картами», Algorithmica , 81 (5): 1818–1843, doi : 10.1007/s00453-018-0510-x , S2CID 254038620
- ^ Чен, Чжи-Чжун (2001), «Алгоритмы аппроксимации независимых множеств в графах отображений», Journal of Algorithms , 41 (1): 20–40, doi : 10.1006/jagm.2001.1178 , MR 1855346 .
- ^ Демейн, Эрик Д .; Фомин Федор Владимирович; Хаджиагайи, Мохаммадтаги ; Тиликос, Димитриос М. (2005), «Алгоритмы с фиксированными параметрами для ( k , r ) -центра в плоских графах и графах карт», Транзакции ACM по алгоритмам , 1 (1): 33–47, CiteSeerX 10.1.1.113.2070 , doi : 10.1145/1077464.1077468 , MR 2163129 , S2CID 2757196 .
- ^ Демейн, Эрик Д .; Хаджиагайи, Мохаммадтаги (2007), «Теория двумерности и ее алгоритмические приложения», The Computer Journal , 51 (3): 292–302, doi : 10.1093/comjnl/bxm033 , hdl : 1721.1/33090 .
- ^ Фомин Федор Владимирович; Локштанов Даниил; Саураб, Сакет (2012), «Двумерность и геометрические графы», Труды двадцать третьего ежегодного симпозиума ACM-SIAM по дискретным алгоритмам (SODA 2012) , стр. 1563–1575, arXiv : 1107.2221 , doi : 10.1137/1.97816119730 99.124 , ISBN 978-1-61197-210-8 , МР 3205314 , S2CID 9336216 .