В теории графов звезда S k — это полный двудольный граф K 1, k : дерево с одним внутренним узлом и k листьями ( но без внутренних узлов и k + 1 листьями, когда k ≤ 1 ). В качестве альтернативы некоторые авторы определяют S k как дерево порядка k с максимальным диаметром 2; в этом случае звезда k > 2 имеет k − 1 листьев.
Звезда с тремя гранями называется клешней .
Звезда S k является рёберно-грациозной , когда k чётное, и не является, когда k нечётное. Это рёберно-транзитивный спичечный граф , имеющий диаметр 2 (когда l > 1 ), обхват ∞ (не имеет циклов), хроматический индекс k и хроматическое число 2 (когда k > 0 ). Кроме того, звезда имеет большую группу автоморфизмов, а именно, симметрическую группу по k буквам.
Звезды также можно описать как единственные связные графы, в которых не более одной вершины имеет степень больше единицы.
Клешни примечательны в определении графов без клешней , графов, которые не имеют клешней в качестве индуцированных подграфов . [1] [2] Они также являются одним из исключительных случаев теоремы Уитни об изоморфизме графов : в общем случае графы с изоморфными линейными графами сами по себе изоморфны, за исключением клешни и треугольника K 3 . [3]
Звезда — это особый вид дерева . Как и любое дерево, звезды могут быть закодированы последовательностью Прюфера ; последовательность Прюфера для звезды K 1, k состоит из k − 1 копий центральной вершины. [4]
Несколько инвариантов графа определяются в терминах звезд. Древовидность звезды — это минимальное количество лесов, на которые граф может быть разделен таким образом, чтобы каждое дерево в каждом лесу было звездой, [5] а хроматическое число звезды графа — это минимальное количество цветов, необходимых для раскраски его вершин таким образом, чтобы каждые два цветовых класса вместе образовывали подграф, в котором все связные компоненты являются звездами. [6] Графы с шириной ветви 1 — это в точности графы, в которых каждый связный компонент является звездой. [7]
Набор расстояний между вершинами клешни представляет собой пример конечного метрического пространства , которое не может быть изометрически вложено в евклидово пространство любой размерности. [8]
Звездообразная сеть — компьютерная сеть , смоделированная по образцу звездообразного графа, играет важную роль в распределенных вычислениях .
Геометрическая реализация звездного графа, образованная путем идентификации ребер с интервалами некоторой фиксированной длины, используется в качестве локальной модели кривых в тропической геометрии . Тропическая кривая определяется как метрическое пространство, локально изоморфное звездообразному метрическому графу.
