Пенни граф

В геометрической теории графов пенни -граф — это контактный граф единичных кругов . Он формируется из набора единичных кругов, которые не пересекаются друг с другом, путем создания вершины для каждого круга и края для каждой пары касательных кругов . ^[1] Круги можно физически представить в виде монет , расположенных без перекрытия на плоской поверхности, с вершиной для каждой монеты и ребром для каждых двух монет, которые соприкасаются.

Пенни-графики также называют графами единичных монет . ^[2] потому что это графы монет, образованные из единичных кругов. ^[1] Если каждая вершина представлена точкой в центре окружности, то две вершины будут смежными тогда и только тогда, когда их расстояние равно минимальному расстоянию среди всех пар вершин. Поэтому пенни-графы еще называют графами минимального расстояния . ^[3] графы наименьших расстояний , ^[4] или графики ближайших пар . ^[5] Аналогично, во взаимном графе ближайших соседей , который соединяет пары точек на плоскости, которые являются ближайшими соседями друг друга , каждый компонент связности представляет собой пенни-граф, хотя ребра в разных компонентах могут иметь разную длину. ^[6]

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

Характеристики

Количество ребер

Каждая вершина пенни-графа имеет не более шести соседних вершин; здесь цифра шесть — это число поцелуев для кругов на плоскости.Однако у монет на границе выпуклой оболочки соседей меньше. Более точный подсчет этого сокращения соседей для граничных пенни приводит к точной оценке количества ребер в любом пенни-графе: пенни-граф с $n$ вершинами имеет не более $\left\lfloor 3n-{\sqrt {12n-3}}\right\rfloor$ края. Некоторые пенни-графы, образованные путем расположения монет в треугольной сетке , имеют именно такое количество ребер. ^[7]^[8]^[9]

Нерешенная задача по математике :

Каково максимальное количество ребер в пенни-графе без треугольников?

(еще нерешенные задачи по математике)

Располагая монеты в квадратной сетке или в виде определенных квадратных графов , можно сформировать пенни -графы без треугольников , число ребер которых не менее $\left\lfloor 2n-2{\sqrt {n}}\right\rfloor ,$ и в любом пенни-графе без треугольников число ребер не более ^[10] $2n-1.65{\sqrt {n}}.$ Свейнпол предположил, что $\left\lfloor 2n-2{\sqrt {n}}\right\rfloor$ переплет плотный. ^[11] Доказательство этого или поиск лучшей границы остается открытым.

Раскраска

Каждый пенни-граф содержит вершину, имеющую не более трех соседей. Например, такую вершину можно найти в одном из углов выпуклой оболочки центров окружностей. Следовательно, пенни-графы имеют вырождение не более трех. На основании этого можно доказать, что их раскраски графов требуют не более четырех цветов, что гораздо проще, чем доказательство более общей теоремы о четырех цветах . ^[12] Однако, несмотря на ограниченную структуру, существуют грошовые графы, для которых по-прежнему требуется четыре цвета. ^[13]

Аналогично, вырождение любого пенни-графа без треугольников не превосходит двух. Каждый такой граф содержит вершину, имеющую не более двух соседей, хотя найти эту вершину на выпуклой оболочке не всегда возможно. На основании этого можно доказать, что для них требуется не более трех цветов, что легче, чем доказательство более общей теоремы Греча о том, что плоские графы без треугольников раскрашиваются в 3 цвета. ^[10]

Независимые наборы

Максимально независимое множество в графе пенни — это подмножество монет, никакие две из которых не касаются друг друга. Поиск максимальных независимых множеств NP-труден для произвольных графов и остается NP-трудным для грошовых графов. ^[2] Это пример проблемы максимального непересекающегося множества , в которой необходимо найти большие подмножества непересекающихся областей плоскости. Однако, как и в случае с плоскими графами в более общем плане, метод Бейкера обеспечивает с полиномиальным временем . схему аппроксимации этой задачи ^[14]

Нерешенная задача по математике :

Какой самый большой

c

такой, что каждый

n

-вершинный пенни-граф имеет независимый набор размеров

cn

?

(еще нерешенные задачи по математике)

В 1983 году Пол Эрдеш спросил о наибольшем числе $c$ , при котором каждый $пенни-граф с n$ -вершинами имеет независимый набор, по крайней мере, из $cn$ вершин. ^[15] То есть, если мы поместим $n$ монет на плоскую поверхность, должно остаться подмножество $монет из cn$ , которые не соприкасаются друг с другом. По теореме о четырех цветах $c \geq 1/4$ , а улучшенная оценка $c \geq 8/31 \approx 0,258$ была доказана Свейнполом. ^[16] С другой стороны, Пах и Тот доказали, что $c \leq 5/16 = 0,3125$ . ^[15] По состоянию на 2013 год это оставались лучшими границами, известными для этой проблемы. ^[4]^[17]

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

