대칭 그래프
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.
1. 개요
대칭 그래프는 그래프의 모든 정점이 다른 정점과 동일한 방식으로 "대칭"을 갖는 그래프이다. 대칭 그래프의 예시로는 사이클 그래프, 완전 그래프, 정규 및 준정규 다면체의 정점과 변으로 형성된 그래프(정육면체, 팔면체, 정이십면체 등), 하이퍼큐브 그래프, 교차 다포체 그래프, 완전 이분 그래프, 크라운 그래프, 라도 그래프 등이 있다. 특히, 모든 꼭짓점이 차수 3을 가지는 3차 대칭 그래프는 포스터 센서스를 통해 목록화되었으며, 이 목록에는 정육면체, 페테르센 그래프, 히우드 그래프 등이 포함된다. 대칭 그래프의 정점 연결도는 차수와 같으며, 차수가 3 이상인 t-추이 그래프는 둘레가 최소 2(t-1)이다.
대칭 그래프의 예시는 다음과 같다.
2. 예시
3차 대칭 그래프는 매우 희귀하며, 로널드 M. 포스터가 작성한 포스터 센서스에 목록화되어 있다.
2. 1. 기본 대칭 그래프
임의의 정점 개수에 대한 대칭 그래프의 두 가지 기본적인 부류는 사이클 그래프(차수 2)와 완전 그래프이다.[1] 추가적인 대칭 그래프는 정육면체, 팔면체, 정이십면체, 정십이면체, 깎은 정육면체, 깎은 정이십면체 등 정규 및 준정규 다면체의 정점과 변으로 형성된다.[1] 정육면체를 n 차원으로 확장하면 하이퍼큐브 그래프(2n개의 정점과 차수 n)가 생성된다.[1] 마찬가지로 팔면체를 n 차원으로 확장하면 교차 다포체 그래프가 생성되며, 이 그래프 부류(2n개의 정점과 차수 2n-2)는 때때로 칵테일 파티 그래프라고도 한다.[1] 칵테일 파티 그래프는 완벽한 매칭을 이루는 변 집합이 제거된 완전 그래프이다.[1] 2n개의 정점으로 구성된 짝수 개의 정점을 가진 추가적인 대칭 그래프 부류는 균등하게 분할된 완전 이분 그래프 Kn,n와 2n개의 정점으로 구성된 크라운 그래프이다.[1] 다른 많은 대칭 그래프는 순환 그래프로 분류할 수 있지만 모두 그런 것은 아니다.[1]
2. 2. 다면체 그래프
정육면체, 팔면체, 정이십면체, 정십이면체, 깎은 정육면체, 깎은 정이십면체 등 정규 및 준정규 다면체의 정점과 변으로 형성된 그래프는 대칭 그래프이다. 정육면체를 n 차원으로 확장하면 하이퍼큐브 그래프(2n개의 정점과 차수 n)가 생성된다. 팔면체를 n 차원으로 확장하면 교차 다포체 그래프(칵테일 파티 그래프, 2n개의 정점과 차수 2n-2)가 생성되는데, 이는 완전 그래프에서 완벽한 매칭을 이루는 변 집합을 제거한 그래프이다.
2. 3. 완전 이분 그래프 및 크라운 그래프
2n개의 정점으로 구성된 균등하게 분할된 완전 이분 그래프 Kn,n는 대칭 그래프이다. 2n개의 정점으로 구성된 크라운 그래프는 대칭 그래프이다.
2. 4. 순환 그래프
많은 대칭 그래프는 순환 그래프로 분류할 수 있지만, 모든 대칭 그래프가 순환 그래프인 것은 아니다.
2. 5. 무한 그래프
라도 그래프는 무한히 많은 정점과 무한 차수를 가진 대칭 그래프의 한 예이다.[1]
2. 6. 3차 대칭 그래프 (Cubic Symmetric Graphs)
모든 꼭짓점이 차수 3을 가지는 3차 대칭 그래프는 짝수 개의 꼭짓점을 가지며, 매우 희귀하여 목록으로 정리할 수 있다. '''포스터 센서스'''는 로널드 M. 포스터가 1930년대부터 벨 연구소에서 시작한 3차 대칭 그래프 목록이다.[7][8] 1988년(포스터가 92세였을 때[1]) 최대 512개의 꼭짓점을 가진 그래프 목록이 책으로 출판되었다.[9]
다음은 포스터 센서스에 포함된 최대 30개의 꼭짓점을 가진 3차 대칭 그래프의 일부이다.[10][11]
| 꼭짓점 | 지름 | 둘레 | 그래프 | 참고 |
|---|---|---|---|---|
| 4 | 1 | 3 | 완전 그래프 K4 | 거리 전이적, 2-호 전이적 |
| 6 | 2 | 4 | 완전 이분 그래프 K3,3 | 거리 전이적, 3-호 전이적 |
| 8 | 3 | 4 | 정육면체의 꼭짓점과 모서리 | 거리 전이적, 2-호 전이적 |
| 10 | 2 | 5 | 페테르센 그래프 | 거리 전이적, 3-호 전이적 |
| 14 | 3 | 6 | Heawood 그래프 | 거리 전이적, 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-호 전이적 |
| 28 | 4 | 7 | 콕세터 그래프 | 거리 전이적, 3-호 전이적 |
| 30 | 4 | 8 | 터트-콕세터 그래프 | 거리 전이적, 5-호 전이적 |
대칭 그래프의 정점 연결도는 항상 차수와 같다.[3] 일반적인 정점 추이 그래프의 경우 정점 연결도는 2(''d''+1)/3보다 크거나 같다.[2]
[1]
서적
Algebraic Graph Theory
Cambridge University Press
다른 잘 알려진 3차 대칭 그래프로는 다이크 그래프, 포스터 그래프, 빅스-스미스 그래프가 있다. 위에 나열된 10개의 거리 전이 그래프와 포스터 그래프, 빅스-스미스 그래프는 유일한 3차 거리 전이 그래프이다.
3. 성질
차수가 3 이상인 ''t''-추이 그래프는 둘레가 최소 2(''t''-1)이다. 그러나 차수가 3 이상인 유한 ''t''-추이 그래프는 ''t'' ≥ 8인 경우 존재하지 않는다. 차수가 정확히 3인 경우(입방 대칭 그래프)에는 ''t'' ≥ 6인 그래프가 존재하지 않는다.
참조
[2]
서적
Algebraic Graph Theory
https://archive.org/[...]
Springer
[3]
서적
Handbook of Combinatorics
Elsevier
[4]
논문
Vertex and Edge Transitive, But Not 1-Transitive Graphs
1970
[5]
서적
Handbook of Graph Theory
CRC Press
[6]
논문
A graph which is edge transitive but not arc transitive
[7]
간행물
Trivalent symmetric graphs on up to 768 vertices
http://www.math.auck[...]
[8]
논문
Geometrical Circuits of Electrical Networks
1932
[9]
서적
The Foster Census: R.M. Foster's Census of Connected Symmetric Trivalent Graphs
[10]
문서
[11]
웹사이트
Cubic Symmetric Graph
http://mathworld.wol[...]
[12]
서적
Algebraic Graph Theory
Cambridge University Press
[13]
서적
Algebraic Graph Theory
Springer
[14]
서적
Handbook of Combinatorics
Elsevier
[15]
논문
Vertex and Edge Transitive, But Not 1-Transitive Graphs
1970
[16]
서적
Handbook of Graph Theory
CRC Press
[17]
논문
A graph which is edge transitive but not arc transitive
[18]
간행물
Trivalent symmetric graphs on up to 768 vertices
http://www.math.auck[...]
[19]
논문
Geometrical Circuits of Electrical Networks
1932
[20]
서적
The Foster Census: R.M. Foster's Census of Connected Symmetric Trivalent Graphs
[21]
문서
[22]
웹사이트
Cubic Symmetric Graph
http://mathworld.wol[...]
본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.
문의하기 : help@durumis.com