Вложение Тутте
В рисовании графов и геометрической теории графов вложение Тутте или барицентрическое вложение простого , 3 -вершинно-связного планарного графа представляет собой прямолинейное вложение без пересечений со свойствами, что внешняя грань является выпуклым многоугольником , а каждая внутренняя вершина находится в среднем (или барицентре) позиций своих соседей. Если внешний многоугольник фиксирован, то это условие на внутренние вершины однозначно определяет их положение как решение системы линейных уравнений . Геометрическое решение уравнений даетпланарное вложение . Теорема Татта о пружинах , доказанная В. Т. Таттом ( 1963 ), утверждает, что это уникальное решение всегда не имеет пересечений, и, что более строго, каждая грань результирующего плоского вложения выпукла. [1] Это называется теоремой о пружинах, потому что такое вложение может быть найдено как положение равновесия для системы пружин , представляющих ребра графа.
Пусть G будет графом куба, и (выбрав одну из его четырехугольных граней в качестве внешней грани) зафиксируйте четыре вершины внешней грани в четырех углах единичного квадрата , точки, координаты x и y которых являются всеми четырьмя комбинациями нуля и единицы. Затем, если оставшиеся четыре вершины разместить в четырех точках, координаты x и y которых представляют собой комбинации 1/3 и 2/3, как на рисунке, результатом будет вложение Тутте. Действительно, в каждой внутренней вершине v вложения и для каждой из двух координат три соседа v имеют значения координат, равные v, меньше на 1/3 и больше на 1/3; среднее значение этих значений совпадает со значением координаты самой v .
Условие того, что вершина v находится в среднем положении своих соседей, может быть выражено в виде двух линейных уравнений , одно для координаты x вершины v , а другое для координаты y вершины v . Для графа с n вершинами, h из которых фиксированы на внешней грани, имеется два уравнения для каждой внутренней вершины, а также две неизвестные (координаты) для каждой внутренней вершины. Следовательно, это дает систему линейных уравнений с 2( n − h ) уравнениями относительно 2( n − h) неизвестных, решением которых является вложение Тутте. Как показал Tutte (1963) , для трехвершинно-связных планарных графов эта система невырождена. Следовательно, он имеет единственное решение, и (при фиксированной внешней грани) граф имеет единственное вложение Тутте. Это вложение можно найти за полиномиальное время , решив систему уравнений, например, методом исключения Гаусса . [2]
По теореме Стейница 3-связные плоские графы, к которым применяется пружинная теорема Тутте, совпадают с многогранными графами , графами, образованными вершинами и ребрами выпуклого многогранника . Согласно соответствию Максвелла–Кремоны , двумерное вложение плоского графа образует вертикальную проекцию трехмерного выпуклого многогранника тогда и только тогда, когда вложение имеет равновесное напряжение, назначение сил каждому ребру (воздействующих на обе конечные точки в равных и противоположных направлениях, параллельных ребру), так что силы сокращаются в каждой вершине. Для вложения Тутте назначение каждому ребру силы притяжения, пропорциональной его длине (например, пружины), заставляет силы сокращаться во всех внутренних вершинах, но это не обязательно является равновесным напряжением в вершинах внешнего многоугольника. Однако, когда внешний многоугольник представляет собой треугольник, можно присвоить силам отталкивания три его края, чтобы силы там тоже компенсировались. Таким образом, вложения Тутте можно использовать для нахождения диаграмм Шлегеля каждого выпуклого многогранника . Для каждого 3-связного планарного графа G либо сам G , либо двойственный графG имеет треугольник, поэтому либо это дает многогранное представление G , либо двойственное ему; в случае, когда двойственный граф - это граф с треугольником, поляризация дает полиэдральное представление самой G. [2]
