Вложение Тутте

В графе рисунке и геометрической теории графов , A Тутта вложения или барицентрическое вложение из простого 3-вершинных-связных плоского графа является переходом свободного от прямой линии вложения со свойствами , что наружная поверхность представляет собой выпуклый многоугольник , и что каждая внутренняя вершина в среднем (или в барицентре) позиций своих соседей. Если внешний многоугольник зафиксирован, это условие на внутренние вершины однозначно определяет их положение как решение системы линейных уравнений . Геометрическое решение уравнений дает плоское вложение .Теорема Тутте о пружине , доказанная В. Т. Тутте  ( 1963 ), утверждает, что это единственное решение всегда не имеет перекрестков, и, что более важно, каждая грань полученного плоского вложения выпукла. ^[1] Это называется теоремой о пружине, потому что такое вложение может быть найдено как положение равновесия для системы пружин, представляющих ребра графа.

Пример [ править ]

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

Пусть G - график куба, и (выбрав одну из его четырехугольных граней в качестве внешней) зафиксируйте четыре вершины внешней грани в четырех углах единичного квадрата , точки, координаты x и y которых являются всеми четырьмя комбинациями нуля и единицы. Затем, если остальные четыре вершины поместить в четыре точки, координаты x и y которых являются комбинациями 1/3 и 2/3, как на рисунке, результатом будет вложение Тутте. Ведь в каждой внутренней вершине v вложения и для каждой из двух координат три соседа v имеют значения координат, равные v, меньше на 1/3 и больше на 1/3; среднее значение этих значений совпадает с координатой самого v .

Система линейных уравнений [ править ]

Условие , что вершина v будет на среднем позиции своих соседей может быть выраженно в виде двух линейных уравнений , один для й  координаты  V , а другие для у  координаты  V . Для графа с n вершинами, h из которых зафиксированы в позиции на внешней грани, есть два уравнения для каждой внутренней вершины, а также два неизвестных (координаты) для каждой внутренней вершины. Следовательно, это дает систему линейных уравнений с 2 ( n  -  h ) уравнениями в 2 ( n  -  h) неизвестных, решением которых является вложение Тутте. Как показал Тутте (1963) , для трехвершинно-связных плоских графов эта система невырождена. Следовательно, у него есть единственное решение, и (с фиксированной внешней гранью) граф имеет единственное вложение Тутта. Это вложение может быть найдено за полиномиальное время путем решения системы уравнений, например, с помощью исключения Гаусса . ^[2]

Многогранное представление [ править ]

По теореме Стейница 3-связные плоские графы, к которым применяется теорема Тутте о пружине, совпадают с многогранными графами , графами, образованными вершинами и ребрами выпуклого многогранника . Согласно соответствию Максвелла – Кремоны , двумерное вложение плоского графа образует вертикальную проекцию трехмерного выпуклого многогранника тогда и только тогда, когда вложение имеет равновесное напряжение, назначение сил каждому ребру (влияющих на обе конечные точки в равных и противоположных направлениях, параллельных ребру), так что силы компенсируются в каждой вершине. Для вложения Тутте присвоение каждому ребру силы притяжения, пропорциональной его длине (как у пружины), заставляет силы сокращаться во всех внутренних вершинах, но это не обязательно является равновесным напряжением в вершинах внешнего многоугольника. Однако, когда внешний многоугольник представляет собой треугольник, можно назначить силы отталкивания его трем краям, чтобы силы отталкивались и там. Таким образом, вложения Тутте можно использовать для нахождения диаграмм Шлегеля для каждого выпуклого многогранника . Для каждого 3-связного планарного графа G , либо G сам по себе или двойственному графугруппы G имеет треугольник, так что либо это дает полиэдральное представление группы G или ее двойственного; в том случае, двойственный граф является один с треугольником, поляризация дает многогранное представление G самому. ^[2]

Приложения в обработке геометрии [ править ]

При обработке геометрии вложение Тутте используется для 2D УФ- параметризации 3D-поверхностей чаще всего в тех случаях, когда топология поверхности остается одинаковой по и (топология диска). Метод Тутте минимизирует общую энергию искажения параметризованного пространства, рассматривая каждую преобразованную вершину как точечную массу, а ребра через соответствующие вершины как пружины. Плотность каждой пружины определяется длиной кромок исходной трехмерной поверхности для сохранения формы. Поскольку разумно иметь меньшие параметризованные длины кромок для меньших кромок и большие параметризованные длины кромок для больших кромок пружинных постоянных${\ Displaystyle {\ mathcal {S}} ^ {*}}$${\ Displaystyle {\ mathcal {S}}}$${\ Displaystyle {\ mathcal {S}}}$${\ Displaystyle {\ mathcal {S}} ^ {*}}$${\ Displaystyle {\ mathcal {S}}}$${\ Displaystyle {\ mathcal {S}}}$${\ displaystyle w_ {ij}}$обычно считаются обратным абсолютному расстоянию между вершинами в трехмерном пространстве.${\ displaystyle i, ~ j}$

