スター (グラフ理論)

スターグラフ（スター）についての概要

スター（星）とは、グラフ理論で重要な役割を果たす特異な構造を持つグラフの一種です。スターグラフは、中心の1つの頂点とその頂点に接続されたk個の葉から成り立っています。これにより、スターは対象の対称性を活かし、通常の木構造と異なる特性を持つため、数学的な観点からも興味深いものとなっています。

スターの特徴

スターの最も基本的な形は、頂点数が3のものです。この特別な形状は「クロー」または「爪」とも呼ばれ、そのシンプルな構造が多くの理論に利用されています。一般的なスターグラフSkにおいては、kが偶数であれば、edge-gracefulという性質を持ち、kが奇数の場合はこれに該当しません。また、スターは自己同型群を持っていることも特徴であり、k次の対称群と結びつきます。

さらに、スターグラフは直径が2であり、1つの頂点の次数が1より大きい連結グラフの一形態とも見なされます。これにより、特にkが大きくなると、スターの持つ性質が強調されることが多いです。

他のグラフとの関連性

スターグラフが持つ重要な性質の一つに、3頂点のスターであるクローが存在します。クローはクローフリーグラフの一例で、このタイプのグラフは誘導部分グラフにクローを含まないため、特定のグラフ同型定理において例外的な扱いを受けます。また、スターは木の特別なケースであるため、プリューファー列（ノードのリスト）で表現でき、この列では中心の頂点をk-1回並べることが特徴です。

グラフの不変量においてもスターは使われ、たとえばスターの「樹化数」という属性は、ある森林に含まれる木を全てスターに分割した際の最小の森の数として定義されます。「スター彩色数」とは、二色で彩色した時に、同じ色の頂点が全てスターとなるための色数を表しています。さらに、「分枝幅が1である」という性質は、連結した分枝がすべてスターの構造を持つことを意味します。

スターの応用

クローのいただ点間の距離を集計したものは、ユークリッド空間における等長写像を持たない有限距離空間の一例を構成します。加えて、分散コンピューティングにおけるネットワーク・トポロジーもスターグラフを用いてモデル化され、非常に重要な概念となっています。さらに、一定間隔で辺を識別することで形成されるスターの幾何学的な実現は、トロピカル幾何学における局所モデルとして利用され、トロピカル曲線として位置付けられます。

このように、スターグラフは多くの分野において基礎的かつ重要な役割を果たしており、その特異な形状と数学的性質は、今後の研究においても注目されるでしょう。

もう一度検索