Граф-звезда — связный граф в котором всё рёбра исходят из одной вершины. Звезда с ${\displaystyle k+1}$ вершиной обычно обозначается ${\displaystyle S_{k}}$ , при этом ${\displaystyle k}$ называют порядком звезды.

Другие определения

• S _k — это полный двудольный граф K _{1, k} . .

• дерево с одним внутренним узлом и ${\displaystyle k}$ листьями. Кроме того, некоторые авторы определяют ${\displaystyle S_{k}}$ как дерево порядка ${\displaystyle k}$ с максимальным диаметром 2; тогда граф-звезда ${\displaystyle k>2}$ имеет ${\displaystyle k-1}$ листьев.

Граф-звезда с тремя ребрами называется лапа , клешня или тринога .

Граф-звезда S _k обладает (англ.) ( , когда k чётно, и не обладает, если k нечётно.

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

Отношение к другим видам графов

Графы-клешни важны в определении графов без клешней , графов, которые не имеют подграфов, являющихся клешнями .

Граф-звезда является особым видом дерева . Как и любое дерево , граф-звезда может быть закодирован при помощи ( англ. ); последовательность Прюфера для графа-звезды K _{1, k} состоит из k − 1 копии центральной вершины .

Другие применения

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

Топология компьютерной сети «Звезда» , построенная в виде графа-звезды, играет важную роль в распределённых вычислениях .

Примечания