Звезда (теория графов) - Star (graph theory)
| Звезда | |
|---|---|
 Звезда S 7 . (Некоторые авторы индексируют это как S 8. )
| |
| Вершины | к + 1 |
| Края | k |
| Диаметр | 2 |
| Обхват | ∞ |
| Хроматическое число | 2 |
| Хроматический индекс | k |
| Характеристики |
Гранично-транзитивное дерево Единичное расстояние Двудольное |
| Обозначение | S k |
| Таблица графиков и параметров | |
В теории графов , А звезда S к является полный двудольный граф K 1, K : а дерево с одним внутренним узлом и K листьев (но без внутренних узлов и K + 1 листьев , когда к ≤ 1). В качестве альтернативы некоторые авторы определяют S k как дерево порядка k с максимальным диаметром 2; в этом случае звезда с k > 2 имеет k - 1 лист.
Звезда с 3-мя гранями называется клешней .
Звезда S к является краевой изящным , когда к четно и не тогда , когда к нечетно. Это реберно-транзитивный граф спичек , имеющий диаметр 2 (когда k > 1), обхват ∞ (у него нет циклов), хроматический индекс k и хроматическое число 2 (когда k > 0). Кроме того, звезда имеет большую группу автоморфизмов, а именно симметрическую группу из k букв.
Звезды также можно описать как единственные связные графы, в которых не более одной вершины имеет степень больше единицы.
Отношение к другим семействам графов
Когти примечательны в определении графов без клешней, графов , которые не имеют клешней в качестве индуцированного подграфа . Они также являются одним из исключительных случаев теоремы об изоморфизме графов Уитни : в общем случае графы с изоморфными линейными графами сами изоморфны, за исключением клешни и треугольника K 3 .
Звезда - это особый вид дерева . Как и в случае с любым деревом, звезды могут быть закодированы последовательностью Прюфера ; последовательность Прюфера для звезды K 1, k состоит из k - 1 копии центральной вершины.
Несколько инвариантов графов определены в терминах звезд. Звездная древовидность - это минимальное количество лесов, на которые граф можно разделить так, чтобы каждое дерево в каждом лесу было звездой, а звездное хроматическое число графа - это минимальное количество цветов, необходимых для окраски его вершин таким образом, чтобы каждые два цветовых класса вместе образуют подграф, в котором все связанные компоненты являются звездами. Графики ширины ветвления 1 - это в точности графы, в которых каждый компонент связности представляет собой звезду.
Другие приложения
Набор расстояний между вершинами когтя представляет собой пример конечного метрического пространства, которое не может быть изометрически вложено в евклидово пространство любого измерения.
Звездой сети , А компьютерная сеть по образцу звезды графика, играет важную роль в распределенных вычислений .
Геометрическая реализация звездного графа, образованная путем отождествления ребер с интервалами некоторой фиксированной длины, используется в качестве локальной модели кривых в тропической геометрии . Тропическая кривая определяется как метрическое пространство, локально изоморфное звездному метрическому графу.