맨위로가기

안둘레

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.

1. 개요

안둘레는 그래프 이론과 매트로이드 이론에서 사용되는 개념으로, 그래프 또는 매트로이드의 "최소 순환 크기"를 의미한다. 그래프의 안둘레는 그래프 내 순환의 최소 길이를, 매트로이드의 안둘레는 회로 크기의 최솟값을 나타낸다. 안둘레와 반대되는 개념으로 밖둘레가 있으며, 그래프 관점에서는 순환의 길이 상한, 매트로이드 관점에서는 회로 크기의 최댓값을 의미한다. 안둘레는 그래프의 변 연결도, 케이지, 그래프 채색 등 다양한 개념과 관련되며, 계산 방법도 존재한다.

더 읽어볼만한 페이지

  • 매트로이드 이론 - 매트로이드 마이너
    매트로이드 마이너는 매트로이드에서 부분집합 제거 또는 제한 연산을 반복하여 얻어지는 매트로이드로, 매트로이드의 성질 보존, 구조 분석, 그래프 이론과의 연결, 여러 종류의 매트로이드, 구조 파악 및 복잡성 분석, 효율적인 테스트 알고리즘 개발 등에 활용된다.
  • 매트로이드 이론 - 탐욕 알고리즘
    탐욕 알고리즘은 각 단계에서 가장 좋아 보이는 선택을 하는 알고리즘 설계 패러다임으로, 최적 부분 구조와 탐욕 선택 속성을 가진 문제에 최적의 해를 보장하며, 다익스트라, 프림, 크루스칼 알고리즘 등에 사용된다.
  • 그래프 이론 - 다이어그램
    다이어그램은 2차원 기하학적 기호를 사용하여 정보를 시각적으로 표현하는 기술로, 과학, 공학, IT, 비즈니스 등 다양한 분야에서 활용되며 정보를 간략하게 나타내고 시각적 사고를 돕는다.
  • 그래프 이론 - 쾨니히스베르크의 다리 문제
    쾨니히스베르크의 다리 문제는 프레겔 강에 놓인 7개의 다리를 한 번씩만 건너 출발점으로 되돌아올 수 있는지 묻는 문제로, 오일러에 의해 그래프 이론적으로 분석되어 해결되었으며 그래프 이론의 탄생에 기여했다.
안둘레
그래프 이론의 핵심 속성
종류그래프 불변량
기호g(G) 또는 girth(G)
정의그래프 G에 포함된 가장 짧은 주기의 길이
속성루프가 있는 경우 1
루프가 없는 경우, 병렬 모서리가 있으면 2
삼각형이 없는 그래프는 거스가 4 이상임

2. 정의

그래프의 '''안둘레'''는 그 그래프에 포함된 가장 짧은 순환의 길이다. 순환이 없는 그래프(숲 그래프)의 경우에는 안둘레가 무한대로 정의된다.[6] 그래프의 '''홀수 둘레'''와 '''짝수 둘레'''는 각각 최단 홀수 순환과 최단 짝수 순환의 길이이다.

그래프의 '''둘레'''는 가장 긴 순환의 길이이다.

2. 1. 매트로이드 관점

매트로이드에서 회로의 크기 중 최솟값을 안둘레(girth)라고 한다. 그래프의 순환 매트로이드에서 안둘레는 그래프 내의 순환 중 가장 짧은 것의 길이다. 순환이 없는 그래프(숲 그래프)는 안둘레가 무한대로 정의된다.[15]

그래프의 안둘레가 가질 수 있는 값은 다음과 같다.

:\{3,4,5,\dotsc\}\sqcup\{+\infty\}

매트로이드에서 회로의 크기 중 최댓값은 밖둘레이다. 그래프의 순환 매트로이드에서 밖둘레는 그래프 내의 순환 중 가장 긴 것의 길이다. 순환이 없는 그래프(숲 그래프)는 밖둘레가 -\infty로 정의된다.[15]

그래프의 밖둘레가 가질 수 있는 값은 다음과 같다.

:\{3,4,5,\dotsc\}\sqcup\{+\infty,-\infty\}

유한 그래프의 밖둘레는 +\infty가 될 수 없다.

그래프의 변 연결도는 접합 매트로이드의 안둘레이다. 즉, 그래프에서 새 연결 성분을 만들기 위해 제거해야 하는 변의 최소 개수이다. 무변 그래프가 아닌 그래프는 변 연결도가 잘 정의되며, 무변 그래프의 경우 +\infty로 정의한다. 무한 그래프의 변 연결도는 임의의 기수 값을 가질 수 있다.[15]

최대 접합 크기는 접합 매트로이드의 밖둘레이다. 즉, 그래프에서 제거했을 때 그래프를 분리시키는 변 집합 중 가장 큰 크기이다. 무변 그래프가 아닌 그래프는 최대 접합 크기가 잘 정의되며, 무변 그래프의 경우 -\infty로 정의한다. 무한 그래프의 최대 접합 크기는 임의의 기수 값을 가질 수 있다.[15]

2. 2. 그래프 관점

그래프의 안둘레는 그 그래프 속의 순환 가운데 가장 짧은 순환의 길이이다. 순환을 갖지 않는 그래프(숲 그래프)의 경우, 안둘레는 무한대로 정의된다. 그래프의 안둘레가 가질 수 있는 값은 다음과 같다.

::\{3,4,5,\dotsc\}\sqcup\{+\infty\}

그래프의 밖둘레는 그래프 속의 순환의 길이들의 상한이다. 순환을 갖지 않는 그래프(숲 그래프)의 경우, 밖둘레는 -\infty로 정의된다. 그래프의 밖둘레가 가질 수 있는 값은 다음과 같다.

