부분 큐브

그래프 이론에서 부분 입방체는 하이퍼큐브의 서브그래프에 등축하는 그래프다.^[1]즉, 부분 큐브에 있는 두 정점 사이의 거리가 하이퍼큐브에 있는 정점 사이의 거리와 동일한 방식으로 부분 큐브를 하이퍼큐브 서브그래프로 식별할 수 있다.동등하게, 부분 입방체는 그래프에서 두 정점 사이의 거리가 라벨 사이의 해밍 거리와 같도록 정점에 동일한 길이의 비트 문자열로 라벨을 붙일 수 있는 그래프다.그러한 라벨링은 해밍 라벨링이라고 불리운다; 그것은 부분 큐브를 하이퍼큐브에 삽입하는 등축계를 나타낸다.

역사

Firsov(1965)는 그래프를 하이퍼큐브에 삽입하는 등축학 연구를 처음 했다.그러한 임베딩을 인정하는 그래프는 조코비치(1973년)와 윙클러(1984년)가 특징이며, 이후 부분 큐브(partial cube)로 명명되었다.같은 구조에 대한 별도의 연구 라인이, 그래프의 하이퍼큐브 라벨링보다는 세트 패밀리들의 용어로는, 쿠즈민&오브친니코프(1975)와 팔마뉴앤도이뇽(1997)이 그 뒤를 이었다.^[2]

예

모든 나무는 부분 큐브다.예를 들어, 트리 T에 m 가장자리가 있다고 가정하고 0에서 m - 1까지(임의적으로) 번호를 매긴다.트리에 대한 루트 꼭지점 r을 선택하고 임의로 각 꼭지점 v에 에지 i가 T의 r에서 v까지의 경로에 위치할 때마다 1을 갖는 m 비트 문자열을 사용하여 레이블을 지정하십시오.예를 들어, r 자체는 모두 0비트인 라벨을 가질 것이고, 그 이웃은 1비트인 라벨을 가질 것이다.그 다음 두 라벨 사이의 해밍 거리는 트리의 두 꼭지점 사이의 거리여서 이 라벨링은 T가 부분 큐브임을 보여준다.

모든 하이퍼큐브 그래프는 그 자체로 부분 큐브인데, 하이퍼큐브의 치수와 동일한 길이의 모든 다른 비트스트링으로 라벨을 붙일 수 있다.

보다 복잡한 예는 다음과 같다.

• 정점 레이블이 n 또는 n + 1 nonzero 비트가 있는 가능한 모든(2n + 1) 자리 비트 문자열로 구성된 그래프를 생각해 보십시오. 여기서 두 정점은 하나의 비트만큼 다를 때마다 인접해 있다.이 라벨링은 이러한 그래프를 하이퍼큐브(특정 길이의 모든 비트스트레이팅 그래프, 동일한 인접 조건)에 포함시키는 것을 정의하며, 거리 보존이 가능하다.결과 그래프는 초당적 Kneser 그래프인데, 이러한 방식으로 n = 2로 형성된 그래프는 정점이 20개, 가장자리가 30개인데, 이를 데스아게스 그래프라고 한다.
• 모든 중위수 그래프는 부분 큐브다.^[3]나무와 하이퍼큐브 그래프는 중위수 그래프의 예다.중위수 그래프에는 정사각형 그래프, 심플렉스 그래프, 피보나치 큐브는 물론 유한분포 래티스의 커버 그래프가 포함되기 때문에 모두 부분적 큐브다.
• 유클리드 평면의 선 배열을 나타내는 평면 이중 그래프는 부분 입방체다.보다 일반적으로, 임의의 수의 치수의 유클리드 공간에 있는 하이퍼플레인 배열의 경우 배열의 각 셀에 대한 꼭지점과 인접한 두 셀에 대한 가장자리가 있는 그래프는 부분 입방체다.^[4]
• 모든 꼭지점에 정확히 세 개의 이웃이 있는 부분 입방체를 입방체 부분 입방체라고 한다.입방체 부분 입방체의 무한 계열이 몇 개 알려져 있지만, 다른 산발적인 많은 예와 함께 평면 그래프가 아닌 유일한 입방체 부분 입방체 그래프는 데스아게스 그래프뿐이다.^[5]
• 항우울제의 기본 그래프는 항우울제의 각 세트에 대한 정점과 단일 원소에 의해 다른 두 세트에 대한 가장자리를 갖는 모든 항우울제의 기본 그래프는 항상 부분 입방체다.
• 한정된 세트의 부분 정육면체 중 카르테시안 제품은 또 다른 부분 정육면체다.^[6]
• 전체 그래프의 하위 분할은 모든 전체 그래프 가장자리가 두 에지 경로로 분할되거나 사건 가장자리가 모두 분리되지 않고 모든 비사건 가장자리가 짝수 길이 경로로 분할된 하나의 완전한 그래프 꼭지점이 있는 경우에만 부분 입방체다.^[7]

