Граф-звезда

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск
Граф-звезда S7

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

Граф-звезда с тремя ребрами называется лапа или клешня [1] (англ. claw).

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

Отношение к другим видам графов[править | править вики-текст]

Claw графы заметны в определении графов без клешней, графов, которые не имеют подграфов, являющихся claw графами[2][3].

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

Графы S3, S4, S5 и S6.

Другие применения[править | править вики-текст]

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

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

Примечания[править | править вики-текст]

  1. В.А. Евстигнеев, В.Н. Касьянов Словарь по графам в информатике. — Новосибирск. — (Конструирование и оптимизация программ). — ISBN 978-591124-036-3
  2. 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 .
  3. Chudnovsky, Maria & Seymour, Paul (2005), "The structure of claw-free graphs", «Surveys in combinatorics 2005», vol. 327, London Math. Soc. Lecture Note Ser., Cambridge: Cambridge Univ. Press, сс. 153–171, <http://www.columbia.edu/~mc2775/claws_survey.pdf> .
  4. 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», Morgan Kaufmann, сс. 343–350, <http://www.ads.tuwien.ac.at/publications/bib/pdf/gottlieb-01.pdf> .
  5. Linial, Nathan (2002), "Finite metric spaces–combinatorics, geometry and algorithms", «Proc. International Congress of Mathematicians, Beijing», vol. 3, сс. 573–586