Граф-звезда — связный граф в котором все рёбра исходят из одной вершины. Звезда с вершиной обычно обозначается , при этом называют порядком звезды.
Другие определения Sk — это полный двудольный граф K1,k.. дерево с одним внутренним узлом и листьями. Кроме того, некоторые авторы определяют как дерево порядка с максимальным диаметром 2; тогда граф-звезда имеет листьев.
Граф-звезда с тремя ребрами называется лапа, клешня или тринога .
Граф-звезда Sk обладает , когда k чётно, и не обладает, если k нечётно.
Граф-звезда также может быть описан как связный граф, в котором не более одной вершины имеет степень больше единицы.
Отношение к другим видам графов Графы-клешни важны в определении графов без клешней, графов, которые не имеют подграфов, являющихся клешнями. ..
Граф-звезда является особым видом дерева. Как и любое дерево, граф-звезда может быть закодирован при помощи ; последовательность Прюфера для графа-звезды K1,k состоит из k − 1 копии центральной вершины ..
Другие применения Множество расстояний между вершинами графа-клешни представляет собой пример метрического пространства, которое не может быть встроено изометрически в евклидово пространство любой размерности.
Топология компьютерной сети «Звезда», построенная в виде графа-звезды, играет важную роль в распределённых вычислениях.
Примечания
Категория:Деревья (структуры данных) Категория:Граф (математика) Категория:Параметрические семейства графов