대칭 그래프
Symmetric graph
그래프 이론의 수학적 분야에서, G의 인접한 정점 u1(v와12 u)의2 두 쌍이 주어진 경우, 자동형성이 있는 경우, 그래프 G는 대칭(또는 호 변환)이다.
그런
즉, 그래프의 자동형성 그룹이 순서가 지정된 인접 정점 쌍(즉, 방향을 갖는 것으로 간주되는 가장자리)에서 전이적으로 작용하는 경우 그래프는 대칭이다.[2]이러한 그래프를 1아크[2] 변환 또는 플래그 변환이라고도 한다.[3]
정의에 의해(u와1 u를2 무시) 정점이 분리되지 않은 대칭 그래프도 정점 변환이어야 한다.[1]위의 정의가 한 에지와 다른 에지를 매핑하므로 대칭 그래프도 에지 변환이 되어야 한다.단, 엣지 변환 그래프는 a-b가 c-d에 매핑될 수 있지만 d-c에는 매핑되지 않을 수 있으므로 대칭적일 필요는 없다.항성 그래프는 정점이나 대칭이 아닌 가장자리-변환성의 간단한 예다.추가 예로서, 반대칭 그래프는 에지 변환 및 정규 그래프지만 정점 변환은 아니다.
| 자동화에 의해 정의된 그래프 패밀리 | ||||
|---|---|---|---|---|
| 거리 변환의 | → | 거리 규칙의 | ← | 매우 규칙적인. |
| ↓ | ||||
| 대칭(대칭 변환) | ← | t-변환, t ≥ 2 | 꼬불꼬불한 | |
| ↓ | ||||
| (연결된 경우) 정점 및 에지 변환 | → | 가장자리-변환적이고 규칙적인 | → | 가장자리-변환성 |
| ↓ | ↓ | ↓ | ||
| 정점 변환의 | → | 정칙의 | → | (양립할 경우) 복엽의 |
| ↑ | ||||
| 케이리 그래프 | ← | 무궤도적 | 비대칭의 | |
따라서 연결된 모든 대칭 그래프는 정점-변환성 및 에지-변환성이어야 하며, 그 반전은 홀수도의 그래프의 경우 참이다.[3]단, 짝수 도로는 정점-변환성 및 에지-변환성이지만 대칭은 아닌 연결된 그래프가 존재한다.[4]이러한 그래프를 반투명이라고 한다.[5]가장 작게 연결된 반투명 그래프는 Holt의 그래프인데, 도 4와 27 정점을 가지고 있다.[1][6]혼란스럽게, 일부 저자들은 "대칭 그래프"라는 용어를 호 변환 그래프보다는 정점 변환적이고 에지 변환적인 그래프를 의미하기 위해 사용한다.그러한 정의는 위의 정의에서 제외되는 반투명 그래프를 포함할 것이다.
거리 변환 그래프는 인접한 정점 쌍(즉, 정점이 1 떨어져 있는 거리)을 고려하는 대신, 정의는 각각 동일한 거리에 있는 두 쌍의 정점 쌍을 포함한다.그러한 그래프는 정의상 자동으로 대칭된다.[1]
t-arc는 시퀀스의 두 개의 연속 정점이 인접하고 반복 정점이 2계단 이상 떨어져 있도록 t + 1 정점의 시퀀스로 정의된다.t-변환 그래프는 자동형 집단이 t-arcs에서 전이적으로 작용하지만 (t + 1)-arc에서는 작용하지 않는 그래프다.1-Arc는 단순히 가장자리이기 때문에 일부 t의 경우 도 3 이상의 모든 대칭 그래프는 t-변환적이어야 하며 t의 값을 사용하여 대칭 그래프를 추가로 분류할 수 있다.예를 들어, 큐브는 2-변환적이다.[1]
예
정점 수에 관계없이 대칭 그래프의 두 가지 기본 패밀리는 주기 그래프(2도)와 전체 그래프다.추가 대칭 그래프는 정점과 정점, 정방형, 정방형, 정방형, 정방형, 정방형, 정방형, 정방형, 정방형 다면체의 가장자리에 의해 형성된다.큐브를 n차원으로 확장하면 하이퍼큐브 그래프(2정점n 및 도 n)가 제공된다.마찬가지로, 8각형에서 n 치수로 확장하면 교차 폴리토프의 그래프가 제공되는데, 이 그래프 제품군(2n 정점과 2n-2)은 칵테일 파티 그래프라고 부르기도 한다. 칵테일 파티 그래프는 가장자리 집합을 가진 완전한 그래프로서 완벽한 일치를 제거한다.정점 수가 2n인 대칭 그래프의 추가 패밀리는 정점 2n의 전체 양분 그래프 K와n,n 크라운 그래프가 있다.많은 다른 대칭 그래프는 순환 그래프(전부는 아님)로 분류할 수 있다.
Rado 그래프는 정점이 무한히 많고 도수가 무한히 많은 대칭 그래프의 예를 형성한다.
입방 대칭 그래프
대칭 조건과 그래프를 세제곱(즉, 모든 정점에는 도 3이 있음)이라는 제한 조건을 결합하면 상당히 강한 조건이 산출되며, 그러한 그래프는 나열할 수 있을 정도로 드물다.그들은 모두 짝수의 정점을 가지고 있다.포스터 인구 조사와 그 확대는 그러한 목록들을 제공한다.[7]포스터 인구조사는 1930년대에 로널드 M에 의해 시작되었다. 포스터는 벨 연구소에 고용되어 있을 때,[8] 1988년(포스터가[1] 92세였을 때) 당시 포스터 센서스(입방 대칭 그래프를 512정점까지 모두 나열한 것)가 책 형태로 출판되었다.[9]목록의 처음 13개 항목은 최대 30개의[10][11] 정점을 갖는 입방 대칭 그래프(이 중 10개는 거리 변환성이며 예외는 다음과 같다):
| 정점 | 지름 | 둘레 | 그래프 | 메모들 |
|---|---|---|---|---|
| 4 | 1 | 3 | 전체4 그래프 K | 거리-변환, 2-변환 |
| 6 | 2 | 4 | 전체 초당적 그래프3,3 K | 거리-변환, 3차원-변환성 |
| 8 | 3 | 4 | 큐브의 꼭지점과 가장자리 | 거리-변환, 2-변환 |
| 10 | 2 | 5 | 피터슨 그래프 | 거리-변환, 3차원-변환성 |
| 14 | 3 | 6 | 히우드 그래프 | 거리-변환, 4-변환 |
| 16 | 4 | 6 | 뫼비우스칸토르 그래프 | 2차 변환 |
| 18 | 4 | 6 | 파푸스 그래프 | 거리-변환, 3차원-변환성 |
| 20 | 5 | 5 | 도데카헤드론의 꼭지점과 가장자리 | 거리-변환, 2-변환 |
| 20 | 5 | 6 | 데스아게네스 그래프 | 거리-변환, 3차원-변환성 |
| 24 | 4 | 6 | 나우루 그래프(일반화된 피터슨 그래프 G(12,5) | 2차 변환 |
| 26 | 5 | 6 | F26A 그래프[11] | 1-510 변환기 |
| 28 | 4 | 7 | 콕시터 그래프 | 거리-변환, 3차원-변환성 |
| 30 | 4 | 8 | 투테-콕시터 그래프 | 거리-변환, 5-변환 |
다른 잘 알려진 세제곱 대칭 그래프는 Dyck 그래프, 포스터 그래프, Biggs-Smith 그래프 등이다.포스터 그래프와 Biggs-Smith 그래프와 함께 위에 열거된 10개의 거리 변환 그래프는 유일하게 세제곱 거리 변환 그래프다.
특성.
대칭 그래프의 정점 연결도는 항상 d도와 동일하다.[3]대조적으로, 일반적으로 정점 변환 그래프의 경우, 정점 연결도는 2(d + 1)/3으로 제한된다.[2]
3도 이상의 t-변환 그래프는 둘레가 최소 2(t – 1)이다.단, t 8 8에 대한 도 3 이상의 유한 t-변환 그래프는 없다.정도가 정확히 3(큐빅 대칭 그래프)인 경우 t 6 6에 대한 값이 없다.
참고 항목
참조
- ^ a b c d e f Biggs, Norman (1993). Algebraic Graph Theory (2nd ed.). Cambridge: Cambridge University Press. pp. 118–140. ISBN 0-521-45897-8.
- ^ a b c Godsil, Chris; Royle, Gordon (2001). Algebraic Graph Theory. New York: Springer. p. 59. ISBN 0-387-95220-9.
- ^ a b c Babai, L (1996). "Automorphism groups, isomorphism, reconstruction" (PDF). In Graham, R; Grötschel, M; Lovász, L (eds.). Handbook of Combinatorics. Elsevier.
- ^ Bouwer, Z. (1970). "Vertex and Edge Transitive, But Not 1-Transitive Graphs". Canad. Math. Bull. 13: 231–237. doi:10.4153/CMB-1970-047-8.
- ^ Gross, J.L. & Yellen, J. (2004). Handbook of Graph Theory. CRC Press. p. 491. ISBN 1-58488-090-2.
- ^ Holt, Derek F. (1981). "A graph which is edge transitive but not arc transitive". Journal of Graph Theory. 5 (2): 201–204. doi:10.1002/jgt.3190050210..
- ^ Marston Conder, 최대 768 정점, J. Combin에 대한 3차원 대칭 그래프.수학. 콤빈.계산, 20권, 페이지 41-63
- ^ 포스터, R. M. "전기 네트워크의 지리 회로"미국 전기 기술자 협회 51, 309–317, 1932.
- ^ Ronald M의 "The Foster Census: R.M. Foster's Connected Symmetric Trivalent Graphs"포스터, 아이즈부워, W.W. 체르노프, B.몬슨과 Z.별 (1988) ISBN 0-919611-19-2
- ^ 빅스, 페이지 148
- ^ a b Weisstein, Eric W. "Cubic Symmetric Graph" 울프램 수학 월드의 "Cubic Symmetric Graph.
외부 링크
- 입방 대칭 그래프(The Foster Census)최대 768정점까지의 모든 입방 대칭 그래프와 최대 1000정점까지의 일부 입방 그래프에 대한 데이터 파일.2001년 2월에 업데이트된 고든 로일은 2009-04-18을 되찾았다.
- 최대 10000개의 정점에 대한 3가 대칭 그래프.마스턴 콘더, 2011년
