星 (图论)

星 (图论)
星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₆四个星图。

其他应用

爪的顶点之间的距离集提供了一个有限度量空间的例子，这个有限度量空间不能被等距嵌入任何维度的欧氏空间。

星型网是一种以星型图为模型的计算机网络，在分布式计算中占有重要地位。

利用星图的一种几何实现方法，即用一定长度的间隔来识别边缘，是热带几何中曲线图常用的局部模型。热带曲线被定义为一个局部同构于星形度量图的度量空间。