피보나치 큐브

Fibonacci cube

피보나치 정육면체 또는 피보나치 네트워크는 숫자 이론에서 그것의 기원에서 파생된 풍부한 재귀적 특성을 가진 비방향 그래프의 계열이다.수학적으로 그것들은 하이퍼큐브 그래프와 유사하지만, 피보나치 정점 수를 가지고 있다.피보나치 큐브는 병렬 또는 분산 시스템을 연결하기 위한 상호 접속 위상의 맥락에서 Hsu(1993)에서 처음으로 명시적으로 정의되었다.그것들은 또한 화학 그래프 이론에도 적용되었다.

피보나치 큐브는 피보나치 코드와 해밍 거리, 경로 그래프의 개별 정점 집합 또는 분배 래티스를 통해 정의될 수 있다.

정의

하이퍼큐브 그래프와 마찬가지로, 순서 n의 피보나치 큐브 정점에는 길이 n의 비트스트링으로 라벨을 붙일 수 있으며, 라벨이 단일 비트로 다를 때마다 두 정점이 인접해 있다.그러나 피보나치 큐브에서 허용되는 라벨은 연속 2비트가 없는 비트스트링뿐이다.하이퍼큐브의 라벨이 이진수로 해석되는 경우, 피보나치 큐브의 라벨은 부분집합, 즉 섬유수다.가능한 Fn + 2 라벨이 있으며, 여기서 F는n n번째 피보나치 숫자를 나타내며, 따라서 순서 n의 피보나치 큐브에는 F 정점이n + 2 있다.

하이퍼큐브의 하위 그래프로서 피보나치 큐브(빨간색으로 표시)

그러한 네트워크의 노드는 0부터n + 2 F - 1까지 연속 정수를 할당할 수 있다. 이 숫자에 해당하는 비트스트링은 Zeckendorf 표현에 의해 주어진다.[1]

피보나치 큐브 순서 6

대수구조

순서 n의 피보나치 입방체는 n-vertex 경로 그래프의 보완 그래프의 심플렉스 그래프다.[2]즉, 피보나치 큐브의 각 꼭지점은 경로 보완 그래프의 클릭을 나타내며, 또는 경로 자체에서 동등하게 독립된 세트를 나타낸다. 두 피보나치 큐브 정점은 단일 요소의 추가 또는 제거에 의해 그들이 나타내는 클릭 또는 독립 집합이 다른 경우 인접한다.따라서 다른 심플렉스 그래프와 마찬가지로 피보나치 큐브는 중위수 그래프와 더 일반적으로 부분적인 큐브다.[3]피보나치 큐브에 있는 정점 세 개의 중위수는 세 개의 라벨의 비트 다수 함수를 계산하여 찾을 수 있다. 세 개의 라벨 각각에 2개의 연속 1비트가 없는 경우, 그들의 다수가 동일하다.

피보나치 큐브는 비르코프의 표현 정리를 통해 지그재그로 된 포셋으로부터 얻을 수 있는 분배 격자의 그래프로서, 순서 관계의 교대 순서에 의해 정의된 부분 순서 집합 a < b > c < d > e < f > ...[4]또한 동일한 격자에 대한 다른 그래프-이론적 설명도 있다. 양분 그래프의 독립적 집합은 양분 한쪽에서 요소를 제거하고 양분 반대쪽에 요소를 추가함으로써 서로 다를 경우 한 독립된 집합이 다른 집합보다 작은 부분적인 순서를 지정할 수 있다. 이 순서와 함께, 두 번째 순서는 다음과 같다.독립 집합은 분배 격자를 형성하며,[5] 이 구조를 경로 그래프에 적용하면 피보나치 큐브와 관련된 격자가 된다.

속성 및 알고리즘

순서 n의 피보나치 입방체는 순서 n - 1의 피보나치 입방체(0비트로 시작하는 라벨이 있는 노드)와 순서 n - 2의 피보나치 입방체(1비트로 시작하는 라벨이 있는 노드)로 분할할 수 있다.[6]

모든 피보나치 큐브에는 해밀턴의 길이 있다.좀 더 구체적으로, 위에서 설명한 파티션에 순응하는 경로가 존재한다. 즉, 첫 번째 비트 0이 있는 노드와 두 개의 연속적인 반복에서 첫 번째 비트 1이 있는 노드를 방문한다.이 두 부분 내에서 경로는 동일한 규칙에 의해 재귀적으로 구성될 수 있으며, 두 번째 비트가 0인 부분 끝의 두 부분 부분을 연결할 수 있다.따라서, 예를 들어, 순서 4의 피보나치 큐브에서, 이러한 방식으로 구성된 순서는 (0100-0101-0001-0000-10)-(10-1000-100-001)이며, 여기서 괄호는 칸막이의 두 하위 그래프 내의 하위 그래프 내에서의 하위 부분을 구분한다.짝수 노드 수가 2개 이상인 피보나치 큐브는 해밀턴 사이클을 가진다.[7]

