그래프 이론과 매트로이드 이론에서 안둘레(영어: girth 거스[*])는 그래프 또는 매트로이드 속의 가장 작은 “구멍”, 즉 최소의 순환의 크기이다. 마찬가지로 그래프 또는 매트로이드의 밖둘레(영어: circumference 서컴퍼런스[*])는 최대의 순환의 크기이다.
매트로이드[편집]
매트로이드
의 회로들의 집합을
![{\displaystyle \operatorname {Circ} (X)\subseteq \operatorname {Pow} (X)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/af1df708c2f906842a8fb510e843ae79221c7930)
라고 하자.
매트로이드
의 안둘레는 그 회로의 크기의 최솟값이다.
![{\displaystyle \operatorname {girth} (X)=\min _{C\in \operatorname {Circ} (X)}|C|\in \{\kappa \in \operatorname {Card} \colon \kappa \leq |X|\}\sqcup \{+\infty \}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7b8daf8988f75f7db4c42d8cc3db708ad429a947)
여기서
는 모든 기수들의 모임이다.
만약 회로가 존재하지 않는다면, 이 경우 안둘레를 형식적인 기호
로 정의한다.
매트로이드
의 밖둘레는 그 회로의 크기의 최댓값이다.
![{\displaystyle \operatorname {circ} (X)=\max _{C\in \operatorname {Circ} (X)}|C|\in \{\kappa \in \operatorname {Card} \colon \kappa \leq |X|\}\sqcup \{-\infty \}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/9d7d46c6ab67940d6be1b477cae200baab6f4673)
만약 회로가 존재하지 않는다면, 이 경우 밖둘레를 형식적인 기호
로 정의한다.
그래프[편집]
임의의 다중 그래프
의 변들의 집합
위에는 다음과 같은 두 매트로이드 구조를 줄 수 있다.[1]:§2.2
- (유한) 순환 매트로이드
에서, 회로는
의 (유한) 순환이다.
- 접합 매트로이드
에서, 회로는 접합(영어: bond)라고 하며,
의 변의 (유한 또는 무한) 집합
가운데, 다음 두 조건을 만족시키는 것이다.
의 연결 성분 가운데 적어도 하나 이상은
에서 연결 성분이 아니게 된다.
- 임의의
에 대하여,
의 모든 연결 성분은
에서도 연결 성분으로 남는다.
이 두 매트로이드는 서로 쌍대 매트로이드를 이룬다.
다중 그래프
의 안둘레는 그 순환 매트로이드
의 안둘레이다. 즉, 그래프
의 안둘레는 그 그래프 속의 순환의 최소 길이이다. 순환을 갖지 않는 그래프(즉, 숲 그래프)의 경우, 안둘레를 무한대로 정의한다. 즉, 그래프의 안둘레의 가능한 값은 다음과 같다.
![{\displaystyle \{3,4,5,\dotsc \}\sqcup \{+\infty \}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/43e0cec722ef6c9dc9ecbbb5e37c2330249c7610)
다중 그래프
의 밖둘레는 그 순환 매트로이드
의 밖둘레이다. 즉, 그래프 속의 순환의 길이들의 상한이다. 순환을 갖지 않는 그래프(즉, 숲 그래프)의 경우, 밖둘레를
로 정의한다. 즉, 그래프의 밖둘레의 가능한 값은 다음과 같다.
![{\displaystyle \{3,4,5,\dotsc \}\sqcup \{+\infty ,-\infty \}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/67f80f34b31453dfbc5eb1e1f18f2f4f8553536e)
물론, 유한 그래프의 밖둘레는
가 될 수 없다.
다중 그래프
의 변 연결도(邊連結度, 영어: edge connectivity)는 그 접합 매트로이드
의 안둘레이다. 즉, 그래프
의 가장 작은 접합의 크기, 즉 새 연결 성분을 만들기 위해서 제거해야 하는 변의 수의 최솟값이다. 무한 그래프의 경우, 변 연결도는 (안둘레와 달리) 임의의 기수 값을 가질 수 있다. 무변 그래프가 아닌 모든 다중 그래프는 하나 이상의 접합을 가지므로, 이 경우 변 연결도는 잘 정의된다. 무변 그래프의 경우, 변 연결도는
로 놓는다.
마찬가지로, 다중 그래프
의 접합 매트로이드의 밖둘레 (접합의 크기의 상한) 역시 정의될 수 있으며, 이를 최대 접합 크기(영어: maximum bond size)라고 하자. 무한 그래프의 경우, 최대 접합 크기는 (밖둘레와 달리) 임의의 기수 값을 가질 수 있다. 무변 그래프가 아닌 모든 다중 그래프는 하나 이상의 접합을 가지므로, 이 경우 최대 접합 크기는 잘 정의된다. 무변 그래프의 경우, 최대 접합 크기는
로 놓는다.
분리합집합[편집]
임의의 그래프들의 족
에 대하여, 다음이 성립한다.
![{\displaystyle \operatorname {girth} \left(\bigsqcup _{i\in I}\Gamma _{i}\right)=\min _{i\in I}\operatorname {girth} \Gamma _{i}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/fa7c9b037c5b9b7e6e893ee40bbeb5b6f28d3b16)
![{\displaystyle \operatorname {circ} \left(\bigsqcup _{i\in I}\Gamma _{i}\right)=\sup _{i\in I}\operatorname {circ} \Gamma _{i}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5a12ecc67f46de2aa2103dbee26492d268e08ae2)
![{\displaystyle \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})}](https://wikimedia.org/api/rest_v1/media/math/render/svg/6bb2fdd6b8345198b82977752c0949ce4d6cd9e3)
![{\displaystyle \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})}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c4c04886361b736979d9dd9e68c136c6df2203f9)
여기서
는 그래프의 분리합집합이다.
꼭짓점이
개인 유한 그래프의 밖둘레는
이하이며, 이 상계는 해밀턴 순환에 의하여 포화된다. 즉, 밖둘레가
인 것은 해밀턴 순환을 갖는 것과 동치이다.
차수
의 정규 그래프
에 대하여, 다음이 성립한다.
![{\displaystyle |\operatorname {V} (\Gamma )|\geq {\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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4beb62c96937b0177508ab2091766b18c752951f)
이 부등식을 포화시키는 정규 그래프를 무어 그래프(영어: Moore graph)라고 한다.
그래프
에서, 주어진 꼭짓점에 연결된 모든 변들의 집합은 접합을 이룬다. 따라서,
꼭짓점의 차수들의 상한은 그 최대 접합 크기의 하계를 이루며, 꼭짓점의 차수들의 최솟값은 변 연결도의 상계를 이룬다.
![{\displaystyle \operatorname {girth} (\operatorname {M_{FB}} (\Gamma ))\leq \min _{v\in \operatorname {V} (\Gamma )}\deg _{\Gamma }v\leq \sup _{v\in \operatorname {V} (\Gamma )}\deg _{\Gamma }v\leq \operatorname {circ} (\operatorname {M_{FB}} (\Gamma ))}](https://wikimedia.org/api/rest_v1/media/math/render/svg/88ee4fdcbee41df4dbdc425bbba7bd917e1e2811)
이름 |
기호 |
안둘레 |
밖둘레 |
변 연결도 |
최대 접합 크기
|
완전 그래프 |
( ) |
3 |
![{\displaystyle n}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a601995d55609f2d9f5e233e36fbe9ea26011b3b) |
![{\displaystyle n-1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/fbd0b0f32b28f51962943ee9ede4fb34198a2521) |
|
완전 이분 그래프 |
( ) |
4 |
![{\displaystyle 2\min\{m,n\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f607f612a7e06289a30c24d79e6c735cc44f5a60) |
![{\displaystyle \min\{m,n\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a50e7d8d8a2fdf94f29f0ed7e8f94a8a7200806b) |
|
숲 그래프 |
( ) |
![{\displaystyle +\infty }](https://wikimedia.org/api/rest_v1/media/math/render/svg/bddbb0e4420a7e744cf71bd71216e11b0bf88831) |
![{\displaystyle -\infty }](https://wikimedia.org/api/rest_v1/media/math/render/svg/ca2608c4b5fd3bffc73585f8c67e379b4e99b6f1) |
1 |
1
|
무변 그래프 |
![{\displaystyle {\bar {K}}_{n}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/497502f0fdc63bcd59f5352bb1f6a2fc8a30f40d) |
![{\displaystyle +\infty }](https://wikimedia.org/api/rest_v1/media/math/render/svg/bddbb0e4420a7e744cf71bd71216e11b0bf88831) |
![{\displaystyle -\infty }](https://wikimedia.org/api/rest_v1/media/math/render/svg/ca2608c4b5fd3bffc73585f8c67e379b4e99b6f1) |
![{\displaystyle +\infty }](https://wikimedia.org/api/rest_v1/media/math/render/svg/bddbb0e4420a7e744cf71bd71216e11b0bf88831) |
|
순환 그래프 |
( ) |
![{\displaystyle n}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a601995d55609f2d9f5e233e36fbe9ea26011b3b) |
![{\displaystyle n}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a601995d55609f2d9f5e233e36fbe9ea26011b3b) |
2 |
2
|
페테르센 그래프 |
![{\displaystyle \operatorname {GPG} (5,2)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4fd215e1115c3d7a62bd06636df5891c1a6180f0) |
5 |
9 |
3 |
|
데자르그 그래프 |
![{\displaystyle \operatorname {GPG} (10,3)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ab54004a50ecd3dcfbadf06fe93cea9ab571080d) |
6 |
20 |
3 |
|
완전 이분 그래프의 변 연결도 및 최대 접합 크기의 계산:
개의 검은 꼭짓점 및
개의 흰 꼭짓점을 갖는 완전 이분 그래프
의 접합을 제거하면,
개의 흰 꼭짓점과
개의 검은 꼭짓점으로 구성된 연결 성분이 생긴다고 하자. 그렇다면, 이를 분리하기 위해 제거해야 할 변의 수는
![{\displaystyle a(n-b)+b(m-a)=mn/2-2(a-m/2)(b-n/2)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/271272201e2366e91c437a0c962f22c315bf5a90)
이다. 이를 최소화하려면,
를 최대화해야 한다. 이는
또는
(또는
또는
)에서 달성되며, 그 접합의 크기는
이다.
반대로, 접합의 크기를 최대화하려면,
를 최소화해야 한다. 이는
![{\displaystyle a=\lfloor m/2\rfloor }](https://wikimedia.org/api/rest_v1/media/math/render/svg/4c190cc6b10d309ea5496d2df0e9652ea96d9dd9)
![{\displaystyle b=\lfloor n/2\rfloor }](https://wikimedia.org/api/rest_v1/media/math/render/svg/7b65513e09fe5de222c89675e2d332ffc10dd113)
에서 달성되며, 그 접합의 크기는
![{\displaystyle \lfloor m/2\rfloor \lceil n/2\rceil +\lceil m/2\rceil \lfloor n/2\rfloor }](https://wikimedia.org/api/rest_v1/media/math/render/svg/8c1e17cee2ed951f53caab5011e2a95b17cb1229)
이다.
무어 그래프의 개념은 미국의 수학자 에드워드 포리스트 무어(영어: Edward Forrest Moore, 1925~2003)가 도입하였다. 변 연결도는 카미유 조르당이 1869년에 도입하였다.[2]
외부 링크[편집]