График Ламана

Шпиндель Мозера , плоский граф Ламана, изображенный как точечная псевдотриангуляция Полный двудольный граф K 3,3, неплоский граф Ламана

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

• 1 Жесткость
• 2 Планарность
• 3 Редкость
• 4 Конструкция Хеннеберга
• 5 Ссылки

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

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

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

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

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

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

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

Конструкция Хеннеберга веретена Мозера

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

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

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