Аполлоническая сеть

Аполлоническая сеть

Граф Гольднера – Харари , негамильтонова аполлонова сеть.

В комбинаторной математике аполлонова сеть — это неориентированный граф, образованный процессом рекурсивного разделения треугольника на три меньших треугольника. Аполлоновы сети могут быть эквивалентно определены как плоские 3-деревья , максимальные плоские хордальные графы, плоские графы, однозначно раскрашиваемые в 4 цвета , и графы сложенных многогранников . Они названы в честь Аполлония Пергского , который изучал родственную конструкцию упаковки кругов.

Определение

Аполлонову сеть можно сформировать, начиная с одного треугольника, вложенного в евклидову плоскость , путем многократного выбора треугольной грани вложения, добавления новой вершины внутри грани и соединения новой вершины с каждой вершиной грани, содержащей ее. Таким образом, треугольник, содержащий новую вершину, делится на три меньших треугольника, которые, в свою очередь, можно разделить таким же образом.

Примеры

с Полные графы тремя и четырьмя вершинами K ₃ и K ₄ являются аполлоновыми сетями. K ₃ формируется путем начала с треугольника без выполнения каких-либо делений, а K ₄ формируется путем выполнения одного деления перед остановкой.

Граф Гольднера – Харари — это аполлонова сеть, образующая наименьший негамильтонов максимальный планарный граф. Другая, более сложная аполлонова сеть была использована Нишизеки (1980), чтобы предоставить пример 1-жесткого негамильтонова максимального планарного графа.

Теоретико-графовые характеристики

Помимо того, что сети Аполлона определяются рекурсивным подразделением треугольников, они имеют несколько других эквивалентных математических характеристик. Это хордальные максимальные плоские графы, хордальные многогранные графы и плоские 3-деревья . Это уникальные плоские графы, раскрашиваемые в 4 цвета , и плоские графы с уникальным разложением древесины Шнайдера на три дерева. Это максимальные планарные графы с шириной дерева три, класс графов, которые можно охарактеризовать своими запрещенными минорами или их сводимостью при преобразованиях Y-Δ . Это максимальные планарные графы с вырождением три. Это также плоские графы с заданным числом вершин, которые имеют максимально возможное количество треугольников, максимально возможное количество тетраэдрических подграфов, максимально возможное количество клик и максимально возможное количество частей после разложения путем разделения треугольников.

хордальность

Аполлоновы сети являются примерами максимальных планарных графов , графов, к которым нельзя добавить никакие дополнительные ребра без нарушения планарности, или, что то же самое, графов, которые можно нарисовать на плоскости так, чтобы каждая грань (включая внешнюю) была треугольником. Они также являются хордальными графами , графами, в которых каждый цикл из четырех или более вершин имеет диагональное ребро, соединяющее две непоследовательные вершины цикла, а порядок, в котором вершины добавляются в процессе подразделения, образующем аполлонову сеть, представляет собой порядок исключения, как хордальный граф. Это формирует альтернативную характеристику аполлоновых сетей: они в точности являются хордальными максимальными планарными графами или, что то же самое, хордальными многогранными графами .

В аполлоновой сети каждая максимальная клика представляет собой полный граф на четырех вершинах, образованный выбором любой вершины и трех ее предыдущих соседей. Каждый минимальный разделитель клики (клика, которая делит граф на два несвязных подграфа) является одним из разделенных треугольников. Хордальный граф, в котором все максимальные клики и все минимальные разделители клик имеют одинаковый размер, является k -деревом , а аполлоновы сети являются примерами 3-деревьев. Не каждое трехдеревье плоское, но плоские трехдеревья представляют собой в точности аполлоновы сети.

Уникальная возможность окрашивания

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

Аполлоновы сети также представляют собой в точности максимальные планарные графы, которые (после фиксирования внешней грани) имеют уникальный лес Шнайдера — разбиение ребер графа на три перемежающихся дерева, корни которых лежат в трех вершинах внешней грани.

Ширина дерева

