순환 그래프

그래프 이론에서 순환 그래프는 다른 정점까지 정점을 가져가는 주기적인 대칭 그룹에 의해 작용하는 비방향 그래프다.때로는 순환 그래프라고 부르기도 하지만,^[1] 이 용어는 다른 의미를 가지고 있다.

등가정의

순환 그래프는 몇 가지 동등한 방법으로 설명할 수 있다.^[2]

• 그래프의 자동형성 그룹에는 그래프의 정점에 대해 트랜스적으로 작용하는 순환형 부분군이 포함된다.즉, 그래프에는 정점의 주기적인 순열인 그래프 자동형이 있다.
• 그래프는 순환 행렬인 인접 행렬을 가지고 있다.
• 그래프의 n 정점은 x와 (x + d) mod n으로 번호가 매겨진 두 정점이 인접한 경우, z와 (z + d) mod n으로 번호가 매 2 정점이 인접하는 방식으로 0에서 n - 1까지 번호를 매길 수 있다.
• 그래프는 정점이 일반 다각형의 모서리에 놓이도록 그릴 수 있으며(아마도 교차점이 있을 것이다), 폴리곤의 모든 회전 대칭도 도면의 대칭이다.
• 그래프는 주기적인 그룹의 Cayley 그래프 입니다.^[3]

예

모든 사이클 그래프는 2모듈로 4정점을 갖는 모든 크라운 그래프와 마찬가지로 순환 그래프다.

순서 n의 Paley 그래프(여기서 n은 1 modulo 4)는 정점이 0에서 n - 1까지의 숫자이고 정점이 2차 잔류물 모듈로 n이면 두 정점이 인접해 있는 그래프다.가장자리의 유무는 두 꼭지수의 차이 모듈로 n에만 의존하므로, 모든 Paley 그래프는 순환 그래프다.

모든 뫼비우스 사다리는 모든 완전한 그래프와 마찬가지로 순환 그래프다.완전한 초당적 그래프는 양쪽에 동일한 수의 정점이 있는 경우 순환적 그래프를 의미한다.

만약 두 숫자 m과 n이 비교적 프라임이라면, m × n 루크의 그래프(m × n 체스판의 각 사각형에 대한 꼭지점과 체스 루크가 한 번의 움직임으로 이동할 수 있는 각 두 사각형에 대한 가장자리가 있는 그래프)는 순환 그래프다.이는 대칭이 부분군으로 주기 그룹 C_mn${\displaystyle }$≃ ${\displaystyle \simeq }$C×C를_mn 포함하기 때문이다.보다 일반적으로, 이 경우, 어떤 m-와 n-vertex 서큘러 사이에 있는 그래프의 텐서 산물은 그 자체로 순환 물질이다.^[2]

Ramsey 숫자에 대해 알려진 많은 하한은 작은 최대 구획과 작은 최대 독립 집합을 갖는 순환 그래프의 예에서 온다.^[1]

구체적인 예

The circulant graph ${\displaystyle C_{n}^{s_{1},\ldots ,s_{k}}}$ with jumps ${\displaystyle s_{1},\ldots ,s_{k}}$ is defined as the graph with ${\displaystyle n}$ nodes labeled ${\displaystyle 0,1,\ldots ,n-1}$ where each node i is adjacent to 2k nodes $i{\displaystyle }$± ${\displaystyle {s\mathrm{}}_{}}$ ${\displaystyle {}_{}}$,${\displaystyle }$…,${\displaystyle }$i${\displaystyle }$± ${\displaystyle s}$ ${\displaystyle mod}$ n ${\displaystyle i\pm s_{1},\ldots, i\pm s_{k}\mod n}$.

