星 (圖論)

星 (圖論)
星S7 (一些文章認為這是星S8 )。
頂點	k+1
邊	k
直徑	(2, k)的較小值
圍長	∞
色數	(2, k+1)的較小值
色指數	k
屬性	邊傳遞 樹 單位距離 二分

在圖論中，星（英語：Star）S_k屬於完全二分圖K_1,k：是具有一個內部節點和k個葉節點的樹（但當k≤1時，沒有內部節點且由k+1個葉節點）。另外，一些文章將S_k 定義為最大直徑為2的k階樹；在這種情況下，k>2的星具有k−1個葉節點。

有三條邊的星又稱為爪。

當k是偶數時，星S_k是邊優美圖，當k是奇數時則不是。它是一個邊傳遞的火柴杆圖，其直徑為2（當k > 1時），圍長為∞（無循環結構），色指數為k，色數為2（當k > 0時）。此外，星具有較大的自同構群，即k個字母上的對稱群。

星也可以被描述為僅有的最多只有一個頂點的度大於1的連通圖。

與其他圖族的關係

爪在無爪圖的定義中是很明顯的，這種圖的導出子圖沒有任何爪結構。它們也是惠特尼圖同構定理的特例之一：一般來說，同構線圖除了爪與K₃的特例外本身就是同構的。

星是一種特殊的樹。與任何樹一樣，星可以由一個普呂弗序列編碼產生;普呂弗序列為K_k 的星由k − 1個中心點的複製形成。

一些圖常量是用星來定義的。蔭度是一個圖表可以劃分成的最小森林數（森林裏的所有樹都是星）。圖的星色數是對頂點着色所需的最小顏色數，該着色使得任意兩個顏色類在一起均可形成一個所有連接組成部分都是星的子圖。分支寬度為1的圖即是每個連接的組成部分都是星的圖。

S₃, S₄, S₅和S₆四個星圖。

其他應用

爪的頂點之間的距離集提供了一個有限度量空間的例子，這個有限度量空間不能被等距嵌入任何維度的歐氏空間。

星型網是一種以星型圖為模型的計算機網絡，在分佈式計算中佔有重要地位。

利用星圖的一種幾何實現方法，即用一定長度的間隔來識別邊緣，是熱帶幾何中曲線圖常用的局部模型。熱帶曲線被定義為一個局部同構於星形度量圖的度量空間。