Аполлоновы сети не образуют семейство графов, замкнутое относительно операции взятия миноров графа , поскольку удаление ребер, но не вершин, из аполлоновой сети дает граф, который не является аполлоновой сетью. Однако плоские частичные трехдеревья , подграфы аполлоновых сетей, минорно-замкнуты. Поэтому, согласно теореме Робертсона-Сеймура , они могут характеризоваться конечным числом запрещенных миноров . Минимальными запрещенными минорами для плоских частичных 3-деревьев являются четыре минимальных графа среди запрещенных миноров для плоских графов и частичных 3-деревьев: полный граф K ₅ , полный двудольный граф K _3,3 , граф октаэдр и график пятиугольной призмы . Аполлоновы графы — это максимальные графы, у которых ни один из этих четырех графов не является минорным.

Преобразование Y-Δ , операция, которая заменяет вершину третьей степени в графе треугольником, соединяющим ее соседей, достаточно (вместе с удалением параллельных ребер), чтобы свести любую аполлонову сеть к одному треугольнику и, в более общем смысле, к Планарные графы, которые можно свести к одному ребру с помощью преобразований Y-Δ, удаления параллельных ребер, удаления вершин первой степени и сжатия вершин второй степени, представляют собой в точности плоские частичные 3-деревья. Двойственные графы плоских частичных 3-деревьев образуют другое минорно-замкнутое семейство графов и представляют собой в точности те планарные графы, которые можно свести к одному ребру с помощью преобразований Δ-Y, удаления параллельных ребер, удаления вершин первой степени и сжатие вершин второй степени.

Вырождение

В каждом подграфе аполлоновой сети последняя добавленная вершина имеет степень не выше трех, поэтому аполлоновы сети имеют вырождение три. Таким образом, порядок, в котором добавляются вершины для создания сети, представляет собой порядок вырождения, а аполлоновы сети совпадают с 3-вырожденными максимальными планарными графами.

Экстремальность

Другая характеристика аполлонических сетей связана с их связностью . Любой максимальный планарный граф можно разложить на 4-связные максимальные планарные подграфы, разбив его по разделяющим его треугольникам (треугольникам, которые не являются гранями графа): для любого неграничного треугольника: можно сформировать два меньших максимальных планарных графа, один состоит из части внутри треугольника, а другой - из части вне треугольника. Максимальные планарные графы без разделяющих треугольников, которые могут быть образованы повторяющимися разбиениями этого типа, иногда называются блоками, хотя это название также использовалось для двусвязных компонентов графа, который сам по себе не является двусвязным. Аполлонова сеть — это максимальный планарный граф, в котором все блоки изоморфны полному графу K ₄ .

В экстремальной теории графов аполлоновы сети также представляют собой планарные графы с n - вершинами, в которых количество блоков достигает максимума, n - 3 , и плоские графы, в которых количество треугольников достигает максимума, 3 n - 8 . Поскольку каждый подграф K ₄ планарного графа должен быть блоком, это также планарные графы, в которых количество подграфов K ₄ достигает максимума, n − 3 , и графы, в которых количество клик любого типа достигает своего максимума. максимум, 8 n − 16 .

Геометрические реализации

Конструкция из круглых насадок

Пример аполлонической прокладки

Построение аполлоновой сети из упаковки кругов.

Аполлонические сети названы в честь Аполлония Пергского , который изучал проблему Аполлония о построении окружности, касательной к трем другим окружностям. Один из методов построения аполлоновых сетей состоит в том, чтобы начать с трех взаимно касающихся кругов, а затем неоднократно вписать еще один круг в зазор, образованный тремя ранее нарисованными кругами. Фрактальная совокупность кругов, полученная таким способом, называется аполлоновой прокладкой .

Если процесс создания аполлоновой прокладки остановлен раньше, имея только конечный набор окружностей, то граф, имеющий одну вершину для каждой окружности и одно ребро для каждой пары касательных окружностей, будет аполлоновой сетью. Существование набора касательных окружностей, касания которых представляют заданную аполлонову сеть, образует простой пример теоремы Кёбе-Андреева-Терстона об упаковке кругов , которая утверждает, что любой плоский граф может быть представлен касательными окружностями таким же образом.

Многогранники

Триакис тетраэдр , многогранная реализация 8-вершинной аполлоновой сети.

