안둘레

그래프 이론과 매트로이드 이론에서 **안둘레**(거스)는 그래프 또는 매트로이드 속의 가장 작은 “구멍”, 즉 최소의 순환의 크기이다. 마찬가지로 그래프 또는 매트로이드의 **밖둘레**(서컴퍼런스)는 최대의 순환의 크기이다.
# 정의

## 매트로이드
매트로이드 X의 회로들의 집합을 :\operatorname{Circ}(X)\subseteq\operatorname{Pow}(X) 라고 하자. 매트로이드 X의 안둘레는 그 회로의 크기의 최솟값이다. :\operatorname{girth}(X)=\min_{C\in\operatorname{Circ}(X)}|C|\in\\{\kappa\in\operatorname{Card}\colon\kappa\le|X|\\}\sqcup\\{+\infty\\} 여기서 \operatorname{Card}는 모든 기수들의 모임이다. 만약 회로가 존재하지 않는다면, 이 경우 안둘레를 형식적인 기호 +\infty로 정의한다. 매트로이드 X의 밖둘레는 그 회로의 크기의 최댓값이다. :\operatorname{circ}(X)=\max_{C\in\operatorname{Circ}(X)}|C|\in\\{\kappa\in\operatorname{Card}\colon\kappa\le|X|\\}\sqcup\\{-\infty\\} 만약 회로가 존재하지 않는다면, 이 경우 밖둘레를 형식적인 기호 -\infty로 정의한다.
## 그래프
임의의 다중 그래프 \Gamma의 변들의 집합 \operatorname E(\Gamma) 위에는 다음과 같은 두 매트로이드 구조를 줄 수 있다.언어=en§2.2 * (유한) **순환 매트로이드** \operatorname M_{\text{FC(\Gamma)에서, 회로는 \Gamma의 (유한) **순환**이다. * **접합 매트로이드** \operatorname M_{\text{B(\Gamma)에서, 회로는 **접합**(bond)라고 하며, \Gamma의 변의 (유한 또는 무한) 집합 S\subseteq\operatorname E(\Gamma) 가운데, 다음 두 조건을 만족시키는 것이다. ** \Gamma의 연결 성분 가운데 적어도 하나 이상은 \Gamma\setminus S에서 연결 성분이 아니게 된다. ** 임의의 e\in S에 대하여, \Gamma의 모든 연결 성분은 \Gamma\setminus (S\setminus\\{e\\})에서도 연결 성분으로 남는다. 이 두 매트로이드는 서로 쌍대 매트로이드를 이룬다. 다중 그래프 \Gamma의 안둘레는 그 순환 매트로이드 \operatorname M_{\text{FC(\Gamma)의 안둘레이다. 즉, 그래프 \Gamma의 안둘레는 그 그래프 속의 순환의 최소 길이이다. 순환을 갖지 않는 그래프(즉, 숲 그래프)의 경우, 안둘레를 무한대로 정의한다. 즉, 그래프의 안둘레의 가능한 값은 다음과 같다. :\\{3,4,5,\dotsc\\}\sqcup\\{+\infty\\} 다중 그래프 \Gamma의 밖둘레는 그 순환 매트로이드 \operatorname M_{\text{FC(\Gamma)의 밖둘레이다. 즉, 그래프 속의 순환의 길이들의 상한이다. 순환을 갖지 않는 그래프(즉, 숲 그래프)의 경우, 밖둘레를 -\infty로 정의한다. 즉, 그래프의 밖둘레의 가능한 값은 다음과 같다. :\\{3,4,5,\dotsc\\}\sqcup\\{+\infty,-\infty\\} 물론, 유한 그래프의 밖둘레는 +\infty가 될 수 없다. 다중 그래프 \Gamma의 **변 연결도**(邊連結度, edge connectivity)는 그 접합 매트로이드 \operatorname M_{\text{FB(\Gamma)의 안둘레이다. 즉, 그래프 \Gamma의 가장 작은 접합의 크기, 즉 새 연결 성분을 만들기 위해서 제거해야 하는 변의 수의 최솟값이다. 무한 그래프의 경우, 변 연결도는 (안둘레와 달리) 임의의 기수 값을 가질 수 있다. 무변 그래프가 아닌 모든 다중 그래프는 하나 이상의 접합을 가지므로, 이 경우 변 연결도는 잘 정의된다. 무변 그래프의 경우, 변 연결도는 +\infty로 놓는다. 마찬가지로, 다중 그래프 \Gamma의 접합 매트로이드의 밖둘레 (접합의 크기의 상한) 역시 정의될 수 있으며, 이를 **최대 접합 크기**(maximum bond size)라고 하자. 무한 그래프의 경우, 최대 접합 크기는 (밖둘레와 달리) 임의의 기수 값을 가질 수 있다. 무변 그래프가 아닌 모든 다중 그래프는 하나 이상의 접합을 가지므로, 이 경우 최대 접합 크기는 잘 정의된다. 무변 그래프의 경우, 최대 접합 크기는 -\infty로 놓는다.
# 성질

## 분리합집합
임의의 그래프들의 족 \\{\Gamma_i\\}_{i\in I}에 대하여, 다음이 성립한다. :\operatorname{girth}\left(\bigsqcup_{i\in I}\Gamma_i\right)=\min_{i\in I}\operatorname{girth}\Gamma_i :\operatorname{circ}\left(\bigsqcup_{i\in I}\Gamma_i\right)=\sup_{i\in I}\operatorname{circ}\Gamma_i :\operatorname{girth}\left(\operatorname{M_B}\left(\bigsqcup_{i\in I}\Gamma_i\right)\right)=\min_{i\in I}\operatorname{girth}\operatorname{M_B}(\Gamma_i) :\operatorname{circ}\left(\operatorname{M_B}\left(\bigsqcup_{i\in I}\Gamma_i\right)\right)=\sup_{i\in I}\operatorname{circ}\operatorname{M_B}(\Gamma_i) 여기서 \textstyle\bigsqcup는 그래프의 분리합집합이다.
## 상계
꼭짓점이 n개인 유한 그래프의 밖둘레는 n 이하이며, 이 상계는 해밀턴 순환에 의하여 포화된다. 즉, 밖둘레가 n인 것은 해밀턴 순환을 갖는 것과 동치이다. 차수 r의 정규 그래프 \Gamma에 대하여, 다음이 성립한다. : |\operatorname V(\Gamma)| \ge \begin{cases} 1+r\sum_{i=0}^{(\operatorname{girth}\Gamma-3)/2}(r-1)^i & 2\nmid\operatorname{girth}\Gamma \\\ 2\sum_{i=0}^{(\operatorname{girth}\Gamma-2)/2}(r-1)^i &2\mid\operatorname{girth}\Gamma \end{cases} 이 부등식을 포화시키는 정규 그래프를 **무어 그래프**(Moore graph)라고 한다. 그래프 \Gamma에서, 주어진 꼭짓점에 연결된 모든 변들의 집합은 접합을 이룬다. 따라서, 꼭짓점의 차수들의 상한은 그 최대 접합 크기의 하계를 이루며, 꼭짓점의 차수들의 최솟값은 변 연결도의 상계를 이룬다. :\operatorname{girth}(\operatorname{M_{FB(\Gamma))\le\min_{v\in\operatorname V(\Gamma)} \deg_\Gamma v\le \sup_{v\in\operatorname V(\Gamma)}\deg_\Gamma v\le\operatorname{circ}(\operatorname{M_{FB(\Gamma))
# 예
{| class=wikitable ! 이름 !! 기호 !! 안둘레 !! 밖둘레 !! 변 연결도 !! 최대 접합 크기 |- | 완전 그래프 || K_n (n\ge3) || 3 || n || n-1 || \lfloor n^2/4\rfloor |- | 완전 이분 그래프 || K_{m,n} (\min\\{m,n\\}\ge2) || 4 || 2\min\\{m,n\\} || \min\\{m,n\\} || \lfloor m/2\rfloor\lceil n/2\rceil + \lceil m/2\rceil\lfloor n/2\rfloor |- | 숲 그래프 || T (|\operatorname E(T)|\ge1) || +\infty || -\infty || 1 || 1 |- | 무변 그래프 || \bar K_n || +\infty || -\infty || +\infty || -\infty |- | 순환 그래프 || C_n (n\ge3) || n || n || 2 || 2 |- | 페테르센 그래프 || \operatorname{GPG}(5,2) || 5 || 9 || 3 || |- | 데자르그 그래프 || \operatorname{GPG}(10,3) || 6 || 20 || 3 || |}

**완전 그래프의 변 연결도 및 최대 접합 크기의 계산**:

완전 그래프 K_n의 접합을 제거하면, a개의 꼭짓점으로 구성된 연결 성분이 생긴다고 하자. 그렇다면, 이를 분리하기 위해 제거해야 할 변의 수는 :a(n-a)=n^2/4-(a-n/2)^2 이다. 이를 최소화하려면, |a-n/2|를 최대화해야 한다. 이는 a=1(또는 a=n-1)에서 달성되며, 그 접합의 크기는 n-1이다. 반대로, 접합의 크기를 최대화하려면, |a-n/2|를 최소화해야 하며, 이는 a=\lfloor n/2\rfloor(또는 a=\lceil n/2\rceil)에서 달성되며, 그 접합의 크기는 \lfloor n^2/4\rfloor이다.

**완전 이분 그래프의 변 연결도 및 최대 접합 크기의 계산**:

m개의 검은 꼭짓점 및 n개의 흰 꼭짓점을 갖는 완전 이분 그래프 K_{m,n}의 접합을 제거하면, a개의 흰 꼭짓점과 b개의 검은 꼭짓점으로 구성된 연결 성분이 생긴다고 하자. 그렇다면, 이를 분리하기 위해 제거해야 할 변의 수는 :a(n-b)+b(m-a) = mn/2 - 2(a-m/2)(b-n/2) 이다. 이를 최소화하려면, (a-m/2)(b-n/2)를 최대화해야 한다. 이는 (a,b)=(0,1) 또는 (1,0) (또는 (m,n-1) 또는 (m-1,n))에서 달성되며, 그 접합의 크기는 \min\\{m,n\\}이다. 반대로, 접합의 크기를 최대화하려면, (a-m/2)(b-n/2)를 최소화해야 한다. 이는 :a=\lfloor m/2\rfloor :b=\lfloor n/2\rfloor 에서 달성되며, 그 접합의 크기는 :\lfloor m/2\rfloor\lceil n/2\rceil + \lceil m/2\rceil\lfloor n/2\rfloor 이다.

# 역사
무어 그래프의 개념은 미국의 수학자 에드워드 포리스트 무어(Edward Forrest Moore, 1925~2003)가 도입하였다. 변 연결도는 카미유 조르당이 1869년에 도입하였다.언어 = fr