안둘레 문서 원본 보기

{{위키데이터 속성 추적}}
[[그래프 이론]]과 [[매트로이드 이론]]에서 '''안둘레'''({{llang|en|girth|거스}})는 [[그래프]] 또는 [[매트로이드]] 속의 가장 작은 “구멍”, 즉 최소의 [[순환 (그래프 이론)|순환]]의 크기이다. 마찬가지로 그래프 또는 매트로이드의 '''밖둘레'''({{llang|en|circumference|서컴퍼런스}})는 최대의 [[순환 (그래프 이론)|순환]]의 크기이다.

== 정의 ==
=== 매트로이드 ===
[[매트로이드]] <math>X</math>의 회로들의 집합을
:<math>\operatorname{Circ}(X)\subseteq\operatorname{Pow}(X)</math>
라고 하자.

매트로이드 <math>X</math>의 안둘레는 그 회로의 크기의 최솟값이다.
:<math>\operatorname{girth}(X)=\min_{C\in\operatorname{Circ}(X)}|C|\in\{\kappa\in\operatorname{Card}\colon\kappa\le|X|\}\sqcup\{+\infty\}</math>
여기서 <math>\operatorname{Card}</math>는 모든 [[기수 (수학)|기수]]들의 [[모임 (집합론)|모임]]이다.
만약 회로가 존재하지 않는다면, 이 경우 안둘레를 형식적인 기호 <math>+\infty</math>로 정의한다.

매트로이드 <math>X</math>의 밖둘레는 그 회로의 크기의 최댓값이다.
:<math>\operatorname{circ}(X)=\max_{C\in\operatorname{Circ}(X)}|C|\in\{\kappa\in\operatorname{Card}\colon\kappa\le|X|\}\sqcup\{-\infty\}</math>
만약 회로가 존재하지 않는다면, 이 경우 밖둘레를 형식적인 기호 <math>-\infty</math>로 정의한다.

=== 그래프 ===
임의의 [[다중 그래프]] <math>\Gamma</math>의 변들의 집합 <math>\operatorname E(\Gamma)</math> 위에는 다음과 같은 두 매트로이드 구조를 줄 수 있다.<ref name="BDKPW">{{저널 인용|제목=Axioms for infinite matroids|이름=Henning|성=Bruhn|이름2=Reinhard|성2=Diestel|이름3=Matthias|성3=Kriesell|이름4=Rudi A.|성4=Pendavingh|이름5=Paul |성5=Wollan|arxiv=1003.3919|doi=10.1016/j.aim.2013.01.011|bibcode=2010arXiv1003.3919B|저널=Advances in Mathematics|권=239|날짜=2013-06-01|쪽=18–46|zbl=1279.05013|언어=en}}</ref>{{rp|§2.2}}
* (유한) '''순환 매트로이드''' <math>\operatorname M_{\text{FC}}(\Gamma)</math>에서, 회로는 <math>\Gamma</math>의 (유한) '''[[순환 (그래프 이론)|순환]]'''이다.
* '''접합 매트로이드''' <math>\operatorname M_{\text{B}}(\Gamma)</math>에서, 회로는 '''접합'''({{llang|en|bond}})라고 하며, <math>\Gamma</math>의 변의 (유한 또는 무한) 집합 <math>S\subseteq\operatorname E(\Gamma)</math> 가운데, 다음 두 조건을 만족시키는 것이다.
** <math>\Gamma</math>의 [[연결 성분]] 가운데 적어도 하나 이상은 <math>\Gamma\setminus S</math>에서 연결 성분이 아니게 된다.
** 임의의 <math>e\in S</math>에 대하여, <math>\Gamma</math>의 모든 연결 성분은 <math>\Gamma\setminus (S\setminus\{e\})</math>에서도 연결 성분으로 남는다.
이 두 매트로이드는 서로 쌍대 매트로이드를 이룬다.

다중 그래프 <math>\Gamma</math>의 안둘레는 그 순환 매트로이드 <math>\operatorname M_{\text{FC}}(\Gamma)</math>의 안둘레이다. 즉, [[그래프]] <math>\Gamma</math>의 안둘레는 그 그래프 속의 [[순환 (그래프 이론)|순환]]의 최소 길이이다. [[순환 (그래프 이론)|순환]]을 갖지 않는 [[그래프]](즉, [[숲 그래프]])의 경우, 안둘레를 [[무한대]]로 정의한다. 즉, 그래프의 안둘레의 가능한 값은 다음과 같다.
:<math>\{3,4,5,\dotsc\}\sqcup\{+\infty\}</math>