• 그래프 ${\displaystyle {Cn}_{}^{}}$ ${\displaystyle {{s\mathrm{}}_{}}_{}^{}}$ 1${\displaystyle {{}_{}}_{}^{}}$,${\displaystyle {}_{}^{}}$… ,${\displaystyle {{}_{}}_{}^{}}$ ${\displaystyle {k_{}}_{}^{}}$ ${\$${\displaystyle {s\_}_{}}$${k}}$는 ${\displaystyle gcd(n}$, s 1${\displaystyle }$, … ,${\displaystyle {}_{}{s\mathrm{}}_{}{}_{}}$ )${\displaystyle }$=$$1$displaysty \gcd(n,s_{1},\ldots_{k}=1$}인 경우에만 연결된다$.$
• 11<>s≤, ⋯<>매우 k{\displaystyle 1\leq s_{1}<, \cdots <, s_{k}}고정이 정수가 아닌 다음 신장 트리의 수)이 n{\displaystyle a_{n}}의 복귀 관계를 만족시킬 n2{\displaystyle t(C_{n}^{s_{1},s_{k},\ldots})=na_{n}^{2}}n(Cns1,…, skm그리고 4.9초 만)하루에 500파운드. 2k${\displaystyle {{}_{}-}^{}}$ ${\displaystyle 1^{}}$ ${\$ 2$^{s_{k}-1$
  • 특히 $t{\displaystyle ({\mathrm{}}_{}^{}}$ 1,${\displaystyle 2_{}^{}}$)${\displaystyle }$= n ${\displaystyle F}$ ${\displaystyle {\mathrm{}}_{}^{}}$ 2 ${\$}2$}}:$ 여기서$$ $F{\displaystyle {}_{}}$ ${\displaystyle n_{}}$ ${\$는 n번째 피보나치 수이다.

자가완성순환제

자기 보완 그래프는 모든 가장자리를 비엣지로 대체하고 그 반대의 경우 이형 그래프를 생성하는 그래프를 말한다.예를 들어, 5Vertex 사이클 그래프는 자가 완성형이며 순환형 그래프이기도 하다.보다 일반적으로 프라임 오더에 대한 모든 창백한 그래프는 자기 완성 순환 그래프다.^[4]Horst Sachs는 n의 모든 주요 요인이 1 modulo 4와 일치한다는 속성을 숫자 n이 가지고 있다면, n 정점을 가진 자기 완성 순환체가 존재한다는 것을 보여주었다.그는 n의 다른 어떤 값도 자기완성 순환제를 존재할 수 없다는 것, 이 조건 또한 필요하다고 추측했다.^[2][4]그 추측은 빌프레드에 의해 약 40년 후에 증명되었다.^[2]

옴의 추측

원형 그래프의 주기적 번호 매기는 0에서 n - 1까지의 숫자로 그래프의 정점을 표시하는 것으로 정의하며, 만약 x와 y로 번호가 매 두 정점이 인접한 경우, (z - x + y) mod n과 z로 번호가 매겨진 정점마다 인접하게 된다.마찬가지로, 순환기 번호 매트릭스는 그래프의 인접 행렬이 순환기 행렬인 정점의 번호 매칭이다.

a를 n에 상대적으로 소수인 정수로 하고, b를 어떤 정수로 한다.그런 다음 도끼 + b에 숫자 x를 사용하는 선형 함수는 순환수 번호를 다른 순환수 번호로 변환한다.Andrahs Ahdam은 이러한 선형 지도가 순환체 특성을 보존하면서 순환체 그래프의 번호를 다시 매기는 유일한 방법이라고 추측했다. 즉, G와 H가 서로 다른 번호의 이소형 순환체 그래프라면, G에 대한 번호를 H에 대한 번호 매김으로 변환하는 선형 지도가 있다.그러나, 아람의 추측은 이제 거짓으로 알려져 있다.그래프 G와 H는 각각 16개의 정점을 가진 그래프 G와 H에 의해 주어진다. G의 꼭지점 x는 6개의 이웃 x ± 1, x ± 2 및 x ± 7 모듈로 16에 연결되어 있는 반면, H의 이웃 6개는 x ± 2, x ± 3 및 x ± 5 모듈로 16이다.이 두 그래프는 이형이지만 이형성은 선형 지도로는 실현할 수 없다.^[2]

토이다의 추측은 인접 그래프 정점 사이의 모든 차이가 정점 수에 상대적으로 가장 큰 비중을 차지하는 특별한 종류의 순환 그래프만을 고려함으로써 아힘의 추측을 반박한다.이러한 정제된 추측에 따르면, 이러한 특별한 순환 그래프들은 모든 대칭이 수치 modulo n의 기본 첨가물 그룹의 대칭에서 오는 속성을 가져야 한다.2001년과 2002년 두 그룹에 의해 증명되었다.^[5][6]

알고리즘 질문

순환 그래프에는 다항 시간 인식 알고리즘이 있으며, 순환 그래프에 대한 이항형성 문제는 다항 시간 내에 해결할 수 있다.^[7][8]

참조

외부 링크

• Weisstein, Eric W. "Circulant Graph". MathWorld.