В теории графов звездой 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]
Звездная сеть , компьютерная сеть, смоделированная по образцу звездного графа, играет важную роль в распределенных вычислениях .
Геометрическая реализация звездного графа, образованная путем отождествления ребер с интервалами некоторой фиксированной длины, используется в качестве локальной модели кривых в тропической геометрии . Тропическая кривая определяется как метрическое пространство, локально изоморфное звездообразному метрическому графу.
