안둘레

3. 성질

임의의 그래프 $\backslash \{\backslash Gamma\_i\backslash \}\_\{i\backslash in\; I\}$에 대하여, 다음이 성립한다.

:$\backslash operatorname\{girth\}\backslash left(\backslash bigsqcup\_\{i\backslash in\; I\}\backslash Gamma\_i\backslash right)=\backslash min\_\{i\backslash in\; I\}\backslash operatorname\{girth\}\backslash Gamma\_i$

:$\backslash operatorname\{circ\}\backslash left(\backslash bigsqcup\_\{i\backslash in\; I\}\backslash Gamma\_i\backslash right)=\backslash sup\_\{i\backslash in\; I\}\backslash operatorname\{circ\}\backslash Gamma\_i$

:$\backslash operatorname\{girth\}\backslash left(\backslash operatorname\{M\_B\}\backslash left(\backslash bigsqcup\_\{i\backslash in\; I\}\backslash Gamma\_i\backslash right)\backslash right)=\backslash min\_\{i\backslash in\; I\}\backslash operatorname\{girth\}\backslash operatorname\{M\_B\}(\backslash Gamma\_i)$

:$\backslash operatorname\{circ\}\backslash left(\backslash operatorname\{M\_B\}\backslash left(\backslash bigsqcup\_\{i\backslash in\; I\}\backslash Gamma\_i\backslash right)\backslash right)=\backslash sup\_\{i\backslash in\; I\}\backslash operatorname\{circ\}\backslash operatorname\{M\_B\}(\backslash Gamma\_i)$

여기서 $\backslash textstyle\backslash bigsqcup$는 그래프의 분리합집합이다.

꼭짓점이 n^영어개인 유한 그래프의 밖둘레는 n^영어 이하이며, 이 상계는 해밀턴 순환에 의하여 포화된다. 즉, 밖둘레가 n^영어인 것은 해밀턴 순환을 갖는 것과 동치이다.

차수가 r^영어인 정규 그래프 Γ^영어에 대하여, 다음 부등식이 성립한다.

이 부등식을 포화시키는 정규 그래프를 '''무어 그래프'''(Moore graph^영어)라고 한다.

3. 1. 분리합집합

3. 2. 상계

이 부등식을 포화시키는 정규 그래프를 '''무어 그래프'''(Moore graph^영어)라고 한다.

4. 케이지 (Cage)

둘레가 *g*인 큐빅 그래프(모든 꼭지점의 차수가 3인 그래프) 중 가장 작은 그래프를 *g*-케이지 (또는 (3,*g*)-케이지)라고 한다. 피터슨 그래프는 유일한 5-케이지(둘레가 5인 가장 작은 큐빅 그래프)이며, 히우드 그래프는 유일한 6-케이지, 맥기 그래프는 유일한 7-케이지, 투테 8-케이지는 유일한 8-케이지이다.^[3] 주어진 둘레에 대해 여러 개의 케이지가 존재할 수 있는데, 예를 들어 꼭지점이 70개인 비동형 10-케이지에는 발라반 10-케이지, 해리스 그래프, 해리스-웡 그래프가 있다.

5. 둘레와 그래프 채색

에르되스 팔은 확률적 방법을 사용하여, 임의의 양의 정수 g와 χ에 대해, 안둘레가 g 이상이고 채색수가 χ 이상인 그래프가 존재함을 증명하였다.^[4] 그는 n개의 정점에 대한 랜덤 그래프를, 각 변을 포함할지 여부를 확률 n^(1-g)/g로 독립적으로 선택하여 형성할 경우, n이 무한대로 갈 때 확률이 1로 수렴하면서, 길이 g 이하의 순환이 최대 n/2개이지만, 크기가 n/2k인 독립 집합이 없음을 보였다. 따라서 각 짧은 순환에서 하나의 정점을 제거하면 둘레가 g보다 큰 더 작은 그래프가 남으며, 이 그래프에서 채색의 각 색상 클래스는 작아야 하므로 어떤 채색에서도 최소 k개의 색상이 필요하다.

높은 둘레와 채색수를 갖는 명시적인 그래프는, 유한체 상의 선형 군의 특정 케일리 그래프로 구성될 수 있다.^[5] 이러한 그래프는 ''라마누잔 그래프''라고 불리며, 큰 확장 계수를 갖는다.

6. 관련 개념

그래프의 '''홀수 둘레'''와 '''짝수 둘레'''는 각각 최단 홀수 순환과 최단 짝수 순환의 길이이다. 한국어로는 각각 '''기내주'''(odd girth) 및 '''우내주'''(even girth)라고도 한다.

둘레는 수축 기하학(시스톨릭 기하학)에서 1-수축(1-systole) 또는 더 높은 수축으로 일반화될 수 있다.^[6]

7. 계산

무방향 그래프의 둘레는 각 노드에서 너비 우선 탐색을 실행하여 계산할 수 있으며, 복잡도는 $O(nm)$이다. 여기서 $n$은 그래프의 정점 수이고, $m$은 모서리 수이다.^[7] 실용적인 최적화 방법으로는 너비 우선 탐색의 깊이를 지금까지 발견된 가장 작은 사이클의 길이에 따라 달라지는 깊이로 제한하는 것이 있다.^[8] 둘레가 짝수인 경우^[9]와 그래프가 평면 그래프인 경우^[10]에는 더 나은 알고리즘이 알려져 있다. 하한 측면에서 그래프의 둘레를 계산하는 것은 그래프에서 삼각형 찾기 문제를 해결하는 것만큼 어렵다.

참조

_[1] 서적 Graph Theory Springer-Verlag
_[2] MathWorld Girth
_[3] 간행물 Cages http://www.win.tue.n[...]
_[4] 간행물 Graph theory and probability
_[5] 간행물 Elementary number theory, group theory, and Ramanujan graphs Cambridge University Press, Cambridge
_[6] 간행물 On the (co)girth of a connected matroid
_[7] 웹사이트 Question 3: Computing the girth of a graph http://webcourse.cs.[...] 2023-02-22
_[8] 웹사이트 Shortest cycle https://tryalgo.org/[...] 2016-11-06
_[9] 웹사이트 ds.algorithms - Optimal algorithm for finding the girth of a sparse graph? https://cstheory.sta[...] 2023-02-22
_[10] 학술지 Computing the Girth of a Planar Graph in Linear Time 2013
_[11] 서적 Graph Theory Springer-Verlag
_[12] 간행물 Girth -- Wolfram MathWorld http://mathworld.wol[...]
_[13] 간행물 Cages http://www.win.tue.n[...]
_[14] 간행물 Graph theory and probability
_[15] 저널
_[16] 저널 Sur les assemblages de lignes http://resolver.sub.[...]