LCF 표기법
LCF notation
결합수학에서 LCF 표기법 또는 LCF 코드는 해밀턴 주기가 포함된 입방 그래프를 나타내기 위해 조슈아 레더버그가 고안하고 H. S. M. 콕시터와 로버트 프루히트가 확장한 표기법이다.[2][3]주기 자체는 각 꼭지점에 대한 세 개의 보조성 중 두 개를 포함하며, LCF 표기법은 각 꼭지점의 세 번째 인접성이 주기에 얼마나 멀리 있는지를 명시한다.단일 그래프에는 LCF 표기법으로 여러 가지 다른 표현이 있을 수 있다.
설명
해밀턴 그래프에서 정점들은 한 사이클로 배열될 수 있으며, 정점당 두 개의 가장자리를 차지한다.그러면 각 정점에서 세 번째 가장자리는 시계방향(양극) 또는 시계 반대방향(음극)으로 얼마나 많은 위치를 유도하는지에 의해 설명할 수 있다.LCF 표기법의 기본 형식은 임의로 선택한 꼭지점에서 시작하여 대괄호로 표기된 이러한 위치 수의 순서일 뿐이다.괄호 사이의 숫자는 모듈로 N으로 해석되며 여기서 N은 정점의 수입니다.항목들은 단순한 그래프에서 허용되지 않는 루프 또는 다중 인접성에 해당하기 때문에 이 숫자의 순서에 일치하는 모듈로 N에서 0, 1 또는 N - 1은 나타나지 않는다.[4]
패턴이 반복되는 경우가 많고, 반복 횟수는 표기법에서 위첨자로 나타낼 수 있다.예를 들어, 오른쪽에 보이는 [1]나우루 그래프는 동일한 6개의 오프셋을 4회 반복하며, LCF 표기법 [5, -9, 7, -7, 9, -5]으로 나타낼 4수 있다.단일 그래프에는 해밀턴 사이클과 시작 꼭지점의 선택에 따라 여러 개의 LCF 표기법이 있을 수 있다.
적용들
LCF 표기법은 아래 예시와 같이 해밀턴 입방 그래프의 간결한 설명을 게시하는 데 유용하다.또한, 그래프를 조작하는 일부 소프트웨어 패키지에는 LCF 표기법에서 그래프를 만드는 유틸리티가 포함되어 있다.[5]
그래프가 LCF 표기법으로 표시되는 경우, 그래프가 초당적인지 여부를 테스트하는 것이 간단하다. 이는 LCF 표기법에서 모든 오프셋이 홀수인 경우에만 해당된다.[6]
예
| 이름 | 정점 | LCF 표기법 |
|---|---|---|
| 사면 그래프 | 4 | [2]4 |
| 효용 그래프 | 6 | [3]6 |
| 입체 그래프 | 8 | [3,−3]4 |
| 바그너 그래프 | 8 | [4]8 또는 [4,-3,3,4]2 |
| 비디아키스 큐브 | 12 | [6,4,-4]4 또는 [6,-3,3,6,3,3]2 또는 [-3,6,4,6,3,4,6,6,4,4,4,3,3,6,4] |
| 프랭클린 그래프 | 12 | [5,-5]6 또는 [-5,-3,3,5]3 |
| Frucht 그래프 | 12 | [−5,−2,−4,2,5,−2,2,5,−2,−5,4,2] |
| 잘린 사면 그래프 | 12 | [2,6,−2]4 |
| 히우드 그래프 | 14 | [5,−5]7 |
| 뫼비우스칸토르 그래프 | 16 | [5,−5]8 |
| 파푸스 그래프 | 18 | [5,7,−7,7,−7,−5]3 |
| 최소 제로대칭 그래프[7] | 18 | [5,−5]9 |
| 데스아게네스 그래프 | 20 | [5,−5,9,−9]5 |
| 도데카헤드 그래프 | 20 | [10,7,4,−4,−7,10,−4,7,−7,4]2 |
| 맥기 그래프 | 24 | [12,7,−7]8 |
| 잘린 칸막이 그래프 | 24 | [2,9,−2,2,−9,−2]4 |
| 잘린 팔면 그래프 | 24 | [3,−7,7,−3]6 |
| 나우루 그래프 | 24 | [5,−9,7,−7,9,−5]4 |
| F26A 그래프 | 26 | [−7, 7]13 |
| 투테-콕시터 그래프 | 30 | [−13,−9,7,−7,9,13]5 |
| Dyck | 32 | [5,−5,13,−13]8 |
| 회색 그래프 | 54 | [−25,7,−7,13,−13,25]9 |
| 잘린 도면체 그래프 | 60 | [30, −2, 2, 21, −2, 2, 12, −2, 2, −12, −2, 2, −21, −2, 2, 30, −2, 2, −12, −2, 2, 21, −2, 2, −21, −2, 2, 12, −2, 2]2 |
| 항렬 그래프 | 70 | [−29,−19,−13,13,21,−27,27,33,−13,13,19,−21,−33,29]5 |
| 해리스-웡 그래프 | 70 | [9, 25, 31, −17, 17, 33, 9, −29, −15, −9, 9, 25, −25, 29, 17, −9, 9, −27, 35, −9, 9, −17, 21, 27, −29, −9, −25, 13, 19, −9, −33, −17, 19, −31, 27, 11, −25, 29, −33, 13, −13, 21, −29, −21, 25, 9, −11, −19, 29, 9, −27, −19, −13, −35, −9, 9, 17, 25, −9, 9, 27, −27, −21, 15, −9, 29, −29, 33, −9, −25] |
| 발라반10길 | 70 | [−9, −25, −19, 29, 13, 35, −13, −29, 19, 25, 9, −29, 29, 17, 33, 21, 9,−13, −31, −9, 25, 17, 9, −31, 27, −9, 17, −19, −29, 27, −17, −9, −29, 33, −25,25, −21, 17, −17, 29, 35, −29, 17, −17, 21, −25, 25, −33, 29, 9, 17, −27, 29, 19, −17, 9, −27, 31, −9, −17, −25, 9, 31, 13, −9, −21, −33, −17, −29, 29] |
| 포스터 그래프 | 90 | [17,−9,37,−37,9,−17]15 |
| 빅스-스미스 그래프 | 102 | [16, 24, −38, 17, 34, 48, −19, 41, −35, 47, −20, 34, −36, 21, 14, 48, −16, −36, −43, 28, −17, 21, 29, −43, 46, −24, 28, −38, −14, −50, −45, 21, 8, 27, −21, 20, −37, 39, −34, −44, −8, 38, −21, 25, 15, −34, 18, −28, −41, 36, 8, −29, −21, −48, −28, −20, −47, 14, −8, −15, −27, 38, 24, −48, −18, 25, 38, 31, −25, 24, −46, −14, 28, 11, 21, 35, −39, 43, 36, −38, 14, 50, 43, 36, −11, −36, −24, 45, 8, 19, −25, 38, 20, −24, −14, −21, −8, 44, −31, −38, −28, 37] |
| 발라반11길 | 112 | [44, 26, −47, −15, 35, −39, 11, −27, 38, −37, 43, 14, 28, 51, −29, −16, 41, −11, −26, 15, 22, −51, −35, 36, 52, −14, −33, −26, −46, 52, 26, 16, 43, 33, −15, 17, −53, 23, −42, −35, −28, 30, −22, 45, −44, 16, −38, −16, 50, −55, 20, 28, −17, −43, 47, 34, −26, −41, 11, −36, −23, −16, 41, 17, −51, 26, −33, 47, 17, −11, −20, −30, 21, 29, 36, −43, −52, 10, 39, −28, −17, −52, 51, 26, 37, −17, 10, −10, −45, −34, 17, −26, 27, −21, 46, 53, −10, 29, −50, 35, 15, −47, −29, −41, 26, 33, 55, −17, 42, −26, −36, 16] |
| 류블랴나 그래프 | 112 | [47, −23, −31, 39, 25, −21, −31, −41, 25, 15, 29, −41, −19, 15, −49, 33, 39, −35, −21, 17, −33, 49, 41, 31, −15, −29, 41, 31, −15, −25, 21, 31, −51, −25, 23, 9, −17, 51, 35, −29, 21, −51, −39, 33, −9, −51, 51, −47, −33, 19, 51, −21, 29, 21, −31, −39]2 |
| 투테 12-케이지 | 126 | [17, 27, −13, −59, −35, 35, −11, 13, −53, 53, −27, 21, 57, 11, −21, −57, 59, −17]7 |
확장 LCF 표기법
더 복잡한 확장 버전의 LCF 표기법은 콕시터, 프루히트, 파워스에 의해 후기 연구에서 제공되었다.[8]특히 대괄호 사이에 있는 숫자의 후반이 상반기의 역(逆)이지만 모든 기호가 바뀌면 세미콜론과 대시로 대체된다는 '반팔자' 표기법을 도입했다.나우루 그래프는 [5, -9, 7, -7, 9, -5]4로 이 조건을 만족하므로 확장 표기법으로 [5, -9, 7; -]4라고 쓸 수 있다.[9]
참조
- ^ a b Eppstein, D. Nauru 그래프의 많은 얼굴들, 2007.
- ^ Pisanski, Tomaž; Servatius, Brigitte (2013), "2.3.2 Cubic graphs and LCF notation", Configurations from a Graphical Viewpoint, Springer, p. 32, ISBN 9780817683641.
- ^ Frucht, R. (1976), "A canonical representation of trivalent Hamiltonian graphs", Journal of Graph Theory, 1 (1): 45–60, doi:10.1002/jgt.3190010111, MR 0463029.
- ^ 섹션 2를 참조하십시오Kutnar, Klavdija; Marušič, Dragan (2008), "Hamiltonicity of vertex-transitive graphs of order 4p", European Journal of Combinatorics, 29 (2): 423–438, arXiv:math/0606585, doi:10.1016/j.ejc.2007.02.002, MR 2388379.
- ^ 예: Maple, NetworkX 웨이백 머신, i그래프 및 세이지에 2012-03-02 보관.
- ^ Coxeter, Harold Scott MacDonald; Frucht, Roberto; Powers, David L. (1981), Zero-symmetric graphs, Academic Press, Inc. [Harcourt Brace Jovanovich, Publishers], New York-London, p. 13, ISBN 0-12-194580-4, MR 0658666.
- ^ Coxeter, Frucht & Powers(1981), 그림 1.1, 페이지 5.
- ^ 콕시터, 프루히트 & 파워스(1981), 페이지 54.
- ^ 콕시터, 프루히트 & 파워스(1981), 페이지 12.
외부 링크
- Weisstein, Eric W. "LCF Notation". MathWorld.
- Ed Pegg Jr. (29 December 2003), Math Games: Cubic Symmetric Graphs, Mathematical Association of America
- "LCF 표기법의 큐빅 해밀턴 그래프" – D3js 라이브러리로 구축된 JavaScript 대화형 응용 프로그램
