안둘레

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

정의편집

매트로이드편집

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

 

라고 하자.

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

 

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

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

 

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

그래프편집

임의의 다중 그래프  의 변들의 집합   위에는 다음과 같은 두 매트로이드 구조를 줄 수 있다.[1]:§2.2

  • (유한) 순환 매트로이드  에서, 회로는  의 (유한) 순환이다.
  • 접합 매트로이드  에서, 회로는 접합(영어: bond)라고 하며,  의 변의 (유한 또는 무한) 집합   가운데, 다음 두 조건을 만족시키는 것이다.
    •  연결 성분 가운데 적어도 하나 이상은  에서 연결 성분이 아니게 된다.
    • 임의의  에 대하여,  의 모든 연결 성분은  에서도 연결 성분으로 남는다.

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

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

 

다중 그래프  의 밖둘레는 그 순환 매트로이드  의 밖둘레이다. 즉, 그래프 속의 순환의 길이들의 상한이다. 순환을 갖지 않는 그래프(즉, 숲 그래프)의 경우, 밖둘레를  로 정의한다. 즉, 그래프의 밖둘레의 가능한 값은 다음과 같다.

 

물론, 유한 그래프의 밖둘레는  가 될 수 없다.

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

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

성질편집

분리합집합편집

임의의 그래프들의 족  에 대하여, 다음이 성립한다.

 
 
 
 

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

상계편집

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

차수  정규 그래프  에 대하여, 다음이 성립한다.

 

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

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

 

편집

이름 기호 안둘레 밖둘레 변 연결도 최대 접합 크기
완전 그래프   ( ) 3      
완전 이분 그래프   ( ) 4      
숲 그래프   ( )     1 1
무변 그래프          
순환 그래프   ( )     2 2
페테르센 그래프   5 9 3
데자르그 그래프   6 20 3

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

완전 그래프  의 접합을 제거하면,  개의 꼭짓점으로 구성된 연결 성분이 생긴다고 하자. 그렇다면, 이를 분리하기 위해 제거해야 할 변의 수는

 

이다. 이를 최소화하려면,  를 최대화해야 한다. 이는  (또는  )에서 달성되며, 그 접합의 크기는  이다.

반대로, 접합의 크기를 최대화하려면,  를 최소화해야 하며, 이는  (또는  )에서 달성되며, 그 접합의 크기는  이다.

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

 개의 검은 꼭짓점 및  개의 흰 꼭짓점을 갖는 완전 이분 그래프  의 접합을 제거하면,  개의 흰 꼭짓점과  개의 검은 꼭짓점으로 구성된 연결 성분이 생긴다고 하자. 그렇다면, 이를 분리하기 위해 제거해야 할 변의 수는

 

이다. 이를 최소화하려면,  를 최대화해야 한다. 이는   또는   (또는   또는  )에서 달성되며, 그 접합의 크기는  이다.

반대로, 접합의 크기를 최대화하려면,  를 최소화해야 한다. 이는

 
 

에서 달성되며, 그 접합의 크기는

 

이다.

역사편집

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

참고 문헌편집

  1. Bruhn, Henning; Diestel, Reinhard; Kriesell, Matthias; Pendavingh, Rudi A.; Wollan, Paul (2013년 6월 1일). “Axioms for infinite matroids”. 《Advances in Mathematics》 (영어) 239: 18–46. arXiv:1003.3919. Bibcode:2010arXiv1003.3919B. doi:10.1016/j.aim.2013.01.011. Zbl 1279.05013. 
  2. Jordan, Camille (1869). “Sur les assemblages de lignes”. 《Journal für die reine und angewandte Mathematik》 (프랑스어) 70 (2): 185–190. doi:10.1515/crll.1869.70.185. ISSN 0075-4102. JFM 02.0344.01. 

외부 링크편집