Граф-звезда (Ijgs-[fy[;g)

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

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

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

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

Граф-звезда S_k обладает изяществом вершин^[англ.], когда k чётно, и не обладает, если k нечётно.

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

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

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

Граф-звезда является особым видом дерева. Как и любое дерево, граф-звезда может быть закодирован при помощи последовательности Прюфера (англ. Prüfer sequence); последовательность Прюфера для графа-звезды K_1,k состоит из k − 1 копии центральной вершины^[5].

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

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

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

Примечания

↑ Публичные учебные материалы ВГУЭС (неопр.). Дата обращения: 3 октября 2016. Архивировано 5 октября 2016 года.
↑ В.А. Евстигнеев, В.Н. Касьянов. Словарь по графам в информатике. — Новосибирск. — (Конструирование и оптимизация программ). — ISBN 978-591124-036-3.
↑ Faudree, Ralph; Flandrin, Evelyne; Ryjáček, Zdeněk (1997), "Claw-free graphs — A survey", Discrete Mathematics, 164 (1—3): 87—147, doi:10.1016/S0012-365X(96)00045-3, MR 1432221.
↑ Chudnovsky, Maria; Seymour, Paul (2005), "The structure of claw-free graphs", Surveys in combinatorics 2005 (PDF), London Math. Soc. Lecture Note Ser., vol. 327, Cambridge: Cambridge Univ. Press, pp. 153—171, MR 2187738, Архивировано (PDF) 23 октября 2012, Дата обращения: 4 января 2013 Источник (неопр.). Дата обращения: 4 января 2013. Архивировано 23 октября 2012 года..
↑ Gottlieb, J.; Julstrom, B. A.; Rothlauf, F.; Raidl, G. R. (2001), "Prüfer numbers: A poor representation of spanning trees for evolutionary search", Proc. Genetic and Evolutionary Computation Conference (PDF), Morgan Kaufmann, pp. 343—350, Архивировано (PDF) 26 сентября 2006, Дата обращения: 4 января 2013 Источник (неопр.). Дата обращения: 4 января 2013. Архивировано из оригинала 26 сентября 2006 года..
↑ Linial, Nathan (2002), "Finite metric spaces–combinatorics, geometry and algorithms", Proc. International Congress of Mathematicians, Beijing, vol. 3, pp. 573—586, arXiv:math/0304466

[1] Публичные учебные материалы ВГУЭС (неопр.). Дата обращения: 3 октября 2016. Архивировано 5 октября 2016 года.

[2] В.А. Евстигнеев, В.Н. Касьянов. Словарь по графам в информатике. — Новосибирск. — (Конструирование и оптимизация программ). — ISBN 978-591124-036-3.

[3] Faudree, Ralph; Flandrin, Evelyne; Ryjáček, Zdeněk (1997), "Claw-free graphs — A survey", Discrete Mathematics, 164 (1—3): 87—147, doi:10.1016/S0012-365X(96)00045-3, MR 1432221.

[4] Chudnovsky, Maria; Seymour, Paul (2005), "The structure of claw-free graphs", Surveys in combinatorics 2005 (PDF), London Math. Soc. Lecture Note Ser., vol. 327, Cambridge: Cambridge Univ. Press, pp. 153—171, MR 2187738, Архивировано (PDF) 23 октября 2012, Дата обращения: 4 января 2013 Источник (неопр.). Дата обращения: 4 января 2013. Архивировано 23 октября 2012 года..

[5] Gottlieb, J.; Julstrom, B. A.; Rothlauf, F.; Raidl, G. R. (2001), "Prüfer numbers: A poor representation of spanning trees for evolutionary search", Proc. Genetic and Evolutionary Computation Conference (PDF), Morgan Kaufmann, pp. 343—350, Архивировано (PDF) 26 сентября 2006, Дата обращения: 4 января 2013 Источник (неопр.). Дата обращения: 4 января 2013. Архивировано из оригинала 26 сентября 2006 года..

[6] Linial, Nathan (2002), "Finite metric spaces–combinatorics, geometry and algorithms", Proc. International Congress of Mathematicians, Beijing, vol. 3, pp. 573—586, arXiv:math/0304466

[1]

[2]

[3]

[4]

[5]

[6]