반감 큐브 그래프

반감 큐브 그래프
반감 큐브 그래프
	반감된 입방체 그래프
정점	2n-1
가장자리	n(n-1)2n-3
자동형성	n! 2n-1 , for n>4; n! 2를n n=4에 대해; (2n-1)!, n<4용
특성.	대칭; 거리 정규
표기법
	그래프 및 모수 표

단일 큐브에서 두 개의 데미큐브(일반적인 테트라헤드라, 스텔라 옥탄굴라 형성)의 시공.치수 3의 반감된 입방체 그래프는 단일 데미큐브의 정점과 가장자리를 나타내는 그래프다.치수 4의 반감된 입방체 그래프는 큐브 정점과 가장자리, 그리고 두 개의 데미큐브의 모든 가장자리를 포함한다.

그래프 이론에서 치수 n의 반감된 입방체 그래프 또는 절반 입방체 그래프는 하이퍼큐브 그래프에서 서로 정확히 2개의 거리에 있는 정점 쌍을 연결하여 형성된 데미하이퍼큐브 그래프다.즉, 하이퍼큐브의 반제곱이다.이 연결 패턴은 서로 단절된 두 개의 이형 그래프를 생성하는데, 각 그래프는 반감된 입방체 그래프다.

등가 구조

반감된 입방체 그래프의 구성은 이진수로 재조정될 수 있다.하이퍼큐브의 정점은 두 정점이 한 비트 안에서 다를 때 정확히 인접하는 방식으로 이진수로 라벨을 붙일 수 있다.데미큐브는 0비트(악의 숫자)가 짝수인 2진수 부분 집합의 볼록한 선체로 하이퍼큐브에서 구성될 수 있으며, 가장자리는 해밍 거리가 정확히 두 개인 숫자 쌍을 연결한다.^[2]

또한 정점의 부분 집합을 취하지 않고 저차원 하이퍼큐브 그래프에서 반감된 큐브 그래프를 구성할 수도 있다.

{\frac {1}{2}}Q_{n}=Q_{n-1}^{2}

여기서 위첨자 2는 하이퍼큐브 그래프 Q의_{n − 1} 제곱을 나타내며, 원래 그래프에서 거리가 최대 2인 정점 쌍을 연결하여 형성된 그래프.예를 들어, 치수 4의 반감된 입방체 그래프는 입방체 가장자리를 유지하고 동일한 사각형의 반대쪽 모서리에 있는 정점 쌍을 연결하는 가장자리를 추가함으로써 일반적인 3차원 입방체로부터 형성될 수 있다.

예

