하이퍼큐브 그래프

하이퍼큐브 그래프
하이퍼큐브 그래프
	하이퍼큐브 그래프4 Q
정점	2n
가장자리	2n−1n
지름	n
둘레	4 만약 n이면 2
자동형성	n! 2n
색수	2
스펙트럼
특성.	대칭; 거리 정규; 단위 거리; 해밀턴어; 양립자
표기법	Qn
	그래프 및 모수 표

그래프 이론에서 하이퍼큐브 그래프 $Q$ 는_n n차원 하이퍼큐브의 정점과 가장자리에서 형성된 그래프다.예를 들어 입체 그래프 $Q$ 는₃ 3차원 큐브의 8개의 꼭지점과 12개의 가장자리에 의해 형성된 그래프다. $Q$ 는_n 2개의ⁿ 꼭지점과 $2n개$ 의ⁿ⁻¹ 가장자리를 가지며, $가장자리$ 가 각 꼭지점에 닿는 정규 그래프다.null

하이퍼큐브 그래프 $Q$ 는_n 또한 n-요소 집합의 각 부분 집합에 대해 정점을 생성하거나, 하위 집합이 한 숫자로 다를 때 정점을 두거나, 각 n자리 이진수에 대해 정점을 생성하며, 이진표현이 한 자릿수로 다를 때 정점을 두 개 생성하여 구성할 수도 있다.2-Vertex 전체 그래프의 n-폴드 카르테시안 제품이며, 완벽한 매칭으로 서로 $연결$ 된_{n − 1} Q의 두 복사본으로 분해될 수 있다.null

하이퍼큐브 그래프는 각 꼭지점에 정확히 세 개의 가장자리가 닿는 그래프인 입방형 그래프와 혼동해서는 안 된다.입방형 그래프인 하이퍼큐브 그래프 $Q$ 는_n 큐빅 그래프 $Q뿐$ 입니다₃.

건설

Q 2

사본 2부에 해당 정점 쌍을 연결하여

Q

의₃ 구성

하이퍼큐브 그래프 $Q$ 는_n 가능한 각 부분집합에 정점을 만들고 해당 부분집합이 단일 요소에서 다를 때마다 가장자리로 두 정점을 결합하여 $n개$ 의 요소가 있는 집합의 부분집합 집합에서 구성할 수 있다.마찬가지로, 이 값은 n비트 이진수로 표시된 정점 $2개$ 를ⁿ 사용하여 구성될 수 있으며, 라벨의 해밍 거리가 1이 될 때마다 가장자리를 기준으로 두 정점을 연결할 수 있다.이 두 구조는 밀접한 관련이 있다: 이진수는 집합으로 해석될 수 있으며( $1자리$ 의 위치가 있는 위치 집합), 해당하는 두 이진수가 해밍 거리 1을 가질 때마다 그러한 두 세트는 단일 원소에서 다르다.null

또는 그림에서와 같이 $Q$ 의_{n − 1} 한 사본에 있는 각 정점으로부터 다른 사본의 해당 정점에 엣지를 추가하여 두 개의 하이퍼큐브 $Q$ 의_{n − 1} 분리 결합으로 $Q$ 를_n 구성할 수 있다.접합 모서리가 완벽하게 일치한다.null

$Q$ 의_n 또 다른 구조는 $n개$ 의 2-Vertex 완전 $그래프 2$ K로 이루어진 데카르트 제품이다.더 일반적으로 전체 그래프의 카세트산물을 해밍 그래프라고 부른다; 하이퍼큐브 그래프는 해밍 그래프의 예들이다.null

예

그래프 $Q$ 는₀ 하나의 꼭지점으로 구성되는 $반면 1$ , Q는 두 정점에 대한 완전한 그래프, $Q$ 는₂ 길이 $4$ 의 사이클이다.

그래프 $Q$ 는₃ 정점 8개와 가장자리 12개를 가진 입방체의 1-제곱 그래프다.null

