사이클 베이시스

수학의 한 분야인 그래프 이론에서, 비방향 그래프의 사이클 기준은 그래프의 사이클 공간의 기초를 이루는 단순한 사이클 집합이다.즉, 모든 이등도 하위 그래프를 기준 주기의 대칭적 차이로 표현할 수 있는 최소한의 주기 집합이다.

트리의 경로와 트리 외부의 단일 가장자리의 조합에 의해 형성된 사이클을 선택하여 해당 그래프의 스패닝 트리 또는 스패닝 포리스트에서 기본 사이클을 구성할 수 있다.또는 그래프의 가장자리가 양의 가중치를 갖는 경우 최소 가중치 기준은 다항식 시간으로 구성할 수 있다.

평면 그래프에서 그래프를 포함하는 경계 주기 집합은 주기 기준을 형성한다.평면 그래프의 최소 중량 사이클 기준은 이중 그래프의 고모리-후 트리에 해당한다.

정의들

주어진 그래프 G의 스패닝 서브그래프는 G 자체와 정점 집합은 동일하지만, 아마도 가장자리가 적을 수 있다.그래프 G, 즉 그 하위 그래프 중 하나는 각각의 정점이 짝수(사건 에지 수)를 갖는다면 오일러라고 한다.그래프의 모든 간단한 사이클은 오일러식 서브그래프지만 다른 사이클도 있을 수 있다.그래프의 주기 공간은 오일러식 서브그래프의 모음입니다.2요소 유한장 위에 벡터 공간을 형성한다.벡터 추가 연산은 둘 이상의 서브그래프의 대칭적 차이며, 대칭 차이 연산에 대한 인수에서 홀수 횟수로 나타나는 에지로 구성된 또 다른 서브그래프를 형성한다.^[1]

주기 기반은 각 기본 벡터가 단순한 주기를 나타내는 이 벡터 공간의 기초다.대칭적 차이를 이용해 모든 오일러 서브그래프를 구성하기 위해 조합할 수 있는 일련의 사이클로 구성되며, 이 속성에서는 최소가 된다.주어진 그래프의 모든 사이클 기준은 사이클 수가 같으며, 이는 사이클 공간의 치수와 같다.이 숫자를 그래프의 회로 순위라고 하며,${\displaystyle \mathrm{여기}}$서 $m$${\$$displaystyle$ m}은$($는) 그래프에서 가장자리 수$,$ n {\displaystyle $n}$은(는) 정점$수$, c {\$displaystyle c}$은(는$)$ 연결된 구성 요소의 수입니다.^[2]

특수 사이클 베이스

기본 사이클 베이스, 약한 기본 사이클 베이스, 희소성(또는 2-) 사이클 베이스 및 적분 사이클 베이스 등 몇 가지 특별한 유형의 사이클 베이스가 연구되었다.^[3]

유도 사이클

모든 그래프는 모든 사이클이 유도 사이클인 사이클 베이스를 가지고 있다.3-Vertex로 연결된 그래프에는 항상 주변 사이클, 제거가 나머지 그래프를 분리하지 않는 사이클로 구성된 기초가 존재한다.^[4][5]한 사이클에 하나의 에지를 추가하여 형성된 그래프 이외의 그래프에서 주변 사이클은 유도 사이클이어야 한다.

기본 사이클