다중 그래프 <math>\Gamma</math>의 밖둘레는 그 순환 매트로이드 <Math>\operatorname M_{\text{FC}}(\Gamma)</math>의 밖둘레이다. 즉, 그래프 속의 순환의 길이들의 [[상한]]이다. 순환을 갖지 않는 [[그래프]](즉, [[숲 그래프]])의 경우, 밖둘레를 <math>-\infty</math>로 정의한다. 즉, 그래프의 밖둘레의 가능한 값은 다음과 같다.
:<math>\{3,4,5,\dotsc\}\sqcup\{+\infty,-\infty\}</math>
물론, [[유한 그래프]]의 밖둘레는 <math>+\infty</math>가 될 수 없다.

다중 그래프 <math>\Gamma</math>의 '''변 연결도'''(邊連結度, {{llang|en|edge connectivity}})는 그 접합 매트로이드 <math>\operatorname M_{\text{FB}}(\Gamma)</math>의 안둘레이다. 즉, 그래프 <math>\Gamma</math>의 가장 작은 접합의 크기, 즉 새 [[연결 성분]]을 만들기 위해서 제거해야 하는 변의 수의 최솟값이다. 무한 그래프의 경우, 변 연결도는 (안둘레와 달리) 임의의 [[기수 (수학)|기수]] 값을 가질 수 있다. [[무변 그래프]]가 아닌 모든 다중 그래프는 하나 이상의 접합을 가지므로, 이 경우 변 연결도는 잘 정의된다. 무변 그래프의 경우, 변 연결도는 <math>+\infty</math>로 놓는다.

마찬가지로, 다중 그래프 <math>\Gamma</math>의 접합 매트로이드의 밖둘레 (접합의 크기의 [[상한]]) 역시 정의될 수 있으며, 이를 '''최대 접합 크기'''({{llang|en|maximum bond size}})라고 하자. 무한 그래프의 경우, 최대 접합 크기는 (밖둘레와 달리) 임의의 [[기수 (수학)|기수]] 값을 가질 수 있다. 무변 그래프가 아닌 모든 다중 그래프는 하나 이상의 접합을 가지므로, 이 경우 최대 접합 크기는 잘 정의된다. 무변 그래프의 경우, 최대 접합 크기는 <math>-\infty</math>로 놓는다.

== 성질 ==
=== 분리합집합 ===
임의의 그래프들의 족 <math>\{\Gamma_i\}_{i\in I}</math>에 대하여, 다음이 성립한다.
:<math>\operatorname{girth}\left(\bigsqcup_{i\in I}\Gamma_i\right)=\min_{i\in I}\operatorname{girth}\Gamma_i</math>
:<math>\operatorname{circ}\left(\bigsqcup_{i\in I}\Gamma_i\right)=\sup_{i\in I}\operatorname{circ}\Gamma_i</math>
:<math>\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)</math>
:<math>\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)</math>
여기서 <math>\textstyle\bigsqcup</math>는 그래프의 [[분리합집합]]이다.

=== 상계 ===
꼭짓점이 <math>n</math>개인 [[유한 그래프]]의 밖둘레는 <math>n</math> 이하이며, 이 [[상계 (수학)|상계]]는 [[해밀턴 순환]]에 의하여 포화된다. 즉, 밖둘레가 <math>n</math>인 것은 해밀턴 순환을 갖는 것과 [[동치]]이다.

차수 <math>r</math>의 [[정규 그래프]] <math>\Gamma</math>에 대하여, 다음이 성립한다.
:<math>
|\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}</math>
이 부등식을 포화시키는 정규 그래프를 '''무어 그래프'''({{llang|en|Moore graph}})라고 한다.

[[그래프]] <math>\Gamma</math>에서, 주어진 꼭짓점에 연결된 모든 변들의 집합은 접합을 이룬다. 따라서,
꼭짓점의 차수들의 [[상한]]은 그 최대 접합 크기의 [[하계 (수학)|하계]]를 이루며, 꼭짓점의 차수들의 [[최솟값]]은 변 연결도의 상계를 이룬다.
:<math>\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))</math>

== 예 ==
{| class=wikitable
! 이름 !! 기호 !! 안둘레 !! 밖둘레 !! 변 연결도 !! 최대 접합 크기
|-
| [[완전 그래프]] || <math>K_n</math> (<math>n\ge3</math>) || 3 || <math>n</math> || <math>n-1</math> || <math>\lfloor n^2/4\rfloor</math>
|-
| [[완전 이분 그래프]]  || <math>K_{m,n}</math> (<math>\min\{m,n\}\ge2</math>) || 4 || <math>2\min\{m,n\}</math> || <math>\min\{m,n\}</math> || <math>\lfloor m/2\rfloor\lceil n/2\rceil + \lceil m/2\rceil\lfloor n/2\rfloor</math>
|-
| [[숲 그래프]] || <math>T</math> (<math>|\operatorname E(T)|\ge1</math>) || <math>+\infty</math> || <math>-\infty</math> || 1 || 1
|-
| [[무변 그래프]] || <math>\bar K_n</math> || <math>+\infty</math> || <math>-\infty</math> || <math>+\infty</math> || <math>-\infty</math>
|-
| [[순환 그래프]] || <math>C_n</math> (<math>n\ge3</math>) || <math>n</math> || <math>n</math> || 2 || 2
|-
| [[페테르센 그래프]] || <math>\operatorname{GPG}(5,2)</math> || 5 || 9  || 3 ||
|-
| [[데자르그 그래프]] || <math>\operatorname{GPG}(10,3)</math>  || 6 || 20 || 3 ||
|}

