뫼비우스-칸토르 그래프
Möbius–Kantor graph| 뫼비우스-칸토르 그래프 | |
|---|---|
 | |
| 의 이름을 따서 명명됨 | 아우구스트 페르디난트 뫼비우스와 S. 칸토르 |
| 꼭지점 | 16 |
| 가장자리 | 24 |
| 반지름 | 4 |
| 직경 | 4 |
| 둘레 | 6 |
| 자기동형 | 96 |
| 색수 | 2 |
| 색채 지수 | 3 |
| 속 | 1 |
| 책 두께 | 3 |
| 큐 번호 | 2 |
| 특성. | 대칭 해밀턴식 초당파 큐빅 단위 거리 케일리 그래프 완벽하다 심플한 방향성 |
| 그래프 및 매개 변수 표 | |
그래프 이론의 수학 분야에서, 뫼비우스-칸토르 그래프는 아우구스트 페르디난드 뫼비우스와 셀리그만 칸토르의 이름을 딴 16개의 꼭지점과 24개의 모서리를 가진 대칭적인 초당 입방 그래프이다.이것은 일반화된 피터슨 그래프 G(8,3)로 정의될 수 있다. 즉, 이것은 8각형의 정점에 의해 형성되며, 8각형의 정점에 의해 별의 각 점이 그것으로부터 3단계 떨어진 지점과 연결되어 있다.
뫼비우스-칸토르 설정
뫼비우스(1828)는 한 폴리곤의 꼭짓점이 다른 폴리곤의 가장자리를 통과하는 선 위에 있다는 특성을 가진 p개의 변이 각각 있는 폴리곤의 쌍이 존재하는지, 그리고 그 반대도 마찬가지이다.이 경우 이러한 폴리곤의 정점과 가장자리가 투영 구성을 형성합니다.p = 4의 경우, 유클리드 평면에 해답은 없지만, 칸토르(1983)는 점과 가장자리가 복잡한 투영 평면에 속하는 문제의 일반화를 위해 이 유형의 폴리곤 쌍을 발견했다.즉, 칸토르의 해법에서, 다각형 꼭지점의 좌표는 복소수이다.복잡한 투영 평면에서 상호 결합되는 4변수 쌍인 p = 4에 대한 칸토르의 해는 뫼비우스-칸토르 배치라고 불린다.Möbius-Kantor 그래프는 Möbius-Kantor 구성의 Levi 그래프에서 이름을 따왔다.점당 하나의 정점과 트리플당 하나의 정점을 가지며, 점이 포함된 세 개의 정점에 해당하는 경우 두 개의 정점을 연결하는 모서리가 있습니다.
구성은 9개의 요소를 가진 아벨 3 × times \의 관점에서 대수적으로 설명할 수도 있습니다.이 그룹에는 순서 3의 서브셋(양식( {(( { (( {i,)}, (0,i의 4개의 서브셋이 있으며 각각 9개의 코셋으로 분할할 수 있습니다.f 코세트당 3개의 요소이들 9개의 요소와 12개의 코셋이 하나의 구성인 헤세 구성을 형성합니다.0 요소 및 0을 포함한 4개의 코셋을 삭제하면 뫼비우스-칸토르 설정이 발생합니다.
4개의 서브셋이 있으며 각각 9개의 서브그래프로
뫼비우스-칸토르 그래프는 하이퍼큐브에서 8개의 에지를 제거하여 형성된 4차원 하이퍼큐브 그래프의 하위 그래프이다(Coxeter 1950).하이퍼큐브는 단위 거리 그래프이므로 뫼비우스-칸토르 그래프는 모든 모서리 단위 길이를 가진 평면에 그릴 수 있지만 이러한 도면에는 반드시 교차하는 모서리 쌍이 있어야 합니다.
뫼비우스-칸토르 그래프는 호프만-싱글턴 그래프의 유도 하위 그래프와 마찬가지로 여러 번 발생한다.이들 각 인스턴스는 사실상 Hoffman-Singleton 그래프의 고유 벡터이며, 관련 고유값은 -3이다.유도된 뫼비우스-칸토르 그래프에 포함되지 않은 각 정점은 뫼비우스-칸토르 그래프에서 정확히 4개의 정점에 인접하며, 뫼비우스-칸토르 그래프의 양분 중 각각 2개씩이다.
토폴로지
뫼비우스-칸토르 그래프는 평면에 교차 없이 삽입할 수 없다. 교차 번호 4를 가지며 교차 번호가 있는 가장 작은 입방체 그래프이다(OEIS의 시퀀스 A110507).또한 모든 서브그래프의 교차번호가 2개 [1]이상 다른 그래프의 예를 제공합니다.그러나 이것은 트로이덜 그래프이다: 이것은 모든 면이 육각형인 토러스 안에 내장되어 있다(Marushich & Pisanski 2000).이 매립의 이중 그래프는 초팔면체 그래프2,2,2,2 K이다.
6개의 팔각형 면을 가진 이중 토러스에는 뫼비우스-칸토르 그래프의 훨씬 더 대칭적인 매립이 있다. 여기서 그래프의 96개 대칭을 모두 매립의 대칭으로 실현할 수 있다. 콕서터(1950)는 이 매립을 Threlfall(1932년)의 탓으로 돌린다.96개 요소 대칭군은 이중 토러스 위에 삽입할 수 있는 케일리 그래프를 가지고 있으며, Tucker(1984)에 의해 2속인 유일한 그룹이라는 것을 보여주었다.96개의 정점에 대한 케일리 그래프는 뫼비우스-칸토르 그래프를 골격으로 하는 2속 정규 지도의 플래그 그래프이다.이것은 중심 분할의 이중 골격으로서 정규 지도에서 얻을 수 있다는 것을 의미합니다.2007년 제6회 슬로베니아 국제 그래프 이론 회의의 일환으로 슬로베니아 기술 박물관에서 뫼비우스-칸토르 그래프의 대칭을 이중 토러스 매립한 드윗 고드프리와 두안 마르티네즈의 조각상이 공개되었다.2013년 이 조각상의 회전 버전이 콜게이트 대학에서 공개되었다.
뫼비우스-칸토르 그래프는 위에서 설명한 이중 토러스 매립의 페트리 쌍대이며, 4개의 12각형 면을 가진 정규 지도인 삼중 토러스(일반 3 토러스)에 매립할 수 있다.
Lijnen & Ceulemans(2004)는 탄소 화합물의 잠재적 화학 구조 조사에 동기 부여되어 2-매니폴드에 대한 뫼비우스-칸토르 그래프의 모든 임베딩 패밀리를 연구했다. 이들은 759가의 불평등 임베딩이 있음을 보여주었다.
대수적 성질
뫼비우스-칸토르 그래프의 자기동형군은 [2]96차수 그룹이다.그래프의 정점, 모서리 및 호에서 횡방향으로 작용합니다.따라서 뫼비우스-칸토르 그래프는 대칭 그래프입니다.어떤 정점을 다른 정점으로, 어떤 모서리를 다른 모서리로 이동시키는 자기동형성을 가지고 있습니다.포스터 인구 조사에 따르면, 뫼비우스-칸토르 그래프는 16개의 꼭지점을 가진 독특한 입방체 대칭 그래프이며 거리 추이가 [3]없는 가장 작은 입방체 대칭 그래프이다.뫼비우스-칸토르 그래프도 케일리 그래프다.
일반화 페테르센 그래프 G(n,k)는 n = 10 및 k = 2 또는 k ≤ ±1(mod n)인2 경우에만 정점-추이적이며, (n,k) = (4,1,2,8,3), (10,3,125) 또는 (125)의 경우에만 에지-추이적이다.따라서 뫼비우스-칸토르 그래프는 7개의 대칭 일반화 페테르센 그래프 중 하나이다.대칭 이중 토러스 매립은 정점의 총 수가 면당 정점 수의 두 배인 7개의 정육면체 맵 중 하나이다(McMullen 1992).7개의 대칭 일반화된 Petersen 그래프에는 G){( G5 {G( Displaystyle 이 있습니다G(
뫼비우스-칸토르 그래프의 특성 다항식은 다음과 같다.
「 」를 참조해 주세요.
메모들
- ^ 를 클릭합니다McQuillan, Dan; Richter, R. Bruce (1992), "On the crossing numbers of certain generalized Petersen graphs", Discrete Mathematics, 104 (3): 311–320, doi:10.1016/0012-365X(92)90453-M, MR 1171327.
- ^ Royle, G. F016A 데이터[permanent dead link]
- ^ Conder, M. 및 Dobcsanyi, P. "3가 대칭 그래프 최대 768 정점." J. Combin.수학. 조합.컴퓨터40, 41-63, 2002.
레퍼런스
- 를 클릭합니다Coxeter, H. S. M. (1950), "Self-dual configurations and regular graphs", Bulletin of the American Mathematical Society, 56 (5): 413–455, doi:10.1090/S0002-9904-1950-09407-5.
- 를 클릭합니다Frucht, Robert; Graver, Jack E.; Watkins, Mark E. (1971), "The groups of the generalized Petersen graphs", Proceedings of the Cambridge Philosophical Society, 70 (02): 211–218, doi:10.1017/S0305004100049811, MR 0289365.
- 를 클릭합니다Kantor, Seligmann (1882), "Über die Configurationen (3, 3) mit den Indices 8, 9 und ihren Zusammenhang mit den Curven dritter Ordnung", Sitzungsberichte der Mathematisch-Naturwissenschaftlichen Classe der Kaiserlichen Akademie der Wissenschaften, Wien, 84 (1): 915–932.
- 를 클릭합니다Lijnen, Erwin; Ceulemans, Arnout (2004), "Oriented 2-Cell Embeddings of a Graph and Their Symmetry Classification: Generating Algorithms and Case Study of the Möbius-Kantor Graph", Journal of Chemical Information and Modeling, 44 (5): 1552–1564, doi:10.1021/ci049865c, PMID 15446812.
- 를 클릭합니다Marušič, Dragan; Pisanski, Tomaž (2000), "The remarkable generalized Petersen graph G(8,3)", Mathematica Slovaca, 50: 117–121.
- 를 클릭합니다McMullen, Peter (1992), "The regular polyhedra of type {p, 3} with 2p vertices", Geometriae Dedicata, 43 (3): 285–289, doi:10.1007/BF00151518.
- Möbius, August Ferdinand (1828), "Kann von zwei dreiseitigen Pyramiden eine jede in Bezug auf die andere um- und eingeschrieben zugleich heissen?" (PDF), Journal für die reine und angewandte Mathematik, 3: 273–278. Gesamelte Werke (1886년) 제1권, 439–446페이지.
- 를 클릭합니다Tucker, Thomas W. (1984), "There is only one group of genus two", Journal of Combinatorial Theory, Series B, 36 (3): 269–275, doi:10.1016/0095-8956(84)90032-7.
- 를 클릭합니다Threlfall, William (1932), "Gruppenbilder", Abhandlungen der Mathematisch-Physischen Klasse der Sächsischen Akademie der Wissenschaften, 41 (6): 1–59.
- 제시카 울즈, SAT의 엔지니어링 선형 배치입니다.2018년 튀빙겐 대학교 석사 논문