무나리니&살비(2002)는 피보나치 큐브의 반지름과 독립 번호를 조사한다.이 그래프들은 초당적이고 해밀턴 경로를 가지고 있기 때문에, 그들의 최대 독립형 집합은 가장 가까운 정수로 반올림된 전체 그래프 정점 수의 절반과 같은 정점을 가지고 있다.[8]순서가 n인 피보나치 입방체의 직경은 n이고, 반지름은 n/2(again, 가장 가까운 정수로 반올림)[9]이다.

타라넨코 & 베셀(2007)은 크기가 거의 선형에 가까운 시간에 그래프가 피보나치 큐브인지 시험할 수 있다는 것을 보여주었다.

적용들

Hsu(1993)와 Hsu, Page & Luuh(1993)는 병렬 컴퓨팅에서 네트워크 토폴로지로 피보나치 큐브를 사용할 것을 제안했다.통신 네트워크로서, 피보나치 큐브는 하이퍼큐브와 유사한 유익한 속성을 가지고 있다: 정점당 입사 에지 수는 최대 n/2이고 네트워크의 직경은 최대 n으로 정점 수의 로그에 비례하며 네트워크의 작은 네트워크로 분할되는 능력이다.동일한 유형으로 여러 병렬 계산 작업 간에 분할할 수 있다.[7]피보나치 큐브는 또한 분산 계산에서 라우팅과 방송을 위한 효율적인 프로토콜을 지원한다.[10]

클라브자르&지거트(2005)는 특정 분자 그래프의 완벽한 일치 집단을 설명하기 위해 화학 그래프 이론에 피보나치 큐브를 적용한다.평면 그래프 G로 기술된 분자 구조에서 G의 공진 그래프 또는 (Z-변환 그래프)는 정점이 G의 완벽한 일치를 설명하고 대칭 차이가 G의 내부 면인 완벽한 일치를 가장자리에 연결하는 그래프다. 다순환 방향족 탄화수소는 육각형의 하위 그래프로 설명될 수 있다.평면의 타일링과 공진 그래프는 이러한 분자의 가능한 이중 촉매 구조를 설명한다.클라바자르&지거트(2005)에서 알 수 있듯이, 헥사곤의 사슬로 형성된 탄화수소는 한 줄로 인접한 헥사곤 3개가 없는 가장자리부터 가장자리까지 연결되어 있으며, 정확히 피보나치 그래프인 공명 그래프를 가지고 있다.보다 일반적으로 장, 오우 & 야오(2009)는 피보나치 큐브를 공진 그래프로 갖는 평면 양분 그래프의 등급을 설명했다.[2]

관련 그래프

일반화된 피보나치 큐브는 k번째 순서 피보나치 숫자에 기초하여 Hsu & Chung(1993)에 의해 제시되었고, 이후 보다 일반적인 형태의 선형 재귀에 기초하여 Hsu, Chung & Das(1997)에 의한 선형 재귀 네트워크라고 불리는 더 큰 등급의 네트워크로 확장되었다.우(1997)는 서로 다른 초기 조건에 기초하여 2차 순서 피보나치 정육면체를 수정했다.또 다른 관련 그래프는 루카스 큐브인데, 각 비트스트링의 첫 번째 위치와 마지막 위치 모두에서 1비트를 금지함으로써 피보나치 큐브에서 정의한 루카스 큐브 숫자의 정점을 가진 그래프로서, 데도, 토리 & 샐비(2002)는 피보나치 큐브와 루카스 큐브의 색채 특성을 조사했다.

메모들

  1. ^ 클라브샤르(2011), 페이지 3-4.
  2. ^ a b 클라브샤르(2011), 페이지 3.
  3. ^ 클라바샤르(2005); 클라바샤르(2011), 정리 5.1, 페이지 10.
  4. ^ 간스너(1982)는 이 격자에는 피보나치 원소의 수가 많다는 사실을 "잘 알려진 사실"이라고 부르고, 스탠리(1986)는 연습에서 그에 대한 설명을 요구한다.Höft & Höft(1985), Beck(1990), Salvi & Salvi(2008)도 참조하십시오.
  5. ^ 프롭(1997년).
  6. ^ 클라브샤르(2011), 페이지 4~5.
  7. ^ a b 콩, 정 & 샤르마(1993)
  8. ^ 클라브샤르(2011), 페이지 6.
  9. ^ 클라바르(2011), 페이지 9.
  10. ^ Hsu(1993);스토즈메노비치 1998.