Построение пенни-графика из положений его $n$ кругов можно выполнить как пример задачи о ближайшей паре точек , затрачивая в худшем случае время $O (n log n)$ ^[5] или (со случайным временем и с использованием функции пола ) ожидаемое время $O (n)$ . ^[18] Альтернативный метод с тем же временем наихудшего случая - построить триангуляцию Делоне или граф ближайших соседей центров окружностей (оба из которых содержат граф пенни в качестве подграфа). ^[5] а затем проверьте, какие края соответствуют касаниям окружностей.

Однако если граф дан без геометрического положения его вершин, то проверка того, можно ли его представить в виде пенни-графа, является NP-трудной . ^[6] Он остается NP-трудным, даже если данный граф является деревом . ^[19] Точно так же проверка того, может ли граф быть представлен в виде трехмерного взаимного графа ближайших соседей, также является NP-трудной. ^[20]

На ориентированных пенни-графах можно выполнять некоторые вычислительные задачи, такие как проверка того, может ли одна вершина достичь другой, за полиномиальное время и значительно меньше, чем в линейном пространстве, при наличии входных данных, представляющих ее круги в форме, позволяющей выполнять основные вычислительные задачи, такие как проверка смежности. и нахождение пересечений окружностей с линиями, параллельными осям. ^[21]

Связанные семейства графов

Пенни-графы — это частный случай монетных графов (графов, которые могут быть представлены касаниями непересекающихся кругов произвольных радиусов). ^[1] Поскольку графы монет такие же, как и плоские графы , ^[22] все пенни-графы плоские. Пенни-графы также являются графами единичных дисков ( графами пересечения единичных кругов), ^[2] графы единичных расстояний (графы, которые можно нарисовать со всеми ребрами одинаковой длины, допускающими пересечения), ^[23] и спичечные графики (графики, которые можно нарисовать на плоскости с прямыми ребрами одинаковой длины и без пересечений ребер). ^[24]

Ссылки

