Граф Ламана

— Веретено Мозера планарный граф Ламана, нарисованный в виде заостренной псевдотриангуляции.

Полный двудольный граф K _3,3 , непланарный граф Ламана

В теории графов графы Ламана представляют собой семейство разреженных графов, описывающих минимально жесткие системы стержней и соединений на плоскости. Формально граф Ламана — это граф на n вершинах, такой, что для всех k каждый подграф k -вершин имеет не более 2 k − 3 ребер и такой, что весь граф имеет ровно 2 n − 3 ребра. Графы Ламана названы в честь Жерара Ламана из Амстердамского университета , который в 1970 году использовал их для характеристики жестких плоских структур. Однако эта характеристика, теорема Гейрингера-Ламана , была открыта уже в 1927 году Хильдой Гейрингер .

Жесткость

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

Если даны n точек на плоскости, то имеется 2n степеней свободы в их расположении (каждая точка имеет две независимые координаты), а жёсткий граф имеет только три степени свободы (положение одной его вершины и вращение оставшегося графа вокруг этой вершины).Интуитивно понятно, что добавление ребра фиксированной длины в граф уменьшает количество степеней свободы на одну, поэтому 2 n - 3 ребра в графе Ламана уменьшают 2 n степеней свободы исходного размещения точки до трех степеней свободы. жесткого графа. Однако не каждый граф с 2 n − 3 ребрами является жестким; условие в определении графа Ламана, согласно которому ни один подграф не может иметь слишком много ребер, гарантирует, что каждое ребро способствует уменьшению общего числа степеней свободы и не тратится впустую внутри подграфа, который сам по себе уже является жестким из-за других ребер.

Планарность

— Заостренная псевдотриангуляция это плоский прямой рисунок графа со свойствами, что внешняя грань выпукла, что каждая ограниченная грань является псевдотреугольником , многоугольником только с тремя выпуклыми вершинами и что ребра, инцидентные каждой вершине, охватывают угол менее 180 градусов. Графы, которые можно нарисовать в виде точечных псевдотриангуляций, представляют собой в точности планарные графы Ламана. Однако графы Ламана имеют плоские вложения, которые не являются псевдотриангуляциями, и существуют неплоские графы Ламана, такие как граф полезности K _3,3 .

Разреженность

Ли и Стрейну (2008) и Стрейну и Теран (2009) определяют граф как $(k,\ell )$-разреженный, если каждый непустой подграф с $n$ вершин имеет не более $kn-\ell$ края, и $(k,\ell )$- тесно, если так $(k,\ell )$- разреженный и имеет ровно $kn-\ell$ края. Таким образом, в своих обозначениях графы Ламана являются в точности (2,3)-плотными графами, а подграфы графов Ламана являются в точности (2,3)-разреженными графами. Те же обозначения можно использовать для описания других важных семейств разреженных графов , включая деревья , псевдолеса и графы ограниченной древесности .

На основе этой характеристики можно распознать n -вершинные графы Ламана за время O ( n ² ) , моделируя «игру с камешками», которая начинается с графа с n вершинами и без ребер, с двумя камешками, помещенными в каждую вершину, и выполняет последовательность следующих двух типов шагов для создания всех ребер графа:

• Создайте новое направленное ребро, соединяющее любые две вершины, в каждой из которых есть по два камушка, и удалите один камешек из начальной вершины нового ребра.
• Если ребро указывает из вершины u , в которой находится не более одного камешка, в другую вершину v , в которой есть хотя бы один камешек, переместите камешек из вершины v в u и переверните ребро.

Если с помощью этих операций можно построить ориентацию данного графа, то он обязательно (2,3)-разреженный, и наоборот.Однако возможны более быстрые алгоритмы, работающие во времени. $O(n^{3/2}{\sqrt {\log n}})$, основанный на проверке того, приводит ли удвоение одного ребра данного графа к (2,2)-плотному мультиграфу (эквивалентно, можно ли его разложить на два непересекающихся по ребрам остовных дерева ), а затем с помощью этого разложения проверить, является ли данный граф является графом Ламана. Методы сетевого потока можно использовать для ли плоский граф графом Ламана. более быстрой и своевременной проверки того, является $O(n\log ^{3}n)$.

Строительство Хеннеберга

Хеннебергская конструкция шпинделя Мозера

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

1. Добавьте в граф новую вершину вместе с ребрами, соединяющими ее с двумя ранее существовавшими вершинами.
2. Разделите ребро графа и добавьте ребро, соединяющее вновь сформированную вершину с третьей ранее существовавшей вершиной.

Последовательность этих операций, образующая данный граф, известна как Хеннеберга конструкция графа .Например, полный двудольный граф K _3,3 может быть сформирован с использованием первой операции для формирования треугольника, а затем применения второй операции для разделения каждого ребра треугольника и соединения каждой точки подразделения с противоположной вершиной треугольника.