참조

  • Beck, István (1990), "Partial orders and the Fibonacci numbers", Fibonacci Quarterly, 28 (2): 172–174, MR 1051291.
  • Cong, B.; Zheng, S. Q.; Sharma, S. (1993), "On simulations of linear arrays, rings and 2D meshes on Fibonacci cube networks", Proc. 7th Int. Parallel Processing Symposium, pp. 748–751, doi:10.1109/IPPS.1993.262788.
  • Dedó, Ernesto; Torri, Damiano; Salvi, Norma Zagaglia (2002), "The observability of the Fibonacci and the Lucas cubes", Discrete Mathematics, 255 (1–3): 55–63, doi:10.1016/S0012-365X(01)00387-9.
  • Gansner, Emden R. (1982), "On the lattice of order ideals of an up-down poset", Discrete Mathematics, 39 (2): 113–122, doi:10.1016/0012-365X(82)90134-0, MR 0675856.
  • Höft, Hartmut; Höft, Margret (1985), "A Fibonacci sequence of distributive lattices", Fibonacci Quarterly, 23 (3): 232–237, MR 0806293.
  • Hsu, W.-J. (1993), "Fibonacci cubes: a new interconnection topology", IEEE Transactions on Parallel and Distributed Systems, 4 (1): 3–12, doi:10.1109/71.205649.
  • Hsu, W.-J.; Chung, M. J. (1993), "Generalized Fibonacci cubes", 1993 International Conference on Parallel Processing - ICPP'93, vol. 1, pp. 299–302, doi:10.1109/ICPP.1993.95.
  • Hsu, W.-J.; Page, C. V.; Liu, J.-S. (1993), "Fibonacci cubes: a class of self-similar graphs", Fibonacci Quarterly, 31 (1): 65–72.
  • Hsu, W.-J.; Chung, M. J.; Das, A. (1997), "Linear recursive networks and their applications in distributed systems", IEEE Transactions on Parallel and Distributed Systems, 8 (7): 673–680, doi:10.1109/71.598343.
  • Klavžar, Sandi (2005), "On median nature and enumerative properties of Fibonacci-like cubes", Discrete Mathematics, 299 (1–3): 145–153, doi:10.1016/j.disc.2004.02.023.
  • Klavžar, Sandi (2011), "Structure of Fibonacci cubes: a survey" (PDF), IMFM Preprint Series, Ljubljana, Slovenia: Institute of Mathematics, Physics and Mechanics, 49 (1150).
  • Klavžar, Sandi; Žigert, Petra (2005), "Fibonacci cubes are the resonance graphs of Fibonaccenes", Fibonacci Quarterly, 43 (3): 269–276, archived from the original on 2007-02-08.
  • Munarini, Emanuele; Salvi, Norma Zagaglia (2002), "Structural and enumerative properties of the Fibonacci cubes", Discrete Mathematics, 255 (1–3): 317–324, doi:10.1016/S0012-365X(01)00407-1.
  • Propp, James (1997), "Generating random elements of finite distributive lattices", Electronic Journal of Combinatorics, 4 (2): R15, arXiv:math.CO/9801066.
  • Salvi, Rodolfo; Salvi, Norma Zagaglia (2008), "Alternating unimodal sequences of Whitney numbers", Ars Combinatoria, 87: 105–117, MR 2414008.
  • Stanley, Richard P. (1986), Enumerative Combinatorics, Wadsworth, Inc. 연습 3.23a 157쪽
  • Stojmenovic, Ivan (1998), "Optimal deadlock-free routing and broadcasting on Fibonacci cube networks" (PDF), Utilitas Mathematica, 53: 159–166, archived from the original (PDF) on 2011-07-25.
  • Taranenko, A.; Vesel, A. (2007), "Fast recognition of Fibonacci cubes", Algorithmica, 49 (2): 81–93, doi:10.1007/s00453-007-9026-5.
  • Wu, Jie (1997), "Extended Fibonacci cubes", IEEE Transactions on Parallel and Distributed Systems, 8 (12): 1203–1210, doi:10.1109/71.640012.
  • Zhang, Heping; Ou, Lifeng; Yao, Haiyuan (2009), "Fibonacci-like cubes as Z-transformation graphs", Discrete Mathematics, 309 (6): 1284–1293, doi:10.1016/j.disc.2008.01.053, MR 2510538.