График Ламана - Laman graph

Moser шпинделя , плоский Ламаном график рисуется в виде заостренного pseudotriangulation

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

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

Жесткость

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

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

Планарность

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

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

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

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

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

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

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

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

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

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

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

использованная литература