$T{\displaystyle }$ ${\displaystyle$ $T$$}$이(가) 지정된 $그래프{\displaystyle }$ G ${\displaystyle G$의 스패닝 트리 또는 스패닝 포리스트이고 $e{\displaystyle }$ ${\displaystyle$ e$}$이(가) $T{\displaystyle }$ ${\$$displaystystyle$ T}에 속하지 않는 에지라면$$$,$$$e {\$displaystyle$ $ce$$}$이(으)로 정의된 $기본{\displaystyle {}_{}}$$$ ${\displaystyle {사이클}_{}}$이다.${\displaystyle }$$e{\displaystyle }$ ${\displaystyle$ $e$$}$의 끝점을 연결하는$$ $T{\displaystyle }$ ${\displaystyle T}$의 경로와 함께$$ e {\displaystyle $e$$정확히{\displaystyle }$ $m{\displaystyle }$- ${\displaystyle n}$+ c ${\displaystyle m-n+c}$ 기본$$ 사이클이 있으며, T ${\displaystyle T}$에 속하지 않는 각 에지마다 하나씩 있다$.$ 각 사이클은 다른$$ 기본 사이클에 $존재$하지 않는$$에지 e {\$displaystyle$ e$}$을(를) 포함하기 때문에 나머지 사이클과 선형적으로 독립적이다.따라서, 기본 사이클은 사이클 공간의 기초를 형성한다.^[1][2]이러한 방식으로 구성된 사이클 베이스를 기본 사이클 베이시스 또는 강력한 기본 사이클 베이시스라고 한다.^[3]

또한 기본 사이클 베이스가 기본인 트리를 지정하지 않고도 기본 사이클 베이스의 특성을 파악할 수 있다.각 주기가 다른 기본 주기에 포함되지 않은 에지를 포함하는 경우, 즉 각 주기가 다른 기본 주기에 독립적인 경우에만 주어진 주기 기준이 기본인 트리가 존재한다.독립성 속성을 가지고 있고 $G{\displaystyle }$ ${\displaystyle G}$의 기반이 되는 정확한 수의 사이클이 있는 경우에만$$ 사이클 $컬렉션$이 G$${\$displaystyle G$}의 기본 사이클 기반인 것으로 뒤따른다$.$^[6]

약한 기본 사이클

각 사이클이 초기 사이클에 포함되지 않은 적어도 하나의 에지를 포함하는 선형 순서로 사이클을 배치할 수 있는 경우 사이클 베이스를 약하게 기초라고 한다.기본 사이클 기준은 (모든 에지 순서에 대해) 자동으로 약하게 기본이다.^[3][7]그래프의 모든 사이클 기준이 약하게 기초적인 경우, 그래프의 모든 마이너도 마찬가지다.이 성질을 바탕으로 매 사이클의 기초가 약하게 되는 그래프(및 멀티그램)의 등급은 금지된 5개의 미성년자, 즉 사각 피라미드의 그래프, 4버텍스 사이클의 모든 모서리를 두 배로 하여 형성된 멀티그램, 사면체의 두 모서리를 두 배로 하여 형성된 두 개의 멀티그램, 그리고 멀티그램이 특징지어질 수 있다.삼각형의 가장자리를 세 배로 ^[8]하여

페이스 사이클

연결된 유한 평면 그래프가 평면에 내장되는 경우, 임베딩의 각 면은 가장자리의 사이클에 의해 경계된다.한 면은 반드시 언바운드(그래프의 정점으로부터 임의로 멀리 떨어진 점을 포함한다)이며, 나머지 면은 경계된다.평면 그래프에 대한 오일러의 공식에 따르면 정확히 ${\displaystyle m}$- n${\displaystyle }$+ ${\displaystyle 1}$ ${\displaystyle m-n+1}$개의$$ 경계면이 있다.모든 얼굴 주기 집합의 대칭적 차이는 해당 얼굴 집합의 경계이며, 경계 면 집합이 서로 다른 경계를 가지고 있기 때문에, 동일한 세트를 얼굴 주기의 대칭적 차이로서 한 가지 이상의 방법으로 나타낼 수 없다. 이것은 얼굴 주기 집합이 선형적으로 독립적이라는 것을 의미한다.충분한 주기의 선형 독립 집합으로서, 반드시 주기 기준을 형성한다.^[9]이것은 항상 약하게 기초적인 주기 기반이며, 그래프의 내장이 외부 평면인 경우에만 기본이다.

임베딩의 모든 면이 위상학적 디스크가 되도록 다른 표면에 적절히 내장된 그래프의 경우 일반적으로 얼굴 사이클만 사용하는 사이클 기준이 존재한다는 것은 사실이 아니다.이러한 임베딩의 얼굴 주기는 모든 오일러 서브그래프의 적절한 부분집합을 생성한다.호몰로지 그룹 $H{\displaystyle {}_{}}$ ${\displaystyle {2\mathrm{}}_{}}$(${\displaystyle S}$, ${\displaystyle {\mathrm{}}_{}}$ ${\displaystyle {}_{}}$) ${\displaystyle H_{2}(S,\mathb {Z} _{2})$는 주어진 $표면{\displaystyle }$ S ${\displaystyle S}$의 경계로 나타낼 수 없는 오일러 서브그래프를 특징으로$$ 한다.맥 레인의 평면성 기준은 이 아이디어를 사용하여 사이클 베이스 측면에서 평면 그래프를 특성화한다. 즉, 그래프의 각 가장자리가 최대 2 베이시스 사이클에 참여하는 기준인 ^[3]희소 사이클 베이스를 가진 경우 및 2 베이스를 가진 경우에만 유한 비방향 그래프가 평면 그래프를 평면적으로 나타낸다.평면 그래프에서 경계면 집합에 의해 형성된 주기 기준은 반드시 희박하며, 반대로 그래프의 희박 주기 기준은 반드시 그래프를 포함하는 평면형 면 집합을 형성한다.^[9][10]

적분 베이스

그래프의 사이클 공간은 그래프의 각 꼭지점에 대한 점과 그래프의 각 가장자리에 대한 선 세그먼트가 있는 단순 복합체의 호몰로지 그룹 H ${\displaystyle {1\mathrm{}}_{}G}$, ${\displaystyle {\mathbb{}}_{}}$ ${\displaystyle {}_{}}$) ${\displaystyle H_{1}(G,\mathb {Z} _{2})$으로 호몰로지 이론을 사용하여 해석할 수 있다.This construction may be generalized to the homology group ${\displaystyle H_{1}(G,R)}$ over an arbitrary ring ${\displaystyle R}$. An important special case is the ring of integers, for which the homology group ${\displaystyle H_{1}(G,\mathbb {Z} )}$ is a free abelian group, a subgroup of그래프의 가장자리에 의해 생성된 자유 아벨 그룹덜 추상적으로, 이 그룹은 주어진 그래프의 가장자리에 임의의 방향을 할당하여 구성할 수 있다. 그러면 $H{\displaystyle {}_{}}$ ${\displaystyle {1\mathrm{}}_{}}$( ${\displaystyle G\mathbb{}}$, ${\displaystyle Z}$) ${\displaystyle H_{1}(G,\mathb {Z})$의 요소들은 각 꼭지점에서 들어오는 가장자리 라벨의 합이 합과 같은 속성의 정수로 그래프 가장자리 라벨링이다$$.f 나가는 가장자리 라벨.그룹 연산은 이러한 라벨 벡터를 추가하는 것이다.적분 주기 기준은 이 그룹을 생성하는 단순한 주기 집합이다.^[3]

최소 중량

그래프의 가장자리에 실제 수 가중치가 부여된 경우, 하위 그래프의 가중치는 가장자리 가중치의 합으로 계산할 수 있다.사이클 공간의 최소 중량 기준은 반드시 사이클 베이시스: 베블렌의 정리에 ^[11]의해 단순한 사이클 자체가 아닌 모든 오일러식 서브그래프는 여러 개의 단순한 사이클로 분해될 수 있는데, 이것은 반드시 더 작은 무게를 가진다.

벡터 공간과 매트로이드에 있는 베이스의 표준 특성에 의해, 최소 중량 주기 기준은 사이클의 가중치 합계를 최소화할 뿐만 아니라, 사이클 가중치의 다른 단조 조합도 최소화한다.예를 들어, 가장 긴 주기의 가중치를 최소화하는 것이 사이클 기준이다.^[12]

다항 시간 알고리즘

어떤 벡터 공간에서, 그리고 보다 일반적으로 어떤 매트로이드에서, 최소 무게 기준은 그들의 무게에 따라 정렬된 순서에 따라 한 번에 하나씩 잠재적 기본 요소를 고려하는 탐욕스러운 알고리즘에 의해 발견될 수 있으며, 이전에 선택한 기본 요소와 선형적으로 독립된 요소를 기초로 포함하는 것이다.선형 독립성 시험은 가우스 제거를 통해 수행할 수 있다.그러나, 비방향 그래프에는 기하급수적으로 큰 일련의 단순한 사이클이 있을 수 있으므로, 그러한 사이클을 모두 생성하고 테스트하는 것은 계산적으로 불가능할 것이다.

Horton(1987)은 모든 에지 중량이 양수인 그래프에서 최소 중량 기준을 찾기 위한 첫 번째 다항 시간 알고리즘을 제공했다.그의 알고리즘은 이 생성 및 테스트 접근방식을 사용하지만 생성된 사이클을 Horton 사이클이라고 불리는 $작은{\displaystyle }$ O${\displaystyle }$( ${\displaystyle m}$ n$){\displaystyle O(mn)}$ 사이클로$$ 제한한다.호튼 사이클은 주어진 그래프의 최단 경로 트리의 기본 사이클이다.최대 n개의 서로 다른 최단 경로 트리(각 출발 정점당 하나씩)가 있으며 각각 m 기본 주기보다 작아서 총 Horton 사이클 수에 대한 경계를 제공한다.Horton이 보여준 것처럼, 최소 체중 주기 기준의 모든 사이클은 Horton 사이클이다.^[13]Dijkstra 알고리즘을 사용하여 각 최단 경로 트리를 찾은 다음 가우스 제거를 사용하여 탐욕스러운 기본 알고리즘의 테스트 단계를 수행하면 최소 체중 주기 기준에 대한 다항 시간 알고리즘이 실행된다.후속 연구자들은 이 문제에 대한 개선된 알고리즘을 개발하여,^{[14][15][16][17]} $M{\displaystyle }$ ${\displaystyle m}$ 가장자리와$$ $n{\displaystyle }$ ${\$$displaystyle n$$}$ 정점을$$ $(m 2n$/ $log ⁡$)에 대한 그래프에서 최소 체중 주기 기준을 찾기 위한 최악의 시간 복잡성을 줄였다$.$^[18]

NP-강경성

가능한 최소 중량으로 기본적 기초를 찾는 것은 쌍방향 거리의 평균을 최소화하는 신장 트리를 찾는 문제와 밀접하게 관련되어 있다. 둘 다 NP-hard이다.^[19]약하게 기초적인 최소 중량을 찾는 것 또한 NP-hard이며,^[7] 대략적으로 MAXSNP-hard이다.^[20]음의 가중치와 음의 가중치가 허용되는 경우, 최소 주기 기준(제한 없이)을 찾는 것도 NP-강성이며, 이는 해밀턴 주기를 찾는 데 사용될 수 있기 때문이다: 그래프가 해밀턴 사이클이고 모든 가장자리가 -1이면 최소 가중치 기준에는 반드시 적어도 하나의 해밀턴 사이클이 포함된다.

평면 그래프에서

평면 그래프의 최소 중량 주기 기준은 경계면에 의해 형성된 기준과 반드시 동일하지는 않다. 즉, 면에 없는 사이클을 포함할 수 있으며, 일부 면은 최소 중량 주기 기준의 사이클로 포함되지 않을 수 있다.그러나 두 사이클이 서로 교차하지 않는 최소 중량 사이클 기준이 존재한다. 즉, 기준의 두 사이클마다 사이클이 경계면의 분리 하위 세트를 둘러싸거나, 두 사이클 중 하나가 다른 사이클을 감싸고 있다.이 사이클 집합은 주어진 평면 그래프의 이중 그래프에서 절삭 공간의 최소 중량 기준인 이중 그래프의 고모리-후 트리를 형성하는 절삭 집합에 해당한다.^[21]이러한 이중성에 기초하여 평면 그래프의 최소 체중 주기 기준의 암묵적 표현을 $시간{\displaystyle }$ O${\displaystyle (n}$ ${\displaystyle {\log }^{}}$ ${\displaystyle {3\mathrm{}}^{}}$ ${\displaystyle {}^{}n}$) ${\displaystyle O(n\log ^{3}n)}$에 구성할 수 있다$.$^[22]

적용들

사이클 베이스는 대중교통 시스템의 일정 결정 문제 등 주기적인 스케줄링 문제를 해결하기 위해 사용되어 왔다.이 애플리케이션에서, 사이클 기준의 사이클은 문제를 해결하기 위한 정수 프로그램의 변수에 해당한다.^[23]

구조 강성 및 운동학 이론에서 사이클 베이스는 구조물의 강성 또는 움직임을 예측하기 위해 해결할 수 있는 비중복 방정식의 시스템 설정 과정을 안내하는 데 사용된다.이 적용에서 최소 또는 거의 최소의 중량 사이클 베이스는 방정식의 단순한 시스템으로 이어진다.^[24]

분산 컴퓨팅에서는 알고리즘이 안정화되는 데 필요한 단계 수를 분석하기 위해 사이클 베이스를 사용해 왔다.^[25]

생물정보학에서는 게놈 서열 데이터에서 happlotype 정보를 결정하기 위해 사이클 베이스를 사용해 왔다.^[26]RNA의 3차 구조를 분석하는 데도 사이클 베이스가 사용되었다.^[27]

3차원 표면에서 추출한 점의 가장 가까운 인접 그래프의 최소 중량 사이클 기준을 사용하여 표면의 재구성을 얻을 수 있다.^[28]

척수학에서 분자 그래프의 최소 주기 기준은 가장 작은 고리의 집합이라고 한다.^[29][30][31]

참조