Аполлоновы сети представляют собой плоские 3-связные графы и поэтому по теореме Стейница всегда могут быть представлены в виде графиков выпуклых многогранников . Выпуклый многогранник, представляющий аполлонову сеть, представляет собой трехмерный сложенный многогранник . Такой многогранник можно получить из тетраэдра, многократно наклеивая по одному на его треугольные грани дополнительные тетраэдры. Следовательно, аполлоновы сети также можно определить как графы сложенных трехмерных многогранников. Можно найти представление любой аполлоновой сети в виде выпуклого трехмерного многогранника, в котором все координаты являются целыми числами полиномиального размера, что лучше, чем то, что известно для других плоских графов.

Треугольные сетки

Рекурсивное деление треугольников на три меньших треугольника исследовалось как метод сегментации изображений в компьютерном зрении Элкоком , Гаргантини и Уолшем (1987) ; в этом контексте они назвали это разложением тройного разностороннего треугольника . Они заметили, что, помещая каждую новую вершину в центр тяжести окружающего ее треугольника, можно выбрать триангуляцию таким образом, чтобы все треугольники имели равные площади, хотя и не все они имели одинаковую форму. В более общем смысле,Аполлонические сети можно нарисовать на плоскости с любой предписанной площадью на каждой грани; если площади являются рациональными числами , то же самое относится и ко всем координатам вершин.

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

Свойства и применение

Графики без совпадений

Пламмер (1992) использовал аполлоновы сети для построения бесконечного семейства максимальных планарных графов с четным числом вершин, но без идеального сопоставления . Графики Пламмера формируются в два этапа. На первом этапе, начиная с треугольника abc , многократно разбивается треугольная грань подразделения, которое содержит ребро bc : в результате получается граф, состоящий из пути от a до конечной вершины подразделения вместе с ребром от каждой вершины пути до каждый из b и c . На втором этапе каждая из треугольных граней полученного плоского графа подразделяется еще раз. Если путь от a до конечной вершины подразделения первого этапа имеет четную длину, то количество вершин в общем графе также четное. Однако примерно 2/3 вершин — это те, которые вставляются на втором этапе; они образуют независимый набор и не могут быть сопоставлены друг с другом, а вне независимого набора недостаточно вершин, чтобы найти совпадения для всех из них.

Хотя сами аполлоновы сети могут не иметь идеальных паросочетаний, плоские двойственные графы аполлоновых сетей представляют собой 3-регулярные графы без разрезов , поэтому по теореме Петерсена (1891) им гарантировано наличие хотя бы одного идеального паросочетания. Однако в этом случае известно больше: двойственные сети Аполлона всегда имеют экспоненциальное число совершенных паросочетаний. Ласло Ловас и Майкл Д. Пламмер предположили, что аналогичная экспоненциальная нижняя оценка справедлива в более общем смысле для любого 3-регулярного графа без разрезанных ребер, и этот результат был позже доказан.

Графики степенного закона

Андраде и др. (2005) изучали степенные законы в последовательностях степеней частного случая сетей этого типа, образованных разделением всех треугольников одинаковое количество раз. Они использовали эти сети для моделирования упаковки пространства частицами разных размеров. На основе своей работы другие авторы представили случайные аполлоновы сети, сформированные путем многократного выбора случайного лица для разделения, и показали, что они также подчиняются степенным законам в распределении степеней. и имеют небольшие средние расстояния. Алан М. Фриз и Харалампос Э. Цуракакис проанализировали высшие степени и собственные значения случайных аполлонических сетей. Андраде и др. также заметил, что их сети удовлетворяют эффекту маленького мира , когда все вершины находятся на небольшом расстоянии друг от друга. Основываясь на числовых данных, они оценили среднее расстояние между случайно выбранными парами вершин в n -вершинной сети этого типа как пропорциональное (log n ) ^3/4 , но позже исследователи показали, что среднее расстояние на самом деле пропорционально log n .

Угловое распределение

Батлер и Грэм (2010) заметили, что если каждая новая вершина помещается в центр своего треугольника, так что края новой вершины делят углы треугольника пополам, то набор троек углов треугольников в подразделении, когда переинтерпретируемый как тройки барицентрических координат точек равностороннего треугольника , сходится по форме к треугольнику Серпинского по мере роста числа уровней подразделения.

гамильтоновость

