해밍 그래프
Hamming graph| 해밍 그래프 | |
|---|---|
| 이름을 따서 명명됨 | 리처드 해밍 |
| 정점 | |
| 가장자리 | |
| 지름 | |
| 스펙트럼 | |
| 특성. | (- ) - 정규 분포 정점 변환 거리-정규어[1] |
| 표기법 | |
| 그래프 및 모수 표 | |
단위 거리 그래프로 그려진 H(3,3)
해밍 그래프는 리처드 해밍의 이름을 딴 그래프의 특별한 등급으로, 수학 및 컴퓨터 과학의 여러 분야에서 사용된다.S는 q 원소의 집합이고 d는 양의 정수로 하자.Hamming 그래프 H(d,q)는d S, S 요소의 순서가 정렬된 d-tuples 집합 또는 S의 길이 d 시퀀스를 가지고 있다.정점 두 개가 정확히 하나의 좌표에서 서로 다르면 인접한다. 즉, 해밍 거리가 하나일 경우.해밍 그래프 H(d,q)는 동등하게 완전한 그래프 K의q 데카르트 산물이다.[1]
어떤 경우에 해밍 그래프는 크기가 다양할 수 있는 완전한 그래프의 데카르트 산물로 더 일반적으로 간주될 수 있다.[2]해밍 그래프 H(d,q)와 달리, 이 보다 일반적인 클래스의 그래프는 반드시 거리 정규일 필요는 없지만, 규칙적이고 정점 변환을 계속한다.
특례
- H(2,3)는 일반화된 쿼드랑글 G Q(2,1)이다.[3]
- H(1,q), 즉 전체 그래프q[4] K
- H(2,q)는 격자 그래프q,q L이고 또한 룩의 그래프임[5]
- H(d,1)는 싱글톤 그래프 K이다1.
- H(d,2)는 하이퍼큐브 그래프 Q이다d.[1]이 그래프의 해밀턴 경로는 회색 코드를 형성한다.
- 그래프의 데카르트 산물은 단위 거리 그래프라는 특성을 보존하기 때문에 해밍 그래프 H(d,2)와 H(d,3)는 모두 단위 거리 그래프다.[6]
적용들
해밍 그래프는 오류 수정 코드[7] 및 연결 체계와 관련하여 두 가지 영역을 명명하는 데 흥미롭다.[8]그것들은 또한 분산 컴퓨팅에서 통신 네트워크 토폴로지로 고려되어 왔다.[4]
계산 복잡성
그래프가 해밍 그래프인지 여부를 선형적으로 테스트할 수 있으며, 해밍 그래프인 경우 해밍 그래프로 인식되는 튜플로 라벨을 찾아낸다.[2]
참조
- ^ a b c Brouwer, Andries E.; Haemers, Willem H. (2012), Spectra of graphs, Universitext, New York: Springer, p. 178, doi:10.1007/978-1-4614-1939-6, ISBN 978-1-4614-1938-9, MR 2882891.
- ^ a b Imrich, Wilfried; Klavžar, Sandi (2000), "Hamming graphs", Product graphs, Wiley-Interscience Series in Discrete Mathematics and Optimization, Wiley-Interscience, New York, pp. 104–106, ISBN 978-0-471-37039-0, MR 1788124.
- ^ Blokhuis, Aart; Brouwer, Andries E.; Haemers, Willem H. (2007), "On 3-chromatic distance-regular graphs", Designs, Codes and Cryptography, 44 (1–3): 293–305, doi:10.1007/s10623-007-9100-7, MR 2336413. 300페이지의 특정 노트(e)를 참조하라.
- ^ a b Dekker, Anthony H.; Colbert, Bernard D. (2004), "Network robustness and graph topology", Proceedings of the 27th Australasian conference on Computer science - Volume 26, ACSC '04, Darlinghurst, Australia, Australia: Australian Computer Society, Inc., pp. 359–368.
- ^ Bailey, Robert F.; Cameron, Peter J. (2011), "Base size, metric dimension and other invariants of groups and graphs", Bulletin of the London Mathematical Society, 43 (2): 209–242, doi:10.1112/blms/bdq096, MR 2781204.
- ^ Horvat, Boris; Pisanski, Tomaž (2010), "Products of unit distance graphs", Discrete Mathematics, 310 (12): 1783–1792, doi:10.1016/j.disc.2009.11.035, MR 2610282
- ^ Sloane, N. J. A. (1989), "Unsolved problems in graph theory arising from the study of codes" (PDF), Graph Theory Notes of New York, 18: 11–20.
- ^ Koolen, 야코부스 H.;이 대통령은 우 태양;마틴, W(2010년),"대수학 관점에서 완전히 규칙적인 코드 Characterizing", Combinatorics와 그래프, Contemp.수학., 531개 vol., 프로비던스, R1:아메르.,를 대신하여 서명함. 223–242, arXiv:0911.1828, doi:10.1090/conm/531/10470, 아이 에스비엔 9780821848654, MR2757802, S2CID 8197351.우편 224일, 저자들은 그"완전히 규칙적인 코드의 그래프 해밍에 주의 깊은 연구 협회 체계를 연구하는 핵심 부분이다"를 쓴다.
