Звезда (теория графов)

Звезда
Звезда S 7. (Некоторые авторы индексируют это как S 8.)
Вершины	k + 1
Ребра	k
Диаметр	минимум (2, k)
Обхват	∞
Хроматическое число	минимум ( 2, k + 1)
Хроматический индекс	k
Свойства	Гранично-транзитивный. Дерево. Единичное расстояние. Двудольное
Обозначение	Sk
Таблица графиков и параметров

В теория графов, звезда Sk- это полный двудольный граф K 1, k : дерево с одним внутренним узел и k листьев (но без внутренних узлов и k + 1 листьев, когда k ≤ 1). В качестве альтернативы, некоторые авторы определяют S k как дерево порядка k с максимумом диаметр 2; в этом случае звезда с k>2 имеет k - 1 лист.

Звезда с 3 ребрами называется клешней .

Звезда S k является изящным по ребрам, когда k четно, а не когда k нечетно. Это переходный по краю граф со спичками и имеет диаметр 2 ( когда k>1), обхват ∞ (не имеет циклов), хроматический индекс k и хроматическое число 2 (когда k>0). звезда h как большая группа автоморфизмов, а именно симметрическая группа на k букв.

Звезды также можно описать как единственные связные графы, в которых не более одной вершины имеет степень больше единицы.

Когти примечательны в определении графов без клешней, графов, которые не имеют когтей в качестве индуцированного подграфа. Они также являются одним из исключительных случаев теоремы об изоморфизме графов Уитни : в общем случае графы с изоморфными линейными графами сами изоморфны, за исключением коготь и треугольник K 3.

Звезда - это особый вид дерева. Как и в случае с любым деревом, звезды могут быть закодированы с помощью последовательности Прюфера ; последовательность Прюфера для звезды K 1, k состоит из k - 1 копий центральной вершины.

Несколько инвариантов графа определены в терминах звезд. Звездная древовидность - это минимальное количество лесов, на которые можно разбить граф, так что каждое дерево в каждом лесу представляет собой звезду, а звездное хроматическое число графа является минимальным числом. цветов, необходимых для раскраски его вершин таким образом, чтобы каждые два класса цветов вместе образовывали подграф, в котором все связанные компоненты являются звездами. Графики ширины ветвления 1 - это в точности графики, в которых каждый компонент связности представляет собой звезду.

Набор расстояний между вершинами когтя представляет собой пример конечного метрического пространства, которое не может быть встроено изометрически в евклидово пространство любого измерения.

звездная сеть, компьютерная сеть, смоделированная по звездному графу, является важно в распределенных вычислениях.

Геометрическая реализация звездного графа, образованная путем идентификации ребер с интервалами некоторой фиксированной длины, используется в качестве локальной модели кривых в тропической геометрии. Тропическая кривая определяется как метрическое пространство, локально изоморфное звездному метрическому графу.

Викискладе есть материалы, связанные с Звездными графиками.