치수 3의 ${\tfrac {1}{2}}Q_{3}$ 반감된 입방체 그래프 ${\tfrac {1}{2}}Q_{3}$ 2 ${\tfrac {1}{2}}Q_{3}$ ${\tfrac {1}{2}}Q_{3}$ ${\$ 는 4면체 그래프인 전체 그래프 K이다₄.치수 4의 ${\tfrac {1}{2}}Q_{4}$ 반감된 입방체 그래프 ${\tfrac {1}{2}}Q_{4}$ ${\tfrac {1}{2}}Q_{4}$ ${\tfrac {1}{2}}Q_{4}$ ${\tfrac {1}{2}}Q_{4}$ ${\$ 는 4차원 일반 폴리토페의 그래프인 K이다_2,2,2,2.치수 5의 ${\tfrac {1}{2}}Q_{5}$ 반감된 입방체 그래프 ${\tfrac {1}{2}}Q_{5}$ 2 ${\tfrac {1}{2}}Q_{5}$ 5 ${\$ 는 때때로 Clebsch 그래프로 알려져 있으며, 일반적으로 Clebsch 그래프라고 불리는 치수 5의 접힌 입방체 그래프를 보완한 것이다.5차원 제복 5폴리코프, 5데미큐브에 존재한다.

특성.

거리 정규 그래프의 절반인 초당적인 크기 때문에 반감된 입방체 그래프는 그 자체가 거리 정규 그래프다.^[3]그리고 그것은 하이퍼큐브를 스패닝 서브그래프로 포함하고 있기 때문에, 그것은 하이퍼큐브로부터 해밀턴 사이클을 포함하는 특성 같은 모든 단조로운 그래프 속성을 상속한다.

하이퍼큐브 그래프와 그 등축(거리 보존) 하위 그래프가 부분 큐브를 나타내듯이, 절반으로 줄어든 입방체 그래프는 맨해튼 미터법(L₁ 거리 함수)으로 실제 벡터 공간에 등축적으로 내장될 수 있다.다항식 시간에 인식될 수 있는 반감된 입방체 그래프의 등축 하위 그래프도 마찬가지다. 이것은 주어진 그래프가 맨해튼 메트릭에 등축적으로 포함되는지 여부를 테스트하는 알고리즘의 핵심 서브루틴을 형성한다.^[4]

치수 5 이상의 반감된 각 입방체 그래프에 대해 결과 색상 그래프에 비교 대칭이 없는 방식으로 정점을 두 가지 색상으로 색칠하는 것이 가능하다.차원 3과 4의 그래프의 경우 모든 대칭을 제거하기 위해 네 가지 색상이 필요하다.^[5]

순서

표시된 두 개의 그래프는 겹치는 모서리와 정점을 포함할 수 있는 관련 폴리토프의 대칭 D_n 및 B Petrie_n 폴리곤 투영(2(n - 1) 및 n 다이헤드 대칭)이다.

n	폴리토프	정점	가장자리
2	라인 세그먼트	2	–
3	사면체	4	6
4	16 셀	8	24
5	5데미큐브	16	80
6	6데미큐브	32	240
7	7데미큐브	64	672
8	8데미큐브	128	1792
9	9데미큐브	256	4608
10	10데미큐브	512	11520

참조

^ A.E. 브루어, A.M. 코헨, A.E.Neumaier(1989), 거리 정규 그래프.뉴욕주 베를린: 스프링거-베를라크, 265페이지. ISBN 3-540-50619-5, ISBN 0-387-50619-5
^ Indyk, Piotr; Matoušek, Jiří (2010), "Low-distortion embeddings of finite metric spaces", in Goodman, Jacob E.; O'Rourke, Joseph (eds.), Handbook of Discrete and Computational Geometry (2nd ed.), CRC Press, p. 179, ISBN 9781420035315.
^ Chihara, Laura; Stanton, Dennis (1986), "Association schemes and quadratic transformations for orthogonal polynomials", Graphs and Combinatorics, 2 (2): 101–112, doi:10.1007/BF01788084, MR 0932118.
^ Deza, M.; Shpectorov, S. (1996), "Recognition of the l₁-graphs with complexity O(nm), or football in a hypercube", European Journal of Combinatorics, 17 (2–3): 279–289, doi:10.1006/eujc.1996.0024, MR 1379378.
^ Bogstad, Bill; Cowen, Lenore J. (2004), "The distinguishing number of the hypercube", Discrete Mathematics, 283 (1–3): 29–35, doi:10.1016/j.disc.2003.11.018, MR 2061481.

외부 링크

Weisstein, Eric W. "Halved Cube Graph". MathWorld.

[Brouwer-1] A.E. 브루어, A.M. 코헨, A.E.Neumaier(1989), 거리 정규 그래프.뉴욕주 베를린: 스프링거-베를라크, 265페이지. ISBN 3-540-50619-5, ISBN 0-387-50619-5

[2] Indyk, Piotr; Matoušek, Jiří (2010), "Low-distortion embeddings of finite metric spaces", in Goodman, Jacob E.; O'Rourke, Joseph (eds.), Handbook of Discrete and Computational Geometry (2nd ed.), CRC Press, p. 179, ISBN 9781420035315.

[3] Chihara, Laura; Stanton, Dennis (1986), "Association schemes and quadratic transformations for orthogonal polynomials", Graphs and Combinatorics, 2 (2): 101–112, doi:10.1007/BF01788084, MR 0932118.

[4] Deza, M.; Shpectorov, S. (1996), "Recognition of the l₁-graphs with complexity O(nm), or football in a hypercube", European Journal of Combinatorics, 17 (2–3): 279–289, doi:10.1006/eujc.1996.0024, MR 1379378.

[5] Bogstad, Bill; Cowen, Lenore J. (2004), "The distinguishing number of the hypercube", Discrete Mathematics, 283 (1–3): 29–35, doi:10.1016/j.disc.2003.11.018, MR 2061481.

[2]

[3]

[4]

[5]

Search

반감 큐브 그래프

네임스페이스

더

목차

등가 구조

예

특성.

순서

참조

외부 링크

반감 큐브 그래프
반감된 입방체 그래프 ${\tfrac {1}{2}}Q_{3}$ ${\tfrac {1}{2}}Q_{3}$ ${\tfrac {1}{2}}Q_{3}$ ${\tfrac {1}{2}}Q_{3}$ ${\$
정점	2^n-1
가장자리	n(n-1)2^n-3
자동형성	n! 2^n-1, for n>4 n! 2를ⁿ n=4에 대해 (2^n-1)!, n<4용
특성.	대칭 거리 정규
표기법	${\tfrac {1}{2}}Q_{n}}$
그래프 및 모수 표