^ Jump up to: ^а ^б ^с Писански, Томаж ; Рандич, Милан (2000), «Мосты между геометрией и теорией графов» (PDF) , в Горини, Кэтрин А. (ред.), Геометрия в работе , Примечания MAA, том. 53, Издательство Кембриджского университета, стр. 174–194, MR 1782654 ; см. особенно стр. 176
^ Jump up to: ^а ^б ^с Чериоли, Марсия Р.; Фариа, Луэрбио; Феррейра, Талита О.; Протти, Фабио (2011), «Заметка о максимальных независимых множествах и минимальных кликовых разделах в графах единичных дисков и пенни-графах: сложность и аппроксимация» , RAIRO Theoretical Informatics and Applications , 45 (3): 331–346, doi : 10.1051/ ита/2011106 , МР 2836493
^ Чизмадиа, Г. (1998), «О числе независимости графов минимальных расстояний», Discrete & Computational Geometry , 20 (2): 179–187, doi : 10.1007/PL00009381 , MR 1637884
^ Jump up to: ^а ^б Брасс, Питер; Мозер, Уильям; Пах, Янош (2005), Проблемы исследования дискретной геометрии , Нью-Йорк: Springer, стр. 228, ISBN 978-0387-23815-9 , МР 2163782
^ Jump up to: ^а ^б ^с Вельткамп, Ремко К. (1994), «2.2.1 Ближайшие пары», Границы замкнутых объектов из разбросанных точек , Конспекты лекций по информатике, том. 885, Берлин: Springer-Verlag, с. 12, номер домена : 10.1007/3-540-58808-6 , ISBN 3-540-58808-6
^ Jump up to: ^а ^б Идс, Питер ; Уайтсайдс, Сью (1996), «Логическая машина и проблема реализации графов ближайших соседей», Theoretical Computer Science , 169 (1): 23–37, doi : 10.1016/S0304-3975(97)84223-5 , MR 1424926
^ Харборт, Х. (1974), «Решение проблемы 664A», Elements of Mathematics , 29 : 14–15 . Цитируется Сванеполом (2009) и Пачом и Агарвалом (1995) .
^ Пах, Янош ; Агарвал, Панкадж К. (1995), Комбинаторная геометрия , Серия Wiley-Interscience по дискретной математике и оптимизации, Нью-Йорк: John Wiley & Sons, Inc., doi : 10.1002/9781118033203 , ISBN 0-471-58890-3 , МР 1354145 ; см. теорему 13.12, с. 211.
^ Купиц, Ю.С. (1994), «О максимальном количестве появлений минимального расстояния между $n$ точками плоскости», Интуитивная геометрия (Szeged, 1991) , Colloq. Математика. Соц. Янош Бояи, том. 63, Северная Голландия, стр. 217–244, MR 1383628.
^ Jump up to: ^а ^б Эппштейн, Дэвид (2018), «Реберные границы и вырождение пенни-графов и квадратных графов без треугольников», Journal of Graph Algorithms and Applications , 22 (3): 483–499, arXiv : 1708.05152 , doi : 10.7155/jgaa.00463 ( неактивен 29.07.2024), МР 3866392 {{citation}}: CS1 maint: DOI неактивен по состоянию на июль 2024 г. ( ссылка )
^ Свейнпол, Конрад Дж. (2009), «Графы минимальных расстояний без треугольников на плоскости» (PDF) , Geombinatorics , 19 (1): 28–30, MR 2584434
^ Хартсфилд, Нора; Рингель, Герхард (2013), «Проблема 8.4.8» , «Жемчужины теории графов: всестороннее введение» , Dover Books on Mathematics, Courier Corporation, стр. 177–178, ISBN 9780486315522 .
^ Гарднер, Мартин (март 1975 г.), «От резиновых веревок до катящихся кубиков, набор освежающих задач», Mathematical Games, Scientific American , 232 (3): 112–117, doi : 10.1038/scientificamerican0375-112 , JSTOR 24949757 ; см. задачу 7 «Цветные покерные фишки», с. 114.
^ Бейкер, Б. (1994), «Алгоритмы аппроксимации NP-полных задач на плоских графах», Журнал ACM , 41 (1): 153–180, doi : 10.1145/174644.174650 , S2CID 9706753
^ Jump up to: ^а ^б Пах, Янош ; Тот, Геза (1996), «О числе независимости графов монет» , Geombinatorics , 6 (1): 30–33, MR 1392795
^ Свейнпол, Конрад Дж. (2002), «Числа независимости плоских контактных графов», Дискретная и вычислительная геометрия , 28 (4): 649–670, arXiv : math/0403023 , doi : 10.1007/s00454-002-2897-y , МР 1949907 ; Результат Свейнпола усиливает более раннюю $c \geq 9/35 \approx 0,257$ границу Csizmadia (1998) .
^ Думитреску, Адриан; Цзян, Минхуэй (июнь 2013 г.), «Столбец вычислительной геометрии 56» (PDF) , SIGACT News , 44 (2), Нью-Йорк, штат Нью-Йорк, США: ACM: 80–87, arXiv : cs/9908007 , doi : 10.1145/2491533.2491550 , S2CID 52807205
^ Хуллер, Самир; Матиас, Йосси (1995), «Простой алгоритм рандомизированного сита для решения задачи поиска ближайшей пары», Information and Computation , 118 (1): 34–37, doi : 10.1006/inco.1995.1049 , MR 1329236
^ Боуэн, Клинтон; Дюроше, Стефан; Леффлер, Мартен; Раунды, Аника; Шульц, Андре; Тот, Чаба Д. (2015), «Реализация односвязных полигональных связей и распознавание деревьев контактов единичного диска», Джакомо, Эмилио Ди; Любив, Анна (ред.), Рисование графов и визуализация сетей: 23-й Международный симпозиум, GD 2015, Лос-Анджелес, Калифорния, США, 24–26 сентября 2015 г., Пересмотренные избранные статьи , Конспекты лекций по информатике , том. 9411, Springer, стр. 447–459, номер doi : 10.1007/978-3-319-27261-0_37 , ISBN. 978-3-319-27260-3
^ Китчинг, Мэтью; Уайтсайдс, Сью (2004), «Трехмерная логическая машина», в Пахе, Янош (ред.), Рисование графиков, 12-й Международный симпозиум, GD 2004, Нью-Йорк, Нью-Йорк, США, 29 сентября - 2 октября 2004 г., исправленная версия Избранные статьи , Конспекты лекций по информатике, том. 3383, Springer, стр. 329–339, номер документа : 10.1007/978-3-540-31843-9_33 , ISBN. 978-3-540-24528-5
^ Бхор, Суджой; Джайн, Рахул (2021), «Экономичные алгоритмы достижимости в ориентированных геометрических графах» , Ан, Хи-Кап; Садакане, Кунихико (ред.), 32-й Международный симпозиум по алгоритмам и вычислениям (ISAAC 2021) , Международные труды Лейбница по информатике (LIPIcs), том. 212, Дагштуль, Германия: Schloss Dagstuhl – Leibniz-Zentrum für Informatik, стр. 63:1–63:17, doi : 10.4230/LIPIcs.ISAAC.2021.63 , ISBN 978-3-95977-214-3 , S2CID 244731943
^ Хартсфилд и Рингель (2013) , Теорема 8.4.2, с. 173.
^ Хорват, Борис; Писански, Томаж (2010), «Продукты графов единичных расстояний», Дискретная математика , 310 (12): 1783–1792, doi : 10.1016/j.disc.2009.11.035 , MR 2610282
^ Фейоле, Лоран (29 мая 2019 г.), «Графики, определяемые спичками, монетами и петлями» , Дискретные заметки

