라만 그래프

그래프 이론에서, 라만 그래프는 평면에서 로드와 이음매의 최소 경성 시스템을 설명하는 희소성 그래프 계열이다.형식적으로, 라만 그래프는 모든 k에 대해 모든 k-vertex 하위 그래프는 최대 2k - 3 에지를 가지며, 전체 그래프는 정확히 2n - 3 에지를 가지도록 n 꼭지점에 대한 그래프다.라만 그래프는 암스테르담 대학의 제라드 라만의 이름을 따온 것인데, 1970년 이 그래프를 단단한 평면 구조를 특징 짓는데 사용했다.^[1]그러나 이러한 특성화는 힐다 게이닝거에 의해 1927년에 이미 발견되었다.^[2]

경성

라만 그래프는 경직성 이론에서 발생한다: 일반적인 위치에 라만 그래프의 정점을 배치하면 일반적으로 모든 그래프 가장자리의 길이를 보존하는 유클리드 결합물을 제외한 모든 포인트의 연속적인 움직임이 동시에 일어나지 않는다.그래프는 모든 정점에 걸쳐 있는 Laman 하위 그래프를 가지고 있는 경우에만 이러한 의미에서 강직하다.따라서, Laman 그래프는 정확히 최소 경성 그래프로서, 2차원 경성 매트로이드의 기초를 형성한다.

평면에 n개의 점이 주어진 경우 배치에는 2n의 자유도(각 점에는 두 개의 독립적인 좌표가 있음)가 있지만, 경직된 그래프는 3개의 자유도(정점 중 하나의 위치 및 그 정점을 중심으로 한 나머지 그래프의 회전)만 가진다.직관적으로 그래프에 고정된 길이의 가장자리를 추가하면 자유도가 1씩 감소하므로, 라만 그래프에서 2n - 3 가장자리는 초기 포인트 배치의 자유도가 3도 정도로 감소한다.단, 가장자리가 2n - 3인 모든 그래프가 경직된 것은 아니다. 하위 그래프가 너무 많은 가장자리를 가질 수 없다는 Laman 그래프의 정의의 조건은 각 가장자리가 전체 자유도 감소에 기여함을 보장하며, 다른 가장자리로 인해 이미 경직된 하위 그래프 내에서 낭비되지 않는다.

평면성

뾰족한 가성비는 그래프의 평면 직선 그림으로, 바깥 면은 볼록하고, 경계면은 모두 가성각이며, 볼록 정점이 3개만 있는 다각형이며, 모든 정점에 입사하는 가장자리가 180도 미만의 각도를 이룬다.뾰족한 가성 계수로 그릴 수 있는 그래프는 정확히 평면 라만 그래프다.^[3]그러나 라만 그래프는 가성비가 아닌 평면 임베딩이 있고, 효용 그래프 K와_3,3 같이 평면형이 아닌 라만 그래프가 있다.

스파르시티

이 대통령&Streinu(2008년)과 Streinu &, 이로써(k, 나는){\displaystyle(k,l)}-sparse 만약 n{n\displaystyle}vertices과 매주 비공의 부분 그래프 가장 k n− 나는{\displaystyle kn-l}가장자리만 가지고 있는 Theran(2009년)고,(k, 나는){\displaystyle(k,l)}-tight{\displaystyle(k,l)}(k, 나는)그래프를 정의합니다. -sparse정확히 $k{\displaystyle }$ -${\displaystyle l}$ ${\displaystyle kn-l}$개의 가장자리가$$ 있다.따라서 이들의 표기법에서 라만 그래프는 정확하게 (2,3)밀도 그래프이고, 라만 그래프의 하위 그래프는 정확하게 (2,3)-스파스 그래프다.나무, 사이비숲, 경계가 있는 수목형 그래프를 포함한 희소성 그래프의 다른 중요한 집단을 설명하는 데 동일한 표기법을 사용할 수 있다.^[4][5]

이러한 특성화를 바탕으로 정점이 없고 가장자리가 없는 그래프로 시작하는 '페블 게임'을 각 꼭지점에 2개의 자갈이 배치되어 시뮬레이션하고, 다음 두 종류의 스텝 순서를 수행하여 그래프의 모든 가장자리를 O(n²) 시간에 n-Vertex Laman 그래프를 인식할 수 있다.

• 두 개의 자갈이 있는 두 꼭지점을 연결하는 새 방향 가장자리를 만들고 새 가장자리의 시작 꼭지점에서 하나의 자갈을 제거한다.
• 한 개의 조약돌이 있는 꼭지점 u에서 한 개 이상의 조약돌이 있는 다른 꼭지점 v로 가장자리가 가리키는 경우, 조약돌을 v에서 u로 이동하고 가장자리를 반전시킨다.

이러한 연산을 사용하여 주어진 그래프의 방향을 구성할 수 있다면, 반드시 (2,3)-sparse이고, 그 반대의 경우도 마찬가지다.However, faster algorithms are possible, running in time ${\displaystyle O(n^{3/2}{\sqrt {\log n}})}$, based on testing whether doubling one edge of the given graph results in a multigraph that is (2,2)-tight (equivalently, whether it can be decomposed into two edge-disjoint spanning trees) and then using this분해하여 지정된 그래프가 라만 그래프인지 확인하십시오.^[6]네트워크 흐름 기법을 사용하여 평면 그래프가 $시간{\displaystyle }$ O${\displaystyle (n}$ ${\displaystyle {\log }^{}}$ ${\displaystyle {3\mathrm{}}^{}}$ ${\displaystyle {}^{}n}$) ${\displaystyle O(n\log ^{3}n)}$에 있는 Laman 그래프인지 여부를 보다 신속하게 테스트할 수 있다$.$^[7]

헤네베르크 건설

레브레히트 헤네베르크[de]는 라만과 게링거의 작품 이전에 다른 방식으로 2차원 최소 경직성 그래프(즉, 라만 그래프)를 특징지었다.^[8]Henneberg는 두 개 이상의 정점에 최소 경직성 그래프가 정확히 단일 에지에서 시작하여 다음 두 가지 유형의 연산을 통해 얻을 수 있는 그래프임을 보여주었다.

1. 그래프를 이전의 두 정점에 연결하는 가장자리와 함께 그래프에 새 정점을 추가하십시오.
2. 그래프의 가장자리를 세분화하고 새로 형성된 정점을 이전에 존재하는 세 번째 정점에 연결하는 가장자리를 추가하십시오.

주어진 그래프를 구성하는 일련의 작업을 헤네베르크 그래프 구조라고 한다.예를 들어, 완전한 초당적 그래프 K는_3,3 첫 번째 연산을 사용하여 삼각형을 형성한 다음 두 번째 연산을 적용하여 삼각형의 각 가장자리를 세분화하고 각 분할점을 반대 삼각형 꼭지점으로 연결할 수 있다.

참조