${\displaystyle {\text{Distortion Energy,}}~E=\Sigma _{(i,j)\in E({\mathcal {S}})}~w_{ij}~\|{\textbf {u}}_{\text{i}}-{\textbf {u}}_{\text{j}}\|^{2}{\text{, where }}w_{ij}={\frac {1}{\|{\textbf {v}}_{\text{i}}-{\textbf {v}}_{\text{j}}\|}}{\text{, }}\{{\textbf {u}}_{\text{i}}\}\in {\mathcal {S}}^{*}{\text{, }}\{{\textbf {v}}_{\text{i}}\}\in {\mathcal {S}}}$

где представляет собой набор ребер в исходной 3D-поверхности. Когда веса положительны (как в случае выше), гарантируется, что отображение биективно без каких-либо инверсий. Но когда никакие дальнейшие ограничения не применяются, решение, которое минимизирует энергию искажения, тривиально сворачивается в единственную точку параметризованного пространства. ${\displaystyle E({\mathcal {S}})}$${\displaystyle w_{ij}}$

Следовательно, необходимо обеспечить граничные условия, при которых набор известных вершин трехмерной поверхности отображается в известные точки в параметризованном двумерном пространстве. Одним из распространенных способов выбора таких граничных условий является рассмотрение вершин на наибольшем граничном контуре исходной трехмерной поверхности, которая затем может быть ограничена для отображения на внешнее кольцо единичного диска в параметризованном двумерном пространстве. Обратите внимание, что если трехмерная поверхность является многообразием, граничные края можно обнаружить, убедившись, что они принадлежат только одной грани сетки.

Приложения параметризации в графике и анимации включают, среди прочего, наложение текстур.

Обобщения [ править ]

Колин де Вердьер (1991) обобщил теорему Тутта о пружине на графы на поверхностях высшего рода с неположительной кривизной , где ребра представлены геодезическими . ^[3] результаты , аналогичные для графиков встраиваемых на торе были независимо друг от друга доказано Delgado-Фридрихса (2005) , ^[4] с помощью Gortler, Гоцман & Thurston (2006) , ^[5] и Lovász (2019) . ^[6]

Чилакамарри, Дин и Литтман (1995) исследуют вложения трехмерных графов графов четырехмерных многогранников , образованных тем же методом, что и вложение Тутте: выберите одну грань многогранника как внешнюю грань трехмерного вложения, и зафиксируем его вершины на месте как вершины трехмерного многогранника в пространстве. Пусть каждая оставшаяся вершина многогранника может свободно перемещаться в пространстве, и заменим каждое ребро многогранника пружиной. Затем найдите конфигурацию системы пружин с минимальной энергией. Как они показывают, полученная таким образом система уравнений снова невырождена, но неясно, при каких условиях этот метод найдет вложение, реализующее все грани многогранника как выпуклые многогранники. ^[7]

Похожие результаты [ править ]

Результат, заключающийся в том, что любой простой плоский граф может быть нарисован с прямыми ребрами, называется теоремой Фари . ^[8] Теорема Тутте о пружине доказывает это для трехсвязных плоских графов, но в более общем случае результат верен для плоских графов независимо от связности. Использование пружинной системы Тутте для графа, который не является 3-связным, может привести к вырождению, при котором подграфы данного графа схлопываются в точку или отрезок линии; однако произвольный планарный граф можно нарисовать с помощью вложения Тутте, добавив дополнительные ребра, чтобы сделать его 3-связным, нарисовав получившийся 3-связный граф, а затем удалив лишние ребра.

Граф является k- вершинно-связным , но не обязательно планарным, тогда и только тогда, когда он имеет выпуклое вложение в ( k -  1) -мерное пространство, в котором произвольный k -набор вершин помещены в вершины симплекса и , для каждой оставшейся вершины V , то выпуклая оболочка из соседей  V полна одномерная с V в его интерьере. Если такое вложение существует, его можно найти, зафиксировав расположение выбранных k вершин и решив систему уравнений, которая помещает каждую вершину в среднее значение ее соседей, как в плоском вложении Тутта. ^[9]

В конечных элементах генерации сетки , лапласиан сглаживание является распространенным методом для постобработки сгенерированных сеток , чтобы улучшить качество его элементов; ^[10] он особенно популярен для четырехугольных сеток , для которых другие методы, такие как алгоритм Ллойда для сглаживания треугольной сетки, менее применимы. В этом методе каждая вершина перемещается в или ближе к среднему положению ее соседей, но это движение выполняется только в течение небольшого количества итераций, чтобы избежать больших искажений размеров элементов или (в случае невыпуклых областей сетки ) запутанные неплоские сетки.

Системы рисования графов, ориентированных на силу , продолжают оставаться популярным методом визуализации графов, но в этих системах обычно используются более сложные системы сил, которые объединяют силы притяжения на ребрах графа (как во встраивании Тутта) с силами отталкивания между произвольными парами вершин. Эти дополнительные силы могут привести к тому, что система будет иметь множество локально стабильных конфигураций, а не единственное глобальное решение, как во встраивании Тутта. ^[11]

Ссылки [ править ]