[links-1] Jump up to: ^а ^б ^с Писански, Томаж ; Рандич, Милан (2000), «Мосты между геометрией и теорией графов» (PDF) , в Горини, Кэтрин А. (ред.), Геометрия в работе , Примечания MAA, том. 53, Издательство Кембриджского университета, стр. 174–194, MR 1782654 ; см. особенно стр. 176

[cffp-2] Jump up to: ^а ^б ^с Чериоли, Марсия Р.; Фариа, Луэрбио; Феррейра, Талита О.; Протти, Фабио (2011), «Заметка о максимальных независимых множествах и минимальных кликовых разделах в графах единичных дисков и пенни-графах: сложность и аппроксимация» , RAIRO Theoretical Informatics and Applications , 45 (3): 331–346, doi : 10.1051/ ита/2011106 , МР 2836493

[csiz-3] Чизмадиа, Г. (1998), «О числе независимости графов минимальных расстояний», Discrete & Computational Geometry , 20 (2): 179–187, doi : 10.1007/PL00009381 , MR 1637884

[bmp-4] Jump up to: ^а ^б Брасс, Питер; Мозер, Уильям; Пах, Янош (2005), Проблемы исследования дискретной геометрии , Нью-Йорк: Springer, стр. 228, ISBN 978-0387-23815-9 , МР 2163782

[rcv-5] Jump up to: ^а ^б ^с Вельткамп, Ремко К. (1994), «2.2.1 Ближайшие пары», Границы замкнутых объектов из разбросанных точек , Конспекты лекций по информатике, том. 885, Берлин: Springer-Verlag, с. 12, номер домена : 10.1007/3-540-58808-6 , ISBN 3-540-58808-6

[ew96-6] Jump up to: ^а ^б Идс, Питер ; Уайтсайдс, Сью (1996), «Логическая машина и проблема реализации графов ближайших соседей», Theoretical Computer Science , 169 (1): 23–37, doi : 10.1016/S0304-3975(97)84223-5 , MR 1424926

[harborth-7] Харборт, Х. (1974), «Решение проблемы 664A», Elements of Mathematics , 29 : 14–15 . Цитируется Сванеполом (2009) и Пачом и Агарвалом (1995) .

[pj95-8] Пах, Янош ; Агарвал, Панкадж К. (1995), Комбинаторная геометрия , Серия Wiley-Interscience по дискретной математике и оптимизации, Нью-Йорк: John Wiley & Sons, Inc., doi : 10.1002/9781118033203 , ISBN 0-471-58890-3 , МР 1354145 ; см. теорему 13.12, с. 211.

[kupitz-9] Купиц, Ю.С. (1994), «О максимальном количестве появлений минимального расстояния между $n$ точками плоскости», Интуитивная геометрия (Szeged, 1991) , Colloq. Математика. Соц. Янош Бояи, том. 63, Северная Голландия, стр. 217–244, MR 1383628.

[eppstein-10] Jump up to: ^а ^б Эппштейн, Дэвид (2018), «Реберные границы и вырождение пенни-графов и квадратных графов без треугольников», Journal of Graph Algorithms and Applications , 22 (3): 483–499, arXiv : 1708.05152 , doi : 10.7155/jgaa.00463 ( неактивен 29.07.2024), МР 3866392 {{citation}}: CS1 maint: DOI неактивен по состоянию на июль 2024 г. ( ссылка )

[swanepoel-11] Свейнпол, Конрад Дж. (2009), «Графы минимальных расстояний без треугольников на плоскости» (PDF) , Geombinatorics , 19 (1): 28–30, MR 2584434

