Меню Главная Случайная статья Настройки Граф-звезда Материал из https://ru.wikipedia.org Граф-звезда — связный граф в котором всё рёбра исходят из одной вершины. Звезда с ${\displaystyle k+1}$ вершиной обычно обозначается ${\displaystyle S_{k}}$, при этом ${\displaystyle k}$ называют порядком звезды. Содержание 1 Другие определения 2 Отношение к другим видам графов 3 Другие применения 4 Примечания Другие определения Sk — это полный двудольный граф K1,k.[1]. дерево с одним внутренним узлом и ${\displaystyle k}$ листьями. Кроме того, некоторые авторы определяют ${\displaystyle S_{k}}$ как дерево порядка ${\displaystyle k}$ с максимальным диаметром 2; тогда граф-звезда ${\displaystyle k>2}$ имеет ${\displaystyle k-1}$ листьев. Граф-звезда с тремя ребрами называется лапа, клешня или тринога [2]. Граф-звезда Sk обладает изяществом вершин[англ.], когда k чётно, и не обладает, если k нечётно. Граф-звезда также может быть описан как связный граф, в котором не более одной вершины имеет степень больше единицы. Отношение к другим видам графов Графы-клешни важны в определении графов без клешней, графов, которые не имеют подграфов, являющихся клешнями[3][4]. Граф-звезда является особым видом дерева. Как и любое дерево, граф-звезда может быть закодирован при помощи последовательности Прюфера (англ. Prfer sequence); последовательность Прюфера для графа-звезды K1,k состоит из k 1 копии центральной вершины[5]. Другие применения Множество расстояний между вершинами графа-клешни представляет собой пример метрического пространства, которое не может быть встроено изометрически в евклидово пространство любой размерности[6]. Топология компьютерной сети «Звезда», построенная в виде графа-звезды, играет важную роль в распределённых вычислениях. Примечания Публичные учебные материалы ВГУЭС  (неопр.). Дата обращения: 3 октября 2016. Архивировано 5 октября 2016 года. В.А. Евстигнеев, В.Н. Касьянов. Словарь по графам в информатике. — Новосибирск. — (Конструирование и оптимизация программ). — ISBN 978-591124-036-3.