スター (グラフ理論)

スター
葉を7つ持つスター S7（一部の人はこれを S8と表現する)
頂点	k+1
辺	k
直径	min(2, k)
内周	∞
彩色数	min(2, k + 1)
彩色指数	k
特性	頂点推移グラフ 木 (数学) 単位距離グラフ 2部グラフ
表記	Sk

スター もしくは星S_k は、グラフ理論の用語の1つであり、ただ1つの頂点とそれにつながる k 個の葉のみを持つグラフである。また、スターは完全2部グラフ K_1, kでもある。スター S_k を直径が2で次数が k である木とする人も存在し、この場合 2 < k であり葉の数は k-1 である。

頂点が3個の星は特別にクローもしくは爪と呼ぶ。

スター S_k は k が偶数のときには edge-graceful であり、 k が奇数の場合はそうでない。スターは頂点推移グラフであり、 1 < k においてグラフの直径は2であり、内周は ∞ である。また、スターは自己同型群を持つ。すなわち、 k 次の対称群である。

スターは、（最大でも）1つの頂点の次数が1より大きい、連結グラフともいえる。

他のグラフとの関係

頂点数が3のスターであるクローはクローフリーグラフ（誘導部分グラフとしてクローを持たないグラフ）の定義で有名である。また、ハスラー・ホイットニー (Hassler Whitney) のグラフ同型定理（一般的に、グラフ同型な線グラフはクローと三角形グラフ K₃を除き同型である。）の例外の1つでもある。

スターは木の特殊な場合であるため、木と同様にプリューファー列で表すことができ、スター S_k は中心の頂点を k-1 回並べた列となる。

スターの考え方を用いて定義されているグラフ不変量がいくつかある。スターの樹化数は森に含まれる木が全てスターとなるような分割を行った際の最小の森の数として定義されている。スター彩色数は、2つの色グループで彩色した場合、同じ色で接続された頂点グループが全てスターとなる彩色数である。分枝幅が1であるというのは、連結している分枝がそれぞれスターであることと同値である。

スターの例。左から順に、S₃, S₄, S_5, S_6。

その他の用途

クローの頂点間の距離の集合は、任意の次元のユークリッド空間への等長写像を持たない、有限距離空間の一例となる。

星型（スター型）のネットワーク・トポロジーはスターグラフでモデル化され、分散コンピューティングの分野において重要な概念である。

一定の長さの間隔で辺を識別することで形成したスターの幾何学的実現は、トロピカル幾何学の曲線の局所モデルとして使用される。トロピカル曲線は、スター型の距離空間の局所的に同型な距離空間として定義される。