Граф-звезда

Граф-звезда S₇

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

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

• S_k — это полный двудольный граф K_1,k..
• дерево с одним внутренним узлом и $k$ листьями. Кроме того, некоторые авторы определяют $S_k$ как дерево порядка $k$ с максимальным диаметром 2; тогда граф-звезда $k>2$ имеет $k-1$ листьев.

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

Граф-звезда S_k обладает Шаблон:Не переведено 3, когда k чётно, и не обладает, если k нечётно.

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

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

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

Граф-звезда является особым видом дерева. Как и любое дерево, граф-звезда может быть закодирован при помощи Шаблон:Не переведено 2; последовательность Прюфера для графа-звезды K_1,k состоит из k − 1 копии центральной вершины.

Графы S₃, S₄, S₅ и S₆.

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

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

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