フィボナッチキューブ

グラフ理論の数学分野において、フィボナッチキューブまたはフィボナッチネットワークは、数論に由来する豊富な再帰特性を持つ無向グラフのファミリーです。数学的にはハイパーキューブグラフに似ていますが、頂点の数がフィボナッチ数になっています。フィボナッチキューブは、並列システムや分散システムを接続するための相互接続トポロジーの文脈で、Hsu (1993)によって初めて明示的に定義されました。また、化学グラフ理論にも応用されています。

フィボナッチキューブは、フィボナッチコードとハミング距離、パスグラフの独立した頂点の集合、または分配格子によって定義できます。

ハイパーキューブグラフと同様に、 n次フィボナッチキューブの頂点には、長さnのビット列でラベルを付けることができ、ラベルが 1 ビットだけ異なる場合に 2 つの頂点が隣接します。ただし、フィボナッチキューブでは、連続する 2 つの 1 ビットを持たないビット列のみがラベルとして許可されます。ハイパーキューブのラベルをバイナリ数として解釈すると、フィボナッチキューブのラベルは部分集合であるフィボナッチバイナリ数になります。F n_はn番目のフィボナッチ数を表すため、可能なラベルはF _{n + 2}個あり、したがって、 n次フィボナッチキューブにはF _{n + 2}個の頂点があります。    

このようなネットワークのノードには、0 からF _{n  +  2} − 1 までの連続する整数を割り当てることができます。これらの数値に対応するビット列は、ゼッケンドルフ表現によって与えられます。^{[ 1 ]}  

n次フィボナッチ キューブは、 n頂点パス グラフの補グラフの単体グラフです。 ^{[ 2 ]}つまり、フィボナッチ キューブの各頂点は、パス補グラフのクリーク、または同等にパス自体の独立集合を表します。2 つのフィボナッチ キューブの頂点は、それらが表すクリークまたは独立集合が 1 つの要素の追加または削除によって異なる場合に隣接します。したがって、他の単体グラフと同様に、フィボナッチ キューブはメディアン グラフであり、より一般的には部分キューブです。^{[ 3 ]}フィボナッチ キューブの任意の 3 つの頂点のメディアンは、3 つのラベルのビットごとの多数決関数を計算することによって見つけることができます。3 つのラベルのそれぞれに 2 つの連続する 1 ビットがない場合、それらの多数決についても同じことが言えます。

フィボナッチキューブは、ジグザグ半順序集合（a < b > c < d > e < f > ...の交互の順序関係によって定義される半順序集合）からバーコフの表現定理によって得られる分配格子のグラフでもあります。 ^{[ 4 ]}また、同じ格子の別のグラフ理論的記述もあります。任意の二部グラフの独立集合には、二部グラフの一方の側から要素を削除し、もう一方の側に要素を追加することによって異なる場合、一方の独立集合が他方の独立集合より小さいという半順序を与えることができます。この順序により、独立集合は分配格子を形成し、^{[ 5 ]}この構成をパスグラフに適用すると、フィボナッチキューブに関連付けられた格子が得られます。

n次フィボナッチキューブは、n − 1 次フィボナッチキューブ(ラベルが 0 ビットで始まるノード) とn − 2 次フィボナッチキューブ (ラベルが 1 ビットで始まるノード) に分割できます。^{[ 6 ]}    

Every Fibonacci cube has a Hamiltonian path. More specifically, there exists a path that obeys the partition described above: it visits the nodes with first bit 0 and the nodes with first bit 1 in two contiguous subsequences. Within these two subsequences, the path can be constructed recursively by the same rule, linking the two subsequences at the ends of the subsequences at which the second bit is 0. Thus, e.g., in the Fibonacci cube of order 4, the sequence constructed in this way is (0100-0101-0001-0000-0010)-(1010-1000-1001), where the parentheses demark the subsequences within the two subgraphs of the partition. Fibonacci cubes with an even number of nodes greater than two have a Hamiltonian cycle.^[7]

Munarini & Salvi (2002) investigate the radius and independence number of Fibonacci cubes. Because these graphs are bipartite and have Hamiltonian paths, their maximum independent sets have a number of vertices that is equal to half of the number of vertices in the whole graph, rounded up to the nearest integer.^[8] The diameter of a Fibonacci cube of order n is n, and its radius is n/2 (again, rounded up to the nearest integer).^[9]

Taranenko & Vesel (2007) showed that it is possible to test whether a graph is a Fibonacci cube in time near-linear in its size.

Hsu (1993) and Hsu, Page & Liu (1993) suggested using Fibonacci cubes as a network topology in parallel computing. As a communications network, the Fibonacci cube has beneficial properties similar to those of the hypercube: the number of incident edges per vertex is at most n/2 and the diameter of the network is at most n, both proportional to the logarithm of the number of vertices, and the ability of the network to be partitioned into smaller networks of the same type allows it to be split among multiple parallel computation tasks.^[7] Fibonacci cubes also support efficient protocols for routing and broadcasting in distributed computations.^[10]

Klavžar & Žigert (2005) は、特定の分子グラフの完全マッチングの族を記述するために、化学グラフ理論にフィボナッチキューブを適用しています。平面グラフGで記述される分子構造の場合、Gの共鳴グラフまたは ( Z変換グラフ) は、頂点がGの完全マッチングを記述し、辺がGの内部面である完全マッチングのペアを接続するグラフです。 多環芳香族炭化水素は、平面の六角形タイル張りの部分グラフとして記述でき、共鳴グラフはこれらの分子の可能な二重結合構造を記述します。Klavžar & Žigert (2005) が示すように、隣接する3 つの六角形が一直線上に並ばずに辺同士で連結された六角形の鎖によって形成される炭化水素は、フィボナッチグラフと完全に一致する共鳴グラフを持ちます。より一般的には、Zhang、Ou 、 Yao（2009）は、共鳴グラフとしてフィボナッチキューブを持つ平面二部グラフのクラスを記述した。^{[ 2 ]}

一般化フィボナッチキューブは、k 次フィボナッチ数に基づいてHsuとChung (1993)によって提示され、後にHsu、ChungおよびDas (1997)によって、より一般的な形式の線形再帰に基づいて、線形再帰ネットワークと呼ばれるより大きなクラスのネットワークにさらに拡張されました。Wu (1997) は、異なる初期条件に基づいて 2 次フィボナッチキューブを修正しました。もう 1 つの関連グラフは、各ビット列の最初と最後の位置の両方で 1 ビットを禁止することによってフィボナッチキューブから定義される、頂点数がルーカス数であるグラフであるルーカスキューブです。Dedó 、TorriおよびSalvi (2002) は、フィボナッチキューブとルーカスキューブの両方の彩色特性を調査しました。