그래프 $Q$ 는₄ 뫼비우스 구성을 나타내는 Levi 그래프다.그것은 또한 4 $4\times 4$ $4\times 4$ ${\displaystyle$ 4 $\time 4}$ 체스판 $4\times 4$ 기사의 그래프이기도 하다.^[1]null

특성.

초당성

모든 하이퍼큐브 그래프는 초당적이다: 그것은 오직 두 가지 색으로만 색칠될 수 있다.이 색상의 두 가지 색상은 고른 수의 원소가 있는 부분 집합에 한 가지 색상을, 홀수의 원소가 있는 부분 집합에 다른 색상을 부여함으로써 하이퍼큐브 그래프의 부분 집합 구성에서 찾을 수 있다.null

해밀턴시티

4비트 주기 회색으로 표시된 정점을 가진 큐빅의 해밀턴 사이클

$n$ > $1$ 을 가진 모든 $하이퍼큐브 n$ Q에는 해밀턴 사이클이 있는데, 이 사이클은 각 꼭지점을 정확히 한 번 방문하는 사이클이다.또한 해밀턴 경로는 그래프의 2-색상에서 서로 다른 색을 갖는 경우에만 두 꼭지점 $u$ 와 v $사이$ 에 존재한다.두 가지 사실 모두 하이퍼큐브 치수에서의 유도 원리와 매칭과 함께 두 개의 작은 하이퍼큐브 그래프를 결합하여 하이퍼큐브 그래프를 구성하여 증명하기 쉽다.null

하이퍼큐브의 해밀턴성은 그레이 코드의 이론과 밀접한 관련이 있다.보다 정확하게는 하이퍼큐브 $Q$ 에서_n n비트 순환 그레이 코드 집합과 해밀턴 주기 집합 사이에 편향적 대응성이 있다.^[2]유사한 속성은 반복 n비트 그레이 코드와 해밀턴 경로에 대한 것이다.null

덜 알려진 사실은 하이퍼큐브의 모든 완벽한 매칭이 해밀턴 사이클로 확장된다는 것이다.^[3]매칭이 해밀턴 사이클로 확장되는가에 대한 의문은 여전히 열려 있는 문제로 남아 있다.^[4]null

기타 속성

하이퍼큐브 $그래프 n$ Q ( $n$ > $1$ ) :