[pearls-12] Хартсфилд, Нора; Рингель, Герхард (2013), «Проблема 8.4.8» , «Жемчужины теории графов: всестороннее введение» , Dover Books on Mathematics, Courier Corporation, стр. 177–178, ISBN 9780486315522 .

[gardner-13] Гарднер, Мартин (март 1975 г.), «От резиновых веревок до катящихся кубиков, набор освежающих задач», Mathematical Games, Scientific American , 232 (3): 112–117, doi : 10.1038/scientificamerican0375-112 , JSTOR 24949757 ; см. задачу 7 «Цветные покерные фишки», с. 114.

[baker-14] Бейкер, Б. (1994), «Алгоритмы аппроксимации NP-полных задач на плоских графах», Журнал ACM , 41 (1): 153–180, doi : 10.1145/174644.174650 , S2CID 9706753

[pt96-15] Jump up to: ^а ^б Пах, Янош ; Тот, Геза (1996), «О числе независимости графов монет» , Geombinatorics , 6 (1): 30–33, MR 1392795

[swan2-16] Свейнпол, Конрад Дж. (2002), «Числа независимости плоских контактных графов», Дискретная и вычислительная геометрия , 28 (4): 649–670, arXiv : math/0403023 , doi : 10.1007/s00454-002-2897-y , МР 1949907 ; Результат Свейнпола усиливает более раннюю $c \geq 9/35 \approx 0,257$ границу Csizmadia (1998) .

[dj13-17] Думитреску, Адриан; Цзян, Минхуэй (июнь 2013 г.), «Столбец вычислительной геометрии 56» (PDF) , SIGACT News , 44 (2), Нью-Йорк, штат Нью-Йорк, США: ACM: 80–87, arXiv : cs/9908007 , doi : 10.1145/2491533.2491550 , S2CID 52807205

[km95-18] Хуллер, Самир; Матиас, Йосси (1995), «Простой алгоритм рандомизированного сита для решения задачи поиска ближайшей пары», Information and Computation , 118 (1): 34–37, doi : 10.1006/inco.1995.1049 , MR 1329236

[bdlrst-19] Боуэн, Клинтон; Дюроше, Стефан; Леффлер, Мартен; Раунды, Аника; Шульц, Андре; Тот, Чаба Д. (2015), «Реализация односвязных полигональных связей и распознавание деревьев контактов единичного диска», Джакомо, Эмилио Ди; Любив, Анна (ред.), Рисование графов и визуализация сетей: 23-й Международный симпозиум, GD 2015, Лос-Анджелес, Калифорния, США, 24–26 сентября 2015 г., Пересмотренные избранные статьи , Конспекты лекций по информатике , том. 9411, Springer, стр. 447–459, номер doi : 10.1007/978-3-319-27261-0_37 , ISBN. 978-3-319-27260-3

[kw04-20] Китчинг, Мэтью; Уайтсайдс, Сью (2004), «Трехмерная логическая машина», в Пахе, Янош (ред.), Рисование графиков, 12-й Международный симпозиум, GD 2004, Нью-Йорк, Нью-Йорк, США, 29 сентября - 2 октября 2004 г., исправленная версия Избранные статьи , Конспекты лекций по информатике, том. 3383, Springer, стр. 329–339, номер документа : 10.1007/978-3-540-31843-9_33 , ISBN. 978-3-540-24528-5

[bj21-21] Бхор, Суджой; Джайн, Рахул (2021), «Экономичные алгоритмы достижимости в ориентированных геометрических графах» , Ан, Хи-Кап; Садакане, Кунихико (ред.), 32-й Международный симпозиум по алгоритмам и вычислениям (ISAAC 2021) , Международные труды Лейбница по информатике (LIPIcs), том. 212, Дагштуль, Германия: Schloss Dagstuhl – Leibniz-Zentrum für Informatik, стр. 63:1–63:17, doi : 10.4230/LIPIcs.ISAAC.2021.63 , ISBN 978-3-95977-214-3 , S2CID 244731943

[FOOTNOTEHartsfieldRingel2013Theorem_8.4.2,_p.&nbsp;173-22] Хартсфилд и Рингель (2013) , Теорема 8.4.2, с. 173.

[hp10-23] Хорват, Борис; Писански, Томаж (2010), «Продукты графов единичных расстояний», Дискретная математика , 310 (12): 1783–1792, doi : 10.1016/j.disc.2009.11.035 , MR 2610282

[dn-24] Фейоле, Лоран (29 мая 2019 г.), «Графики, определяемые спичками, монетами и петлями» , Дискретные заметки

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[23]

[24]