В теории графов , то Laman графики представляют собой семейство разреженных графов , описывающих минимально жесткие системы стержней и соединений в плоскости. Формально граф Ламана - это граф с n вершинами, такой, что для всех k каждый подграф с k- вершинами имеет не более 2 k - 3 ребер, и такой, что весь граф имеет ровно 2 n - 3 ребра. Laman графики имя Gerard Ламана , из Амстердамского университета , который в 1970 году использовал их для характеристики жестких плоских структур. [1]Эта характеристика, однако, была открыта еще в 1927 году Хильдой Гейрингер . [2]
Жесткость
Графы Ламана возникают в теории жесткости : если разместить вершины графа Ламана на евклидовой плоскости в общем положении , в общем случае не будет одновременного движения всех точек, кроме евклидовых сравнений , которое сохраняет длины всех ребра графа. Граф является жестким в этом смысле тогда и только тогда, когда он имеет подграф Ламана, охватывающий все его вершины. Таким образом, графы Ламана - это в точности минимально жесткие графы, и они составляют основу двумерных матроидов жесткости .
Если задано n точек на плоскости, то имеется 2 n степеней свободы в их размещении (каждая точка имеет две независимые координаты), но жесткий граф имеет только три степени свободы (положение одной из его вершин и вращение оставшегося графа вокруг этой вершины). Интуитивно понятно, что добавление ребра фиксированной длины к графу уменьшает его количество степеней свободы на одну, поэтому 2 n - 3 ребра в графе Ламана уменьшают 2 n степеней свободы размещения начальной точки до трех степеней свободы. жесткого графа. Однако не всякий граф с 2 n - 3 ребрами является жестким; условие в определении графа Ламана о том, что ни один подграф не может иметь слишком много ребер, гарантирует, что каждое ребро способствует уменьшению общего числа степеней свободы и не тратится впустую в подграфе, который уже сам по себе является жестким из-за других его ребер.
Планарность
Заостренные pseudotriangulation является плоской прямой линии рисования графа, со свойствами , что наружная поверхность является выпуклой, что каждое ограниченное лицо является pseudotriangle , многоугольник только с тремя выпуклыми вершинами, и что ребра , инцидентные каждой вершины диапазона ап угол менее 180 градусов. Графы, которые можно нарисовать как точечные псевдотриангуляции, в точности являются планарными графами Ламана. [3] Однако графы Ламана имеют плоские вложения, которые не являются псевдотриангуляциями, и есть графы Ламана, которые не являются планарными, например граф полезности K 3,3 .
Разреженность
Ли и Стрейну (2008) и Стрейну и Теран (2009) определяют граф как-разрежьте, если каждый непустой подграф с вершин не более края и - герметично, если это - разреженный и ровно края. Таким образом, в своих обозначениях графы Ламана являются в точности (2,3) -плотными графами, а подграфы графов Ламана являются в точности (2,3)-разреженными графами. Эти же обозначения можно использовать для описания других важных семейств разреженных графов , включая деревья , псевдолеса и графы ограниченной древовидности . [4] [5]
Основываясь на этой характеристике, можно распознать n- вершинные графы Ламана за время O ( n 2 ) , моделируя "игру в камешки", которая начинается с графа с n вершинами и без ребер, с двумя камешками, помещенными на каждую вершину, и выполняет последовательность следующих двух шагов для создания всех ребер графа:
- Создайте новое направленное ребро, соединяющее любые две вершины, каждая из которых имеет по два камня, и удалите один камень из начальной вершины нового ребра.
- Если ребро указывает из вершины u с не более чем одним камешком на другую вершину v с хотя бы одним камешком, переместите камень из v в u и переместите край.
Если эти операции можно использовать для построения ориентации данного графа, то он обязательно (2,3) -разреженный, и наоборот. Однако возможны более быстрые алгоритмы, работающие во времени., основанный на проверке того, приводит ли удвоение одного ребра данного графа к (2,2) -плотному мультиграфу (эквивалентно, может ли он быть разложен на два непересекающихся по ребрам остовных деревьев ), а затем с использованием этого разложения для проверки того, является ли данный граф является графом Ламана. [6]
Строительство Хеннеберга
До работы Ламана и Гейрингера Лебрехт Хеннеберг [7] Хеннеберг показал, что минимально жесткие графы на двух или более вершинах - это именно те графы, которые могут быть получены, начиная с одного ребра, с помощью последовательности операций следующих двух типов:
по-другому охарактеризовал двумерные минимально жесткие графы (то есть графы Ламана).- Добавьте новую вершину в граф вместе с ребрами, соединяющими ее с двумя ранее существовавшими вершинами.
- Разделите ребро графа и добавьте ребро, соединяющее вновь образованную вершину с третьей ранее существовавшей вершиной.
Последовательность этих операций, образующая данный граф, называется конструкцией графа Хеннеберга . Например, полный двудольный граф K 3,3 может быть сформирован с использованием первой операции для формирования треугольника и последующего применения второй операции для подразделения каждого ребра треугольника и соединения каждой точки подразделения с противоположной вершиной треугольника.
Рекомендации
- ^ Ламан, Г. (1970), «О графах и жесткости плоских скелетных структур», J. Engineering Mathematics , 4 (4): 331–340, Bibcode : 1970JEnMa ... 4..331L , doi : 10.1007 / BF01534980 , Руководство по ремонту 0269535.
- ^ Поллачек-Гейрингер, Хильда (1927), «Über die Gliederung ebener Fachwerke», Zeitschrift für Angewandte Mathematik und Mechanik , 7 (1): 58–72.
- ^ Хаас, Рут ; Орден, Дэвид; Роте, Гюнтер; Сантос, Франциско ; Серватиус, Бриджит ; Серватий, Герман; Сувейн, Дайан ; Стрейну, Илеана ; Уайтли, Уолтер (2005), «Плоские минимально жесткие графы и псевдотриангуляции», Теория вычислительной геометрии и приложения , 31 (1-2): 31–61, arXiv : math / 0307347 , doi : 10.1016 / j.comgeo.2004.07 .003 , Руководство по ремонту 2131802.
- ^ Ли, Одри; Стрейну, Илеана (2008), «Игровые алгоритмы и разреженные графы», Дискретная математика , 308 (8): 1425–1437, arXiv : math / 0702129 , doi : 10.1016 / j.disc.2007.07.104 , MR 2392060.
- ^ Стрейну, И .; Теран, Л. (2009), "Разреженные гиперграфы и алгоритмы камешковой игры", Европейский журнал комбинаторики , 30 (8): 1944–1964, arXiv : math / 0703921 , doi : 10.1016 / j.ejc.2008.12.018.
- ^ Daescu, O .; Курдия, А. (2009), "На пути к оптимальному алгоритму распознавания графов Ламана", Proc. 42-я Гавайская международная конференция по системным наукам (HICSS '09) , IEEE, стр. 1–10, arXiv : 0801.2404 , doi : 10.1109 / HICSS.2009.470.
- ^ Хеннеберг, Л. (1911), Die graphische Statik der Starren Systeme , Лейпциг