Такео (1960) ошибочно утверждал, что все аполлоновы сети имеют гамильтоновы циклы ; однако граф Гольднера – Харари представляет собой контрпример. Если аполлонова сеть имеет жесткость больше единицы (это означает, что удаление любого набора вершин из графа оставляет меньшее количество компонентов связности, чем количество удаленных вершин), то она обязательно имеет гамильтонов цикл, но существуют негамильтоновы аполлоновы сети. чья жесткость равна единице.

Перечисление

Комбинаторная задача подсчета аполлоновых триангуляций была изучена Такео (1960) , который показал, что они имеют простую производящую функцию f ( x ) , описываемую уравнением f ( x ) = 1 + x ( f ( x )) ³ .В этой производящей функции член степени n подсчитывает количество аполлоновых сетей с фиксированным внешним треугольником и n + 3 вершинами.Таким образом, количество аполлоновых сетей (с фиксированным внешним треугольником) на 3, 4, 5,... вершинах равно:

1, 1, 3, 12, 55, 273, 1428, 7752, 43263, 246675, ... (последовательность A001764 в OEIS ),

последовательность, которая также считает троичные деревья и разрезания выпуклых многоугольников на нечетные многоугольники.Например, существует 12 6-вершинных аполлонических сетей: три образованы путем разделения внешнего треугольника один раз, а затем разделения двух полученных треугольников,и девять, образованные путем разделения внешнего треугольника один раз, разделения одного из его треугольников, а затем разделения одного из получившихся меньших треугольников.

История

Биркгоф (1930) — ранняя статья, в которой используется двойная форма аполлоновых сетей, плоские карты, образованные путем многократного размещения новых регионов в вершинах более простых карт, как класс примеров плоских карт с небольшим количеством раскрасок.

Геометрические структуры, тесно связанные с аполлоновыми сетями, изучаются в полиэдральной комбинаторике , по крайней мере, с начала 1960-х годов, когда они использовались Грюнбаумом (1963) для описания графов, которые могут быть реализованы как граф многогранника только одним способом, без размерности или комбинаторные неоднозначности, а также Мун и Мозер (1963) для поиска симплициальных многогранников без длинных путей. В теории графов тесная связь между планарностью и шириной дерева восходит к Робертсону и Сеймуру (1984) , которые показали, что каждое малозамкнутое семейство графов либо имеет ограниченную древовидную ширину, либо содержит все плоские графы. Плоские 3-деревья как класс графов подробно рассматривались Хакими и Шмейхелем (1979) , Алоном и Каро (1984) , Патилом (1986) и многими авторами после них.

Название «аполлоническая сеть» было дано Андраде и др. (2005) к изученным ими сетям, в которых уровень подразделения треугольников одинаков по всей сети; эти сети геометрически соответствуют типу сложенного многогранника, называемому Клитопом . Другие авторы в более широком смысле применили то же название к плоским трехмерным деревьям в своей работе, обобщающей модель Андраде и др. случайным аполлоновым сетям. Триангуляции, созданные таким образом, также получили название «сложные триангуляции». или «стек-триангуляции».

См. также

• Барицентрическое подразделение — другой метод разделения треугольников на меньшие треугольники.
• Поверхность разделения петли , еще один метод разделения треугольников на меньшие треугольники.

Ссылки