유한 부울 대수의 하세 다이어그램이다.
중위수 그래프 입니다.모든 중위수 그래프는 하이퍼큐브의 등축 하위그래프로, 하이퍼큐브의 수축으로 형성될 수 있다.
2개 이상의 완벽한 $짝$ 을^{2^n-2} 가지고 있다.(귀납적 구성에서 쉽게 따라오는 또 다른 결과)
호는 전이적이고 대칭이다.하이퍼큐브 그래프의 대칭은 서명한 순열로 나타낼 수 있다.
$길이$ 4, $6$ , $..., 2$ 의ⁿ 모든 사이클을 포함하며, 따라서 두 번 반복 그래프인 것이다.
$n$ 원소 집합의 하위 집합에서 하이퍼큐브 그래프를 구성하고, 각 세트 원소에 대해 구별되는 단위 벡터를 선택하고, $S$ 의 벡터 합계에 세트 $S$ 에 해당하는 정점을 배치하여 유클리드 평면에서 단위 거리 그래프로 그릴 수 있다.
발린스키의 정리에 의해 n-Vertex로 연결된 그래프다.
평면형(교차 없이 그릴 수 있음)인 경우 및 n if $3$ 인 경우에만. $n$ 의 큰 값의 경우, 하이퍼큐브에는 $(n -$ 4) $2 n - 3$ + $1$ 이 있다.^[5]^[6]
정확히 $2^{2^{n}-n-1}\prod _{k=2}^{n}k^{n \choose k}$ - 1 $2^{2^{n}-n-1}\prod _{k=2}^{n}k^{n \choose k}$ $2^{2^{n}-n-1}\prod _{k=2}^{n}k^{n \choose k}$ = $2^{2^{n}-n-1}\prod _{k=2}^{n}k^{n \choose k}$ k ( $2^{2^{n}-n-1}\prod _{k=2}^{n}k^{n \choose k}$ $){\$ }\ $prod _{k=2}^{n$ ^{n $}k^{n$ \n \ $n}}}}}}}}}$ 스패닝 $2^{2^{n}-n-1}\prod _{k=2}^{n}k^{n \choose k}$ 트리를 선택한다.^[6]
대역폭은 정확히 $\sum _{i=0}^{n-1}{\binom {i}{\lfloor i/2\rfloor }}$ $\sum _{i=0}^{n-1}{\binom {i}{\lfloor i/2\rfloor }}$ = $\sum _{i=0}^{n-1}{\binom {i}{\lfloor i/2\rfloor }}$ $\sum _{i=0}^{n-1}{\binom {i}{\lfloor i/2\rfloor }}$ - 1 $\sum _{i=0}^{n-1}{\binom {i}{\lfloor i/2\rfloor }}$ ( $\sum _{i=0}^{n-1}{\binom {i}{\lfloor i/2\rfloor }}$ $\sum _{i=0}^{n-1}{\binom {i}{\lfloor i/2\rfloor }}$ i $\sum _{i=0}^{n-1}{\binom {i}{\lfloor i/2\rfloor }}$ / $\sum _{i=0}^{n-1}{\binom {i}{\lfloor i/2\rfloor }}$ $\sum _{i=0}^{n-1}{\binom {i}{\lfloor i/2\rfloor }}$ ) ${\$ i $/2\loor$ $\sum _{i=0}^{n-1}{\binom {i}{\lfloor i/2\rfloor }}$ ^[7]
${\sqrt {n2^{n}}}$ ${\sqrt {n2^{n}}}$ ${\$ 에 비례하는 무채색 수를 가지지만 비례의 상수는 정확히 알 수 없다.^[8]
인접 행렬의 고유값 $(- n, -n$ + 2 $, -n$ + 4, $..., n$ - 4 $, n$ - 2 $,$ $n)$ 과 라플라시안 행렬의 고유값 $(0,$ 2, $..., 2n)$ 이 있다.k번째 고유값은 두 경우 모두 ${\binom {n}{k}}$ 다중성 ${\binom {n}{k}}$ k ${\binom {n}{k}}$ ) ${\$ 을(를) 가진다.
$등측위수$ h $(G)$ = $1$ 이다.

모든 $n$ > $1$ 에 대한 패밀리 $Q$ 는_n 레비 그래프 계열이다.

문제

1에서 4까지의 치수 n에 대한 즉시 뱀(L_s) 및 코일(L_c) 최대 길이

주어진 하이퍼큐브 그래프의 유도 서브그래프인 가장 긴 경로나 사이클을 찾는 문제를 '스네이크 인 더 박스(snake-in-the-box) 문제'라고 한다.null

Szymanski의 추측은 통신을 위한 네트워크 토폴로지로서 하이퍼큐브의 적합성에 관한 것이다.그것은 각 하이퍼큐브 정점을 연결해야 하는 다른 정점에 연결하는 순열을 어떻게 선택하든, 어떤 방향의 가장자리를 공유하지 않는 경로로 이러한 정점 쌍을 연결하는 방법이 항상 존재한다고 말한다.^[9]null

참고 항목

메모들

^ Watkins, John J. (2004), Across the Board: The Mathematics of Chessboard Problems, Princeton University Press, p. 68, ISBN 978-0-691-15498-5.
^ Mills, W. H. (1963), "Some complete cycles on the $n$ -cube", Proceedings of the American Mathematical Society, American Mathematical Society, 14 (4): 640–643, doi:10.2307/2034292, JSTOR 2034292.
^ Fink, J. (2007), "Perfect matchings extend to Hamiltonian cycles in hypercubes", Journal of Combinatorial Theory, Series B, 97 (6): 1074–1076, doi:10.1016/j.jctb.2007.02.007.
^ 러스키, F., 새비지, C.짝짓기는 오픈 문제 가든의 하이퍼큐브에서 해밀턴 사이클까지 확장된다.2007.
^ Ringel, G. (1955), "Über drei kombinatorische Probleme am $n$ -dimensionalen Wiirfel und Wiirfelgitter", Abh. Math. Sem. Univ. Hamburg, 20: 10–19, MR 0949280
^ ^a ^b Harary, Frank; Hayes, John P.; Wu, Horng-Jyh (1988), "A survey of the theory of hypercube graphs" (PDF), Computers & Mathematics with Applications, 15 (4): 277–289, doi:10.1016/0898-1221(88)90213-1, hdl:2027.42/27522, MR 0949280.
^ 그래프, L.H. 하퍼, 결합 이론 저널, 1,385–393, doi:10.1016/S0021-9800(66)80059-5의 최적 번호 및 등측위 문제
^ Roichman, Y. (2000), "On the Achromatic Number of Hypercubes", Journal of Combinatorial Theory, Series B, 79 (2): 177–182, doi:10.1006/jctb.2000.1955.
^ Szymanski, Ted H. (1989), "On the Permutation Capability of a Circuit-Switched Hypercube", Proc. Internat. Conf. on Parallel Processing, vol. 1, Silver Spring, MD: IEEE Computer Society Press, pp. 103–110.

참조

Harary, F.; Hayes, J. P.; Wu, H.-J. (1988), "A survey of the theory of hypercube graphs", Computers & Mathematics with Applications, 15 (4): 277–289, doi:10.1016/0898-1221(88)90213-1, hdl:2027.42/27522.

[1] Watkins, John J. (2004), Across the Board: The Mathematics of Chessboard Problems, Princeton University Press, p. 68, ISBN 978-0-691-15498-5.

[2] Mills, W. H. (1963), "Some complete cycles on the $n$ -cube", Proceedings of the American Mathematical Society, American Mathematical Society, 14 (4): 640–643, doi:10.2307/2034292, JSTOR 2034292.

[3] Fink, J. (2007), "Perfect matchings extend to Hamiltonian cycles in hypercubes", Journal of Combinatorial Theory, Series B, 97 (6): 1074–1076, doi:10.1016/j.jctb.2007.02.007.

[4] 러스키, F., 새비지, C.짝짓기는 오픈 문제 가든의 하이퍼큐브에서 해밀턴 사이클까지 확장된다.2007.

[ringel-5] Ringel, G. (1955), "Über drei kombinatorische Probleme am $n$ -dimensionalen Wiirfel und Wiirfelgitter", Abh. Math. Sem. Univ. Hamburg, 20: 10–19, MR 0949280

[hhw-6] Harary, Frank; Hayes, John P.; Wu, Horng-Jyh (1988), "A survey of the theory of hypercube graphs" (PDF), Computers & Mathematics with Applications, 15 (4): 277–289, doi:10.1016/0898-1221(88)90213-1, hdl:2027.42/27522, MR 0949280.

[7] 그래프, L.H. 하퍼, 결합 이론 저널, 1,385–393, doi:10.1016/S0021-9800(66)80059-5의 최적 번호 및 등측위 문제

[8] Roichman, Y. (2000), "On the Achromatic Number of Hypercubes", Journal of Combinatorial Theory, Series B, 79 (2): 177–182, doi:10.1006/jctb.2000.1955.

[9] Szymanski, Ted H. (1989), "On the Permutation Capability of a Circuit-Switched Hypercube", Proc. Internat. Conf. on Parallel Processing, vol. 1, Silver Spring, MD: IEEE Computer Society Press, pp. 103–110.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

Search

하이퍼큐브 그래프

네임스페이스

더

목차

건설

예

특성.

초당성

해밀턴시티

기타 속성

문제

참고 항목

메모들

참조

하이퍼큐브 그래프
하이퍼큐브 그래프₄ Q
정점	$2 n$
가장자리	$2 n -1 n$
지름	$n$
둘레	$4$ 만약 $n이면$ 2
자동형성	$n! 2 n$
색수	$2$
스펙트럼	$\{(n-2k)^{\binom {n}{k};k=0,\ldots,n\}$
특성.	대칭 거리 정규 단위 거리 해밀턴어 양립자
표기법	$Q n$
그래프 및 모수 표