<div class="mw-collapsible mw-collapsed toccolours">
'''[[완전 그래프]]의 변 연결도 및 최대 접합 크기의 계산''':
<div class="mw-collapsible-content">
[[완전 그래프]] <math>K_n</math>의 접합을 제거하면, <math>a</math>개의 꼭짓점으로 구성된 [[연결 성분]]이 생긴다고 하자. 그렇다면, 이를 분리하기 위해 제거해야 할 변의 수는
:<math>a(n-a)=n^2/4-(a-n/2)^2</math>
이다. 이를 최소화하려면, <math>|a-n/2|</math>를 최대화해야 한다. 이는 <math>a=1</math>(또는 <math>a=n-1</math>)에서 달성되며, 그 접합의 크기는 <math>n-1</math>이다.

반대로, 접합의 크기를 최대화하려면, <math>|a-n/2|</math>를 최소화해야 하며, 이는 <math>a=\lfloor n/2\rfloor</math>(또는 <math>a=\lceil n/2\rceil</math>)에서 달성되며, 그 접합의 크기는 <math>\lfloor n^2/4\rfloor</math>이다.
</div></div>

<div class="mw-collapsible mw-collapsed toccolours">
'''[[완전 이분 그래프]]의 변 연결도 및 최대 접합 크기의 계산''':
<div class="mw-collapsible-content">
<math>m</math>개의 검은 꼭짓점 및 <math>n</math>개의 흰 꼭짓점을 갖는 [[완전 이분 그래프]] <math>K_{m,n}</math>의 접합을 제거하면, <math>a</math>개의 흰 꼭짓점과 <math>b</math>개의 검은 꼭짓점으로 구성된 [[연결 성분]]이 생긴다고 하자. 그렇다면, 이를 분리하기 위해 제거해야 할 변의 수는
:<math>a(n-b)+b(m-a) = mn/2 - 2(a-m/2)(b-n/2)</math>
이다. 이를 최소화하려면, <math>(a-m/2)(b-n/2)</math>를 최대화해야 한다. 이는 <math>(a,b)=(0,1)</math> 또는 <math>(1,0)</math> (또는 <math>(m,n-1)</math> 또는 <math>(m-1,n)</math>)에서 달성되며, 그 접합의 크기는 <math>\min\{m,n\}</math>이다.

반대로, 접합의 크기를 최대화하려면, <math>(a-m/2)(b-n/2)</math>를 최소화해야 한다. 이는
:<math>a=\lfloor m/2\rfloor</math>
:<math>b=\lfloor n/2\rfloor</math>
에서 달성되며, 그 접합의 크기는
:<math>\lfloor m/2\rfloor\lceil n/2\rceil + \lceil m/2\rceil\lfloor n/2\rfloor</math>
이다.
</div></div>

== 역사 ==
무어 그래프의 개념은 미국의 수학자 에드워드 포리스트 무어({{llang|en|Edward Forrest Moore}}, 1925~2003)가 도입하였다. 변 연결도는 [[카미유 조르당]]이 1869년에 도입하였다.<ref>{{저널 인용
| last        = Jordan
| first       = Camille
| authorlink  = 카미유 조르당
| year        = 1869
| title       = Sur les assemblages de lignes
| journal     = Journal für die reine und angewandte Mathematik
| volume      = 70
| issue       = 2
| pages       = 185–190
| url         = http://resolver.sub.uni-goettingen.de/purl?GDZPPN002153998
| doi=10.1515/crll.1869.70.185 | jfm=02.0344.01
| issn=0075-4102
| 언어    = fr
}}</ref>

== 각주 ==
{{각주}}

== 외부 링크 ==
* {{eom|title=Graph, connectivity of a}}
* {{매스월드|id=Girth|title=Girth}}
* {{매스월드|id=GraphCircumference|title=Graph circumference}}
* {{매스월드|id=EdgeConnectivity|title=Edge connectivity}}
* {{매스월드|id=k-Edge-ConnectedGraph|title=''k''-edge-connected graph}}
* {{웹 인용|url=http://www.math.uchicago.edu/~may/VIGRE/VIGRE2007/REUPapers/FINALAPP/Ullery.pdf | 제목=Regular graphs of given girth | 이름=Brooke | 성=Ullery | 날짜=2007-08-03 |언어=en}}

[[분류:그래프 이론]]
[[분류:매트로이드 이론]]