• Альбенке, Мари; Маркерт, Жан-Франсуа (2008), «Некоторые семейства возрастающих плоских карт» , Electronic Journal of Probability , 13 : 1624–1671, arXiv : 0712.0593 , doi : 10.1214/ejp.v13-563 , MR   2438817 , S2CID   2420262
• Альмеринг, JHJ (1963), «Рациональные четырехугольники», Mathematical Inquiries , 25 : 192–199, doi : 10.1016/S1385-7258(63)50020-1 , MR   0147447 .
• Алон, Н. ; Каро, Ю. (1984), «О количестве подграфов заданного типа плоских графов с заданным количеством вершин», в Розенфельде, М.; Закс, Дж. (ред.), Выпуклость и теория графов: материалы конференции по выпуклости и теории графов, Израиль, март 1981 г. , Анналы дискретной математики 20, Математические исследования Северной Голландии 87, Elsevier, стр. 25–36, ISBN  978-0-444-86571-7 , МР   0791009 .
• Андраде, Хосе С. младший; Херрманн, Ганс Дж.; Андраде, Роберто Ф.С.; да Силва, Лучано Р. (2005), «Аполлоновы сети: одновременно безмасштабные, маленький мир, евклидовы, заполнение пространства и с соответствующими графами», Physical Review Letters , 94 (1): 018702, arXiv : cond-mat/ 0406295 , Bibcode : 2005PhRvL..94a8702A , doi : 10.1103/physrevlett.94.018702 , PMID   15698147 .
• Арнборг, С.; Проскуровский А.; Корниэль, Д. (1986), Характеристика запрещенных несовершеннолетних частичных трехдеревьев , Технический отчет CIS-TR-86-07, Факультет компьютерных и информационных наук, Университет Орегона . Цитируется Эль-Маллахом и Колборном (1990) .
• Бадент, Мелани; Бинуччи, Карла; Ди Джакомо, Эмилио; Дидимус, Уолтер; Фельснер, Стефан; Джордано, Франческо; Краточвил, Ян; Палладино, Пьетро; Патриньяни, Маурицио; Тротта, Франческо (2007), «Гомотетичные треугольные контактные представления планарных графов», Канадская конференция по вычислительной геометрии (PDF) .
• Ниже Александр; Де Лоэра, Хесус А .; Рихтер-Геберт, Юрген (2000), Сложность поиска малых триангуляций выпуклых трехмерных многогранников , arXiv : math/0012177 , Bibcode : 2000math.....12177B .
• Бернарди, Оливье; Бонихон, Николя (2009), «Интервалы в каталонских решетках и реализаторы триангуляции», Журнал комбинаторной теории , серия A, 116 (1): 55–75, doi : 10.1016/j.jcta.2008.05.005 , MR   2469248 .
• Бидль, Тереза ; Руис Веласкес, Лесвия Елена (2010), «Рисование плоских трехдеревьев с заданными площадями граней», Рисование графов, 17-й Международный симпозиум, GD 2009, Чикаго, Иллинойс, США, 22–25 сентября 2009 г., Переработанные статьи , Конспекты лекций в области компьютерных наук, вып. 5849, Springer-Verlag, стр. 316–322, номер документа : 10.1007/978-3-642-11805-0_30 .
• Биркгоф, Джордж Д. (1930), «О количестве способов раскрасить карту», ​​Труды Эдинбургского математического общества , (2), 2 (2): 83–91, doi : 10.1017/S0013091500007598 .
• Бодлендер, Ханс Л. (1998), «Частичный k -дендрарий графов с ограниченной шириной дерева», Theoretical Computer Science , 209 (1–2): 1–45, doi : 10.1016/S0304-3975(97)00228-4 , HDL : 1874/18312 , МР   1647486 .
• Бёме, Томас; Харант, Йохен; Ткач, Михал (1999), «Более одного жесткого хордального плоского графа являются гамильтоновыми», Journal of Graph Theory , 32 (4): 405–410, doi : 10.1002/(SICI)1097-0118(199912)32:4< 405::AID-JGT8>3.3.CO;2-Q , MR   1722793 .
• Батлер, С.; Грэм, Рон (2010), «Итерированные треугольные перегородки», Катона, Г.; Шрийвер, А .; Сони, Т. (ред.), Фестиваль комбинаторики и информатики (PDF) , Математические исследования Общества Боляи, том. 29, Гейдельберг: Springer-Verlag, стр. 23–42 .
• Дай, Уэйн Вэй-Мин; Сато, Масао (1990), «Минимальная запрещенная второстепенная характеристика плоских частичных трехдеревьев и применение к компоновке схем», Международный симпозиум IEEE по схемам и системам , том. 4, стр. 2677–2681, номер документа : 10.1109/ISCAS.1990.112560 , S2CID   122926229.
• Демейн, Эрик ; Шульц, Андре (2011), «Вложение сложенных многогранников в сетку полиномиального размера», Proc. Симпозиум ACM-SIAM по дискретным алгоритмам (PDF) , стр. 1177–1187, заархивировано из оригинала (PDF) 1 июня 2011 г. , получено 7 марта 2011 г.
• Дуймович, Вида ; Фиявж, Гашпер; Жоре, Гвенаэль; Вуд, Дэвид Р. (2009), «Максимальное количество клик в графе, встроенном в поверхность», European Journal of Combinatorics , 32 (8): 1244–1252, arXiv : 0906.4142 , Bibcode : 2009arXiv0906.4142D , doi : 10.1016/j.ejc.2011.04.001 , S2CID   1733300 .
• Эль-Маллах, Эхаб С.; Колборн, Чарльз Дж. (1990), «О двух двойственных классах плоских графов», Discrete Mathematics , 80 (1): 21–40, doi : 10.1016/0012-365X(90)90293-Q , MR   1045921 .
• Элкок, EW; Гаргантини, И .; Уолш, Т.Р. (1987), «Треугольное разложение», Image and Vision Computing , 5 (3): 225–231, doi : 10.1016/0262-8856(87)90053-9 .
• Фельснер, Стефан; Зикфельд, Флориан (2008), «О количестве плоских ориентаций с заданными степенями» (PDF) , Электронный журнал комбинаторики , 15 (1): R77, arXiv : math/0701771 , Bibcode : 2007math......1771F , doi : 10.37236/801 , MR   2411454 , S2CID   13893657 .
• Фриз, Алан М .; Цуракакис, Харалампос Э. (2011), Вершины высоких степеней, собственные значения и диаметр случайных аполлоновых сетей , arXiv : 1104.5259 , Bibcode : 2011arXiv1104.5259F .
• Фаулер, Томас (1998), Уникальная раскраска планарных графов (PDF) , доктор философии. диссертация, математический факультет Технологического института Джорджии .
• Гилен, Джим; Го, Энджи; Маккиннон, Дэвид (2008), «Вложения прямых кубических плоских графов с целочисленными длинами ребер», Journal of Graph Theory , 58 (3): 270–274, doi : 10.1002/jgt.20304 , MR   2419522 .
• Герлах, Т. (2004), «Твердость и гамильтоновость класса плоских графов», Discrete Mathematics , 286 (1–2): 61–65, doi : 10.1016/j.disc.2003.11.046 , MR   2084280 .
• Гольднер, А.; Харари, Ф. (1975), «Замечание о наименьшем негамильтоновом максимальном плоском графе», Bull. Малазийская математика. Соц. , 6 (1): 41–42 . См. также тот же журнал 6 (2):33 (1975) и 8 :104-106 (1977). Ссылка из списка публикаций Харари .
• Грюнбаум, Бранко (1963), «Однозначные многогранные графы», Израильский журнал математики , 1 (4): 235–238, doi : 10.1007/BF02759726 , MR   0185506 , S2CID   121075042 .
• Грюнбаум, Бранко (1967), Выпуклые многогранники , Wiley Interscience .
• Хакими, СЛ ; Шмейхель, EF (1979), «О количестве циклов длины k в максимальном плоском графе», Journal of Graph Theory , 3 (1): 69–86, doi : 10.1002/jgt.3190030108 , MR   0519175 .
• Хименес, Андреа; Киви, Маркос (2010), Подсчет идеальных паросочетаний кубических графов в двойственной геометрической форме , arXiv : 1010.5918 , Bibcode : 2010arXiv1010.5918J .
• Кумар, П. Шриниваса; Мадхаван, CE Вени (1989), «Новый класс сепараторов и планарность хордальных графов», Основы программных технологий и теоретической информатики, Девятая конференция, Бангалор, Индия, 19–21 декабря 1989 г., Труды , конспекты лекций по информатике , том. 405, Springer-Verlag, стр. 30–43, номер документа : 10.1007/3-540-52048-1_30 , MR   1048636 .
• Маркензон, Л.; Жюстел, CM; Пасиорник, Н. (2006), «Подклассы k -деревьев: характеристика и распознавание», Discrete Applied Mathematics , 154 (5): 818–825, doi : 10.1016/j.dam.2005.05.021 , MR   2207565 .
• Мондал, Дебаджьоти; Нишат, Рахнума Ислам; Рахман, штат Мэриленд Саидур; Алам, Мухаммад Джавахерул (2010), «Чертежи плоских трехдеревьев минимальной площади», Канадская конференция по вычислительной геометрии (PDF) .
• Мун, Дж.В.; Мозер, Л. (1963), «Простые пути на многогранниках» , Pacific Journal of Mathematics , 13 (2): 629–631, doi : 10.2140/pjm.1963.13.629 , MR   0154276 .
• Нишат, Рахнума Ислам; Мондал, Дебаджьоти; Рахман, доктор медицины Саидур (2011), «Вложения плоских трехдеревьев в множество точек», Рисование графов, 18-й Международный симпозиум, GD 2010, Констанц, Германия, 21–24 сентября 2010 г., Пересмотренные избранные статьи , Конспекты лекций на компьютере Наука, том. 6502, Springer-Verlag, стр. 317–328, номер документа : 10.1007/978-3-642-18469-7_29 .
• Нишизеки, Такао (1980), «1-жесткий негамильтонов максимальный плоский граф», Discrete Mathematics , 30 (3): 305–307, doi : 10.1016/0012-365X(80)90240-X , MR   0573648 .
• Патил, HP (1986), «О структуре k -деревьев», Журнал комбинаторики, информации и системных наук , 11 (2–4): 57–64, MR   0966069 .
• Петерсен, Юлиус (1891), «Теория регулярных графов», Acta Mathematica , 15 : 193–220, doi : 10.1007/BF02392606 .
• Пламмер, Майкл Д. (1992), «Расширение паросочетаний в плоских графах IV», Discrete Mathematics , 109 (1–3): 207–219, doi : 10.1016/0012-365X(92)90292-N , MR   1192384 .
• Политоф, Т. (1983), Характеристика и эффективный расчет надежности приводимых Δ-Y сетей , доктор философии. диссертация, Калифорнийский университет, Беркли . Цитируется Эль-Маллахом и Колборном (1990) .
• Робертсон, Нил ; Сеймур, П.Д. (1984), «Минорные графы. III. Ширина плоского дерева», Журнал комбинаторной теории , серия B, 36 (1): 49–64, doi : 10.1016/0095-8956(84)90013-3 , МР   0742386 .
• Такео, Фудзио (1960), «О триангулированных графах. I», Bull. Фукуокский университет Гакугеи. III , 10 :9–21, МР   0131372 . На ошибку, касающуюся гамильтоновости, указал MathSciNet обозреватель WT Tutte .
• Терстон, Уильям (1978–1981), Геометрия и топология трехмерных многообразий , конспект лекций в Принстоне .
• Цуракакис, Харалампос Э. (2011), Степенная последовательность случайных аполлоновых сетей , arXiv : 1106.1940 .
• Вуд, Дэвид Р. (2007), «О максимальном количестве клик в графе», Graphs and Combinatorics , 23 (3): 337–352, arXiv : math/0602191 , doi : 10.1007/s00373-007-0738- 8 , МР   2320588 , S2CID   46700417 .
• Чжан, Чжунчжи; Чен, Личао; Чжоу, Шуйген; Фанг, Луджун; Гуань, Цзихун; Цзоу, Тао (2008), «Аналитическое решение средней длины пути для аполлоновых сетей», Physical Review E , 77 (1): 017102, arXiv : 0706.3491 , Bibcode : 2008PhRvE..77a7102Z , doi : 10.1103/PhysRevE.77.017102 , ПМИД   18351964 , S2CID   30404208 .
• Чжоу, Тао; Ян, Банда; Ван, Бинг-Хонг (2005), «Максимальные плоские сети с большим коэффициентом кластеризации и степенным распределением степеней», Physical Review E , 71 (4): 046141, arXiv : cond-mat/0412448 , Bibcode : 2005PhRvE..71d6141Z , doi : 10.1103/PhysRevE.71.046141 , PMID   15903760 , S2CID   21740312 .
• Чжоу, Тао; Ян, Банда; Чжоу, Пэй-Лин; Фу, Чжун-Цянь; Ван, Бинг-Хонг (2004), Случайные аполлонические сети , arXiv : cond-mat/0409414v2 , Bibcode : 2004cond.mat..9414Z .
• Зикфельд, Флориан; Циглер, Гюнтер М. (2006), «Целочисленные реализации сложенных многогранников», Семинар по геометрической и топологической комбинаторике (PDF) .

Внешние ссылки

• Вайсштейн, Эрик В. , «Аполлонианская сеть» , MathWorld
• Код моделирования Matlab