안둘레
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.
1. 개요
안둘레는 그래프 이론과 매트로이드 이론에서 사용되는 개념으로, 그래프 또는 매트로이드의 "최소 순환 크기"를 의미한다. 그래프의 안둘레는 그래프 내 순환의 최소 길이를, 매트로이드의 안둘레는 회로 크기의 최솟값을 나타낸다. 안둘레와 반대되는 개념으로 밖둘레가 있으며, 그래프 관점에서는 순환의 길이 상한, 매트로이드 관점에서는 회로 크기의 최댓값을 의미한다. 안둘레는 그래프의 변 연결도, 케이지, 그래프 채색 등 다양한 개념과 관련되며, 계산 방법도 존재한다.
더 읽어볼만한 페이지
- 매트로이드 이론 - 매트로이드 마이너
매트로이드 마이너는 매트로이드에서 부분집합 제거 또는 제한 연산을 반복하여 얻어지는 매트로이드로, 매트로이드의 성질 보존, 구조 분석, 그래프 이론과의 연결, 여러 종류의 매트로이드, 구조 파악 및 복잡성 분석, 효율적인 테스트 알고리즘 개발 등에 활용된다. - 매트로이드 이론 - 탐욕 알고리즘
탐욕 알고리즘은 각 단계에서 가장 좋아 보이는 선택을 하는 알고리즘 설계 패러다임으로, 최적 부분 구조와 탐욕 선택 속성을 가진 문제에 최적의 해를 보장하며, 다익스트라, 프림, 크루스칼 알고리즘 등에 사용된다. - 그래프 이론 - 다이어그램
다이어그램은 2차원 기하학적 기호를 사용하여 정보를 시각적으로 표현하는 기술로, 과학, 공학, IT, 비즈니스 등 다양한 분야에서 활용되며 정보를 간략하게 나타내고 시각적 사고를 돕는다. - 그래프 이론 - 쾨니히스베르크의 다리 문제
쾨니히스베르크의 다리 문제는 프레겔 강에 놓인 7개의 다리를 한 번씩만 건너 출발점으로 되돌아올 수 있는지 묻는 문제로, 오일러에 의해 그래프 이론적으로 분석되어 해결되었으며 그래프 이론의 탄생에 기여했다.
안둘레 | |
---|---|
그래프 이론의 핵심 속성 | |
종류 | 그래프 불변량 |
기호 | g(G) 또는 girth(G) |
정의 | 그래프 G에 포함된 가장 짧은 주기의 길이 |
속성 | 루프가 있는 경우 1 루프가 없는 경우, 병렬 모서리가 있으면 2 삼각형이 없는 그래프는 거스가 4 이상임 |
2. 정의
그래프의 '''안둘레'''는 그 그래프에 포함된 가장 짧은 순환의 길이다. 순환이 없는 그래프(숲 그래프)의 경우에는 안둘레가 무한대로 정의된다.[6] 그래프의 '''홀수 둘레'''와 '''짝수 둘레'''는 각각 최단 홀수 순환과 최단 짝수 순환의 길이이다.
그래프의 '''둘레'''는 가장 긴 순환의 길이이다.
2. 1. 매트로이드 관점
매트로이드에서 회로의 크기 중 최솟값을 안둘레(girth)라고 한다. 그래프의 순환 매트로이드에서 안둘레는 그래프 내의 순환 중 가장 짧은 것의 길이다. 순환이 없는 그래프(숲 그래프)는 안둘레가 무한대로 정의된다.[15]그래프의 안둘레가 가질 수 있는 값은 다음과 같다.
:
매트로이드에서 회로의 크기 중 최댓값은 밖둘레이다. 그래프의 순환 매트로이드에서 밖둘레는 그래프 내의 순환 중 가장 긴 것의 길이다. 순환이 없는 그래프(숲 그래프)는 밖둘레가 로 정의된다.[15]
그래프의 밖둘레가 가질 수 있는 값은 다음과 같다.
:
유한 그래프의 밖둘레는 가 될 수 없다.
그래프의 변 연결도는 접합 매트로이드의 안둘레이다. 즉, 그래프에서 새 연결 성분을 만들기 위해 제거해야 하는 변의 최소 개수이다. 무변 그래프가 아닌 그래프는 변 연결도가 잘 정의되며, 무변 그래프의 경우 로 정의한다. 무한 그래프의 변 연결도는 임의의 기수 값을 가질 수 있다.[15]
최대 접합 크기는 접합 매트로이드의 밖둘레이다. 즉, 그래프에서 제거했을 때 그래프를 분리시키는 변 집합 중 가장 큰 크기이다. 무변 그래프가 아닌 그래프는 최대 접합 크기가 잘 정의되며, 무변 그래프의 경우 로 정의한다. 무한 그래프의 최대 접합 크기는 임의의 기수 값을 가질 수 있다.[15]
2. 2. 그래프 관점
그래프의 안둘레는 그 그래프 속의 순환 가운데 가장 짧은 순환의 길이이다. 순환을 갖지 않는 그래프(숲 그래프)의 경우, 안둘레는 무한대로 정의된다. 그래프의 안둘레가 가질 수 있는 값은 다음과 같다.::
그래프의 밖둘레는 그래프 속의 순환의 길이들의 상한이다. 순환을 갖지 않는 그래프(숲 그래프)의 경우, 밖둘레는 로 정의된다. 그래프의 밖둘레가 가질 수 있는 값은 다음과 같다.
::
유한 그래프의 밖둘레는 가 될 수 없다.
그래프의 '''홀수 둘레'''와 '''짝수 둘레'''는 각각 최단 홀수 순환과 최단 짝수 순환의 길이이다.
그래프의 '''둘레'''는 가장 긴 (단순) 순환의 길이이다.
2. 2. 1. 접합 매트로이드와 변 연결도
다중 그래프 의 '''변 연결도'''(邊連結度, edge connectivity영어)는 그 접합 매트로이드 의 안둘레이다.[15] 즉, 그래프 의 가장 작은 접합의 크기로, 새로운 연결 성분을 만들기 위해 제거해야 하는 변의 수의 최솟값이다. 무한 그래프의 경우, 변 연결도는 (안둘레와 달리) 임의의 기수 값을 가질 수 있다. 무변 그래프가 아닌 모든 다중 그래프는 하나 이상의 접합을 가지므로, 이 경우 변 연결도는 잘 정의된다. 무변 그래프의 경우, 변 연결도는 로 정의한다.마찬가지로, 다중 그래프 의 접합 매트로이드의 밖둘레 (접합의 크기의 상한) 역시 정의할 수 있으며, 이를 '''최대 접합 크기'''(maximum bond size영어)라고 한다. 무한 그래프의 경우, 최대 접합 크기는 (밖둘레와 달리) 임의의 기수 값을 가질 수 있다. 무변 그래프가 아닌 모든 다중 그래프는 하나 이상의 접합을 가지므로, 이 경우 최대 접합 크기는 잘 정의된다. 무변 그래프의 경우, 최대 접합 크기는 로 정의한다.
3. 성질
임의의 그래프 에 대하여, 다음이 성립한다.
:
:
:
:
여기서 는 그래프의 분리합집합이다.
꼭짓점이 n영어개인 유한 그래프의 밖둘레는 n영어 이하이며, 이 상계는 해밀턴 순환에 의하여 포화된다. 즉, 밖둘레가 n영어인 것은 해밀턴 순환을 갖는 것과 동치이다.
차수가 r영어인 정규 그래프 Γ영어에 대하여, 다음 부등식이 성립한다.
2가 girthΓ영어를 나누지 못하는 경우(홀수) | 2가 girthΓ영어를 나누는 경우(짝수) |
---|---|
이 부등식을 포화시키는 정규 그래프를 '''무어 그래프'''(Moore graph영어)라고 한다.
3. 1. 분리합집합
임의의 그래프들의 족 에 대하여, 다음이 성립한다.:
:
:
:
여기서 는 그래프의 분리합집합이다.
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-케이지, 해리스 그래프, 해리스-웡 그래프가 있다.
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. 계산
무방향 그래프의 둘레는 각 노드에서 너비 우선 탐색을 실행하여 계산할 수 있으며, 복잡도는 이다. 여기서 은 그래프의 정점 수이고, 은 모서리 수이다.[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