Граф-звезда: различия между версиями
| [непроверенная версия] | [непроверенная версия] |
EmausBot (обсуждение | вклад) м Перемещение 5 интервики-ссылок в Викиданные (d:Q2589168) |
Dulat K (обсуждение | вклад) мНет описания правки |
||
| Строка 1: | Строка 1: | ||
[[Файл:Star network 7.svg|180px|thumb|right|Граф-звезда ''S<sub>7</sub>'']] |
[[Файл:Star network 7.svg|180px|thumb|right|Граф-звезда ''S<sub>7</sub>'']] |
||
В [[Теория графов|теории графов]], a '''граф-звезда''' ''S''<sub>k</sub> — это полный [[Двудольный граф|двудольный граф]] ''K''<sub>1,''k''</sub>: [[Дерево (теория графов)|дерево]] с одним внутренним узлом и ''k'' листьями. Кроме того, некоторые авторы определяют ''S''<sub>k</sub> как дерево порядка ''k'' с максимальным диаметром - 2; откуда граф-звезда ''k'' > 2 имеет ''k'' |
В [[Теория графов|теории графов]], a '''граф-звезда''' ''S''<sub>k</sub> — это полный [[Двудольный граф|двудольный граф]] ''K''<sub>1,''k''</sub>: [[Дерево (теория графов)|дерево]] с одним внутренним узлом и ''k'' листьями. Кроме того, некоторые авторы определяют ''S''<sub>k</sub> как дерево порядка ''k'' с максимальным диаметром - 2; откуда граф-звезда ''k'' > 2 имеет ''k'' — 1 листьев. |
||
Граф-звезда с тремя ребрами называется ''лапа'' ({{lang-en|claw}}). |
Граф-звезда с тремя ребрами называется ''лапа'' ({{lang-en|claw}}). |
||
Версия от 06:16, 2 апреля 2013
В теории графов, a граф-звезда Sk — это полный двудольный граф K1,k: дерево с одним внутренним узлом и k листьями. Кроме того, некоторые авторы определяют Sk как дерево порядка k с максимальным диаметром - 2; откуда граф-звезда k > 2 имеет k — 1 листьев.
Граф-звезда с тремя ребрами называется лапа (англ. claw).
Граф-звезда Sk называется изящным, когда k четно и не является таковым при нечетных k. Граф-звезда также может быть описан как связный граф, в котором не более одной вершины может имеет степень больше единицы.
Отношение к другим видам графов
Claw графы заметны в определении claw-free графов (англ. claw-free graphs), графов, которые не имеют подграфов, являющихся claw графами[1][2].
Граф-звезда является особым видом дерева. Как и любое дерево, граф-звезда может быть закодирован при помощи Prüfer последовательности (англ. Prüfer sequence); Prüfer последовательность для графа-звезды K1,k состоит из k − 1 копий центральной вершины[3].
Другие применения
Набор расстояний между вершинами claw-графа представляет собой пример конечного метрического пространства, которое не может быть встроено изометрически в евклидово пространство любой размерности[4].
"Звезда", компьютерная сеть, построенная по графу-звезде, играет важную роль в распределенных вычислениях.
Примечания
- ↑ 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.
- ↑ 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.
- ↑ Linial, Nathan (2002), "Finite metric spaces–combinatorics, geometry and algorithms", Proc. International Congress of Mathematicians, Beijing, vol. 3, pp. 573—586, arXiv:math/0304466
 | Для улучшения этой статьи желательно:
|