조코비치-윙클러 관계

부분 큐브에 대한 많은 이론들은 그래프의 가장자리에 정의된 특정한 이항 관계에 직접 또는 간접적으로 기초한다.This relation, first described by Djoković (1973) and given an equivalent definition in terms of distances by Winkler (1984), is denoted by ${\displaystyle \Theta }$. Two edges ${\displaystyle e=\{x,y\}}$ and ${\displaystyle f=\{u,v\}}$ are defined to be in the relation ${\displaystyle \Theta$}, e θ f ${\displaystyle e{\mathrel {\}$라고 쓰여 있음$Theta$ }}}, 만약 d( x ,u)+ d( y, v) ≠ d( x, v)+ d ( y ,u ) ${\displaystyle d(x,u)+d(y,v)\not=d(x$,v$)+d(y,u$ 이 관계는 반사적이고 대칭적이지만, 일반적으로는 아니다.

Winkler는 연결된 그래프가 초당적이고 relation ${\displaystyle$ ^[8]$\Teta}$ 관계가 전이적인 경우에만 부분 큐브임을 보여주었다.이 경우 등가 관계를 형성하고 각 등가 등급은 그래프의 연결된 하위 그래프 두 개를 서로 분리한다.해밍 라벨링은 조코비치-윙클러 관계의 각 등가 등급에 각 라벨의 1비트를 할당하여 얻을 수 있다. 가장자리의 등가 등급으로 분리된 두 개의 연결된 하위 그래프 중 하나에서 모든 정점이 라벨의 해당 위치에 0을 가지고 있고, 다른 연결된 하위 그래프에서 모든 정점이 1을 가지고 있다.같은 처지에

인식

부분 큐브를 인식할 수 있으며 해밍 라벨이 구성된 시간이 O (n 2) ${\displaystyle$O$(n^{2})$이며, 여기서 n{\$displaystyle n}$은 그래프에서 정점 수입니다.^[9]부분 큐브를 지정하면, O (nm) ${\displaystyle$ O$(nm$ O(n 2) ${\displaystyle O(n^{2})}$ -시간 인식 알고리즘으로 각 꼭지점에서 첫 번째 폭 검색을 수행하여 조코비치-윙클러 관계의 동등성 클래스를 구성하는 것이 간단하다.그래프를 통과하는 한 번의 통과로 다중 폭의 첫 번째 검색을 구성한 다음 별도의 알고리즘을 적용하여 이 계산 결과가 유효한 부분 큐브 라벨링인지 검증한다.

치수

부분 입방체의 등축 치수는 등축적으로 삽입될 수 있는 하이퍼큐브의 최소 치수로 조코비치-윙클러 관계의 등가 등급 수와 동일하다.예를 들어, n ${\displaystyle n}$ -vertex 트리의 등축 치수는 가장자리 수, n- 1 ${\displaystyle n-1}$이다. 이 치수의 하이퍼큐브에 부분 큐브를 내장하는 것은 하이퍼큐브의 대칭까지 독특하다.^[10]

모든 하이퍼큐브와 따라서 모든 부분 큐브는 등축적으로 정수 격자에 삽입될 수 있다.그래프의 격자 치수는 그래프가 등축적으로 포함될 수 있는 정수 격자의 최소 치수다.격자 치수는 등축 치수보다 상당히 작을 수 있다. 예를 들어, 나무의 경우 나무의 잎 수의 절반(가장 가까운 정수로 반올림).모든 그래프의 격자 치수 및 최소 치수의 격자 내장 치수는 보조 그래프에서 최대 일치를 기반으로 하는 알고리즘에 의해 다항 시간에서 찾을 수 있다.^[11]

또한 보다 전문화된 구조물에 임베딩하는 것에 기초하여 부분 정육면체의 다른 형태도 정의되었다.^[12]

화학 그래프에 적용 이론

그래프를 하이퍼큐브에 내장하는 등축은 화학 그래프 이론에서 중요한 응용을 한다.벤제노이드 그래프는 6각형 격자 안에 사이클의 내부와 위에 놓여 있는 모든 정점과 가장자리로 구성된 그래프다.그러한 그래프는 많은 종류의 유기 분자인 벤제노이드 탄화수소의 분자 그래프다.그러한 모든 그래프는 부분 큐브다.그러한 그래프의 해밍 라벨링은 해당 분자의 Wiener 지수를 계산하는 데 사용될 수 있으며, 이 지수를 사용하여 화학적 성질을 예측할 수 있다.^[13]

탄소로부터 형성된 다른 분자 구조인 다이아몬드 입방체도 부분 입방체 그래프를 형성한다.^[14]

메모들

참조

• Beaudou, Laurent; Gravier, Sylvain; Meslem, Kahina (2008), "Isometric embeddings of subdivided complete graphs in the hypercube" (PDF), SIAM Journal on Discrete Mathematics, 22 (3): 1226–1238, doi:10.1137/070681909, MR 2424849
• Cabello, S.; Eppstein, D.; Klavžar, S. (2011), "The Fibonacci dimension of a graph", Electronic Journal of Combinatorics, 18 (1), P55, arXiv:0903.2507, Bibcode:2009arXiv0903.2507C, doi:10.37236/542.
• Djoković, Dragomir Ž. (1973), "Distance-preserving subgraphs of hypercubes", Journal of Combinatorial Theory, Series B, 14 (3): 263–267, doi:10.1016/0095-8956(73)90010-5, MR 0314669.
• Eppstein, David (2005), "The lattice dimension of a graph", European Journal of Combinatorics, 26 (6): 585–592, arXiv:cs.DS/0402028, doi:10.1016/j.ejc.2004.05.001.
• Eppstein, David (2006), "Cubic partial cubes from simplicial arrangements", Electronic Journal of Combinatorics, 13 (1), R79, arXiv:math.CO/0510263, doi:10.37236/1105.
• Eppstein, David (2008), "Recognizing partial cubes in quadratic time", Proc. 19th ACM-SIAM Symposium on Discrete Algorithms, pp. 1258–1266, arXiv:0705.1025, Bibcode:2007arXiv0705.1025E.
• Eppstein, David (2009), "Isometric diamond subgraphs", Proc. 16th International Symposium on Graph Drawing, Heraklion, Crete, 2008, Lecture Notes in Computer Science, vol. 5417, Springer-Verlag, pp. 384–389, arXiv:0807.2218, doi:10.1007/978-3-642-00219-9_37.
• Falmagne, J.-C.; Doignon, J.-P. (1997), "Stochastic evolution of rationality", Theory and Decision, 43 (2): 107–138, doi:10.1023/A:1004981430688.
• Firsov, V.V. (1965), "On isometric embedding of a graph into a Boolean cube", Cybernetics, 1: 112–113, doi:10.1007/bf01074705. Ovchinnikov(2011년)의 인용.
• Hadlock, F.; Hoffman, F. (1978), "Manhattan trees", Utilitas Mathematica, 13: 55–67. Ovchinnikov(2011년)의 인용.
• Imrich, Wilfried; Klavžar, Sandi (2000), Product Graphs: Structure and Recognition, Wiley-Interscience Series in Discrete Mathematics and Optimization, New York: John Wiley & Sons, ISBN 978-0-471-37039-0, MR 1788124.
• Klavžar, Sandi; Gutman, Ivan; Mohar, Bojan (1995), "Labeling of benzenoid systems which reflects the vertex-distance relations" (PDF), Journal of Chemical Information and Computer Sciences, 35 (3): 590–593, doi:10.1021/ci00025a030.
• Kuzmin, V.; Ovchinnikov, S. (1975), "Geometry of preferences spaces I", Automation and Remote Control, 36: 2059–2063. Ovchinnikov(2011년)의 인용.
• Ovchinnikov, Sergei (2011), Graphs and Cubes, Universitext, Springer. 특히 5장 "부분 큐브", 페이지 127–181을 참조하십시오.
• Winkler, Peter M. (1984), "Isometric embedding in products of complete graphs", Discrete Applied Mathematics, 7 (2): 221–225, doi:10.1016/0166-218X(84)90069-6, MR 0727925.