안둘레

틀:위키데이터 속성 추적 그래프 이론과 매트로이드 이론에서 안둘레(틀:Llang)는 그래프 또는 매트로이드 속의 가장 작은 “구멍”, 즉 최소의 순환의 크기이다. 마찬가지로 그래프 또는 매트로이드의 밖둘레(틀:Llang)는 최대의 순환의 크기이다.

정의

매트로이드

매트로이드 $X$의 회로들의 집합을

$\mathrm{Circ}(X)\subseteq \mathrm{Pow}(X)$

라고 하자.

매트로이드 $X$의 안둘레는 그 회로의 크기의 최솟값이다.

$\mathrm{girth}(X)=\underset{C\in \mathrm{Circ}(X)}{\min }|C|\in \{\kappa \in \mathrm{Card}:\kappa \le |X|\}\bigsqcup \{+\mathrm{\infty }\}$

여기서 $\mathrm{Card}$는 모든 기수들의 모임이다. 만약 회로가 존재하지 않는다면, 이 경우 안둘레를 형식적인 기호 $+\mathrm{\infty }$로 정의한다.

매트로이드 $X$의 밖둘레는 그 회로의 크기의 최댓값이다.

$\mathrm{circ}(X)=\underset{C\in \mathrm{Circ}(X)}{\max }|C|\in \{\kappa \in \mathrm{Card}:\kappa \le |X|\}\bigsqcup \{-\mathrm{\infty }\}$

만약 회로가 존재하지 않는다면, 이 경우 밖둘레를 형식적인 기호 $-\mathrm{\infty }$로 정의한다.

그래프

임의의 다중 그래프 $\mathrm{\Gamma }$의 변들의 집합 $\mathrm{E}(\mathrm{\Gamma })$ 위에는 다음과 같은 두 매트로이드 구조를 줄 수 있다.틀:Rp

• (유한) 순환 매트로이드 ${\mathrm{M}}_{\text{FC}}(\mathrm{\Gamma })$에서, 회로는 $\mathrm{\Gamma }$의 (유한) 순환이다.
• 접합 매트로이드 ${\mathrm{M}}_{\text{B}}(\mathrm{\Gamma })$에서, 회로는 접합(틀:Llang)라고 하며, $\mathrm{\Gamma }$의 변의 (유한 또는 무한) 집합 $S\subseteq \mathrm{E}(\mathrm{\Gamma })$ 가운데, 다음 두 조건을 만족시키는 것이다.
  • $\mathrm{\Gamma }$의 연결 성분 가운데 적어도 하나 이상은 $\mathrm{\Gamma }\setminus S$에서 연결 성분이 아니게 된다.
  • 임의의 $e\in S$에 대하여, $\mathrm{\Gamma }$의 모든 연결 성분은 $\mathrm{\Gamma }\setminus (S\setminus \{e\})$에서도 연결 성분으로 남는다.

이 두 매트로이드는 서로 쌍대 매트로이드를 이룬다.

다중 그래프 $\mathrm{\Gamma }$의 안둘레는 그 순환 매트로이드 ${\mathrm{M}}_{\text{FC}}(\mathrm{\Gamma })$의 안둘레이다. 즉, 그래프 $\mathrm{\Gamma }$의 안둘레는 그 그래프 속의 순환의 최소 길이이다. 순환을 갖지 않는 그래프(즉, 숲 그래프)의 경우, 안둘레를 무한대로 정의한다. 즉, 그래프의 안둘레의 가능한 값은 다음과 같다.

$\{3,4,5,\dots \}\bigsqcup \{+\mathrm{\infty }\}$

다중 그래프 $\mathrm{\Gamma }$의 밖둘레는 그 순환 매트로이드 ${\mathrm{M}}_{\text{FC}}(\mathrm{\Gamma })$의 밖둘레이다. 즉, 그래프 속의 순환의 길이들의 상한이다. 순환을 갖지 않는 그래프(즉, 숲 그래프)의 경우, 밖둘레를 $-\mathrm{\infty }$로 정의한다. 즉, 그래프의 밖둘레의 가능한 값은 다음과 같다.

$\{3,4,5,\dots \}\bigsqcup \{+\mathrm{\infty },-\mathrm{\infty }\}$

물론, 유한 그래프의 밖둘레는 $+\mathrm{\infty }$가 될 수 없다.

다중 그래프 $\mathrm{\Gamma }$의 변 연결도(邊連結度, 틀:Llang)는 그 접합 매트로이드 ${\mathrm{M}}_{\text{FB}}(\mathrm{\Gamma })$의 안둘레이다. 즉, 그래프 $\mathrm{\Gamma }$의 가장 작은 접합의 크기, 즉 새 연결 성분을 만들기 위해서 제거해야 하는 변의 수의 최솟값이다. 무한 그래프의 경우, 변 연결도는 (안둘레와 달리) 임의의 기수 값을 가질 수 있다. 무변 그래프가 아닌 모든 다중 그래프는 하나 이상의 접합을 가지므로, 이 경우 변 연결도는 잘 정의된다. 무변 그래프의 경우, 변 연결도는 $+\mathrm{\infty }$로 놓는다.