::\{3,4,5,\dotsc\}\sqcup\{+\infty,-\infty\}

유한 그래프의 밖둘레는 +\infty가 될 수 없다.

그래프의 '''홀수 둘레'''와 '''짝수 둘레'''는 각각 최단 홀수 순환과 최단 짝수 순환의 길이이다.

그래프의 '''둘레'''는 가장 긴 (단순) 순환의 길이이다.

2. 2. 1. 접합 매트로이드와 변 연결도

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

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

3. 성질

임의의 그래프 \{\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영어정규 그래프 Γ영어에 대하여, 다음 부등식이 성립한다.

2가 girthΓ영어를 나누지 못하는 경우(홀수)2가 girthΓ영어를 나누는 경우(짝수)



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

3. 1. 분리합집합

임의의 그래프들의 족 \{\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는 그래프의 분리합집합이다.

3. 2. 상계

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

차수 r영어정규 그래프 Γ영어에 대하여, 다음 부등식이 성립한다.

2가 girthΓ영어를 나누지 못하는 경우(홀수)2가 girthΓ영어를 나누는 경우(짝수)



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

4. 케이지 (Cage)

둘레가 *g*인 큐빅 그래프(모든 꼭지점의 차수가 3인 그래프) 중 가장 작은 그래프를 *g*-케이지 (또는 (3,*g*)-케이지)라고 한다. 피터슨 그래프는 유일한 5-케이지(둘레가 5인 가장 작은 큐빅 그래프)이며, 히우드 그래프는 유일한 6-케이지, 맥기 그래프는 유일한 7-케이지, 투테 8-케이지는 유일한 8-케이지이다.[3] 주어진 둘레에 대해 여러 개의 케이지가 존재할 수 있는데, 예를 들어 꼭지점이 70개인 비동형 10-케이지에는 발라반 10-케이지, 해리스 그래프, 해리스-웡 그래프가 있다.

히우드 그래프의 둘레는 6이다.

5. 둘레와 그래프 채색

에르되스 팔은 확률적 방법을 사용하여, 임의의 양의 정수 g와 χ에 대해, 안둘레가 g 이상이고 채색수가 χ 이상인 그래프가 존재함을 증명하였다.[4] 그는 n개의 정점에 대한 랜덤 그래프를, 각 변을 포함할지 여부를 확률 n(1-g)/g로 독립적으로 선택하여 형성할 경우, n이 무한대로 갈 때 확률이 1로 수렴하면서, 길이 g 이하의 순환이 최대 n/2개이지만, 크기가 n/2k인 독립 집합이 없음을 보였다. 따라서 각 짧은 순환에서 하나의 정점을 제거하면 둘레가 g보다 큰 더 작은 그래프가 남으며, 이 그래프에서 채색의 각 색상 클래스는 작아야 하므로 어떤 채색에서도 최소 k개의 색상이 필요하다.

높은 둘레와 채색수를 갖는 명시적인 그래프는, 유한체 상의 선형 군의 특정 케일리 그래프로 구성될 수 있다.[5] 이러한 그래프는 ''라마누잔 그래프''라고 불리며, 큰 확장 계수를 갖는다.

6. 관련 개념

그래프의 '''홀수 둘레'''와 '''짝수 둘레'''는 각각 최단 홀수 순환과 최단 짝수 순환의 길이이다. 한국어로는 각각 '''기내주'''(odd girth) 및 '''우내주'''(even girth)라고도 한다.

둘레는 수축 기하학(시스톨릭 기하학)에서 1-수축(1-systole) 또는 더 높은 수축으로 일반화될 수 있다.[6]

7. 계산

무방향 그래프의 둘레는 각 노드에서 너비 우선 탐색을 실행하여 계산할 수 있으며, 복잡도는 O(nm)이다. 여기서 n은 그래프의 정점 수이고, m은 모서리 수이다.[7] 실용적인 최적화 방법으로는 너비 우선 탐색의 깊이를 지금까지 발견된 가장 작은 사이클의 길이에 따라 달라지는 깊이로 제한하는 것이 있다.[8] 둘레가 짝수인 경우[9]와 그래프가 평면 그래프인 경우[10]에는 더 나은 알고리즘이 알려져 있다. 하한 측면에서 그래프의 둘레를 계산하는 것은 그래프에서 삼각형 찾기 문제를 해결하는 것만큼 어렵다.

참조

[1] 서적 Graph Theory Springer-Verlag
[2] MathWorld Girth
[3] 간행물 Cages http://www.win.tue.n[...]
[4] 간행물 Graph theory and probability
[5] 간행물 Elementary number theory, group theory, and Ramanujan graphs Cambridge University Press, Cambridge
[6] 간행물 On the (co)girth of a connected matroid
[7] 웹사이트 Question 3: Computing the girth of a graph http://webcourse.cs.[...] 2023-02-22
[8] 웹사이트 Shortest cycle https://tryalgo.org/[...] 2016-11-06
[9] 웹사이트 ds.algorithms - Optimal algorithm for finding the girth of a sparse graph? https://cstheory.sta[...] 2023-02-22
[10] 학술지 Computing the Girth of a Planar Graph in Linear Time 2013
[11] 서적 Graph Theory Springer-Verlag
[12] 간행물 Girth -- Wolfram MathWorld http://mathworld.wol[...]
[13] 간행물 Cages http://www.win.tue.n[...]
[14] 간행물 Graph theory and probability
[15] 저널
[16] 저널 Sur les assemblages de lignes http://resolver.sub.[...]



본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com