마찬가지로, 다중 그래프 $\mathrm{\Gamma }$의 접합 매트로이드의 밖둘레 (접합의 크기의 상한) 역시 정의될 수 있으며, 이를 최대 접합 크기(틀:Llang)라고 하자. 무한 그래프의 경우, 최대 접합 크기는 (밖둘레와 달리) 임의의 기수 값을 가질 수 있다. 무변 그래프가 아닌 모든 다중 그래프는 하나 이상의 접합을 가지므로, 이 경우 최대 접합 크기는 잘 정의된다. 무변 그래프의 경우, 최대 접합 크기는 $-\mathrm{\infty }$로 놓는다.

성질

분리합집합

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

$\mathrm{girth}\left(\underset{i\in I}{⨆}{\mathrm{\Gamma }}_i\right)=\underset{i\in I}{\min }\mathrm{girth}{\mathrm{\Gamma }}_i$

$\mathrm{circ}\left(\underset{i\in I}{⨆}{\mathrm{\Gamma }}_i\right)=\underset{i\in I}{\sup }\mathrm{circ}{\mathrm{\Gamma }}_i$

$\mathrm{girth}({\mathrm{M}}_{\mathrm{B}}\left(\underset{i\in I}{⨆}{\mathrm{\Gamma }}_i\right))=\underset{i\in I}{\min }\mathrm{girth}{\mathrm{M}}_{\mathrm{B}}({\mathrm{\Gamma }}_i)$

$\mathrm{circ}({\mathrm{M}}_{\mathrm{B}}\left(\underset{i\in I}{⨆}{\mathrm{\Gamma }}_i\right))=\underset{i\in I}{\sup }\mathrm{circ}{\mathrm{M}}_{\mathrm{B}}({\mathrm{\Gamma }}_i)$

여기서 $⨆$는 그래프의 분리합집합이다.

상계

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

차수 $r$의 정규 그래프 $\mathrm{\Gamma }$에 대하여, 다음이 성립한다.

$|\mathrm{V}(\mathrm{\Gamma })|\ge \{\begin{array}{cc}1+r\sum _{i=0}^{(\mathrm{girth}\mathrm{\Gamma }-3)/2}(r-1{)}^i& 2\nmid \mathrm{girth}\mathrm{\Gamma }\\ 2\sum _{i=0}^{(\mathrm{girth}\mathrm{\Gamma }-2)/2}(r-1{)}^i& 2\mid \mathrm{girth}\mathrm{\Gamma }\end{array}$

이 부등식을 포화시키는 정규 그래프를 무어 그래프(틀:Llang)라고 한다.

그래프 $\mathrm{\Gamma }$에서, 주어진 꼭짓점에 연결된 모든 변들의 집합은 접합을 이룬다. 따라서, 꼭짓점의 차수들의 상한은 그 최대 접합 크기의 하계를 이루며, 꼭짓점의 차수들의 최솟값은 변 연결도의 상계를 이룬다.

$\mathrm{girth}({\mathrm{M}}_{\mathrm{FB}}(\mathrm{\Gamma }))\le \underset{v\in \mathrm{V}(\mathrm{\Gamma })}{\min }{\mathrm{deg}}_{\mathrm{\Gamma }}v\le \underset{v\in \mathrm{V}(\mathrm{\Gamma })}{\sup }{\mathrm{deg}}_{\mathrm{\Gamma }}v\le \mathrm{circ}({\mathrm{M}}_{\mathrm{FB}}(\mathrm{\Gamma }))$

예

이름	기호	안둘레	밖둘레	변 연결도	최대 접합 크기
완전 그래프	$K_n$ ($n\ge 3$)	3	$n$	$n-1$	$\lfloor n^2/4\rfloor$
완전 이분 그래프	$K_{m,n}$ ($\min \{m,n\}\ge 2$)	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$ ($|\mathrm{E}(T)|\ge 1$)	$+\mathrm{\infty }$	$-\mathrm{\infty }$	1	1
무변 그래프	${\overline{K}}_n$	$+\mathrm{\infty }$	$-\mathrm{\infty }$	$+\mathrm{\infty }$	$-\mathrm{\infty }$
순환 그래프	$C_n$ ($n\ge 3$)	$n$	$n$	2	2
페테르센 그래프	$\mathrm{GPG}(5,2)$	5	9	3
데자르그 그래프	$\mathrm{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$

이다.

역사

무어 그래프의 개념은 미국의 수학자 에드워드 포리스트 무어(틀:Llang, 1925~2003)가 도입하였다. 변 연결도는 카미유 조르당이 1869년에 도입하였다.

외부 링크

• 틀:Eom
• 틀:매스월드
• 틀:매스월드
• 틀:매스월드
• 틀:매스월드
• 틀:웹 인용