Граф-звезда: различия между версиями
| [отпатрулированная версия] | [отпатрулированная версия] |
Komap (обсуждение | вклад) →Преамбула: орфография |
Komap (обсуждение | вклад) убрал {{rq|stub|checktranslate}} - вроде нормально |
||
| Строка 74: | Строка 74: | ||
</ref>. |
</ref>. |
||
Топология компьютерной сети [[Звезда (топология компьютерной сети)|«Звезда»]], построенная |
Топология компьютерной сети [[Звезда (топология компьютерной сети)|«Звезда»]], построенная в виде графа-звезды, играет важную роль в [[Распределённые вычисления|распределенных вычислениях]]. |
||
== Примечания == |
== Примечания == |
||
{{примечания}} |
{{примечания}} |
||
{{rq|stub|checktranslate}} |
|||
[[Категория:Деревья (структуры данных)]] |
[[Категория:Деревья (структуры данных)]] |
||
[[Категория:Граф (математика)]] |
[[Категория:Граф (математика)]] |
||
Версия от 15:45, 3 октября 2016
В теории графов граф-звезда Sk — это полный двудольный граф K1,k. Граф вида K1,k. называется звездой порядка k[1].
Другое определение: дерево с одним внутренним узлом и k листьями. Кроме того, некоторые авторы определяют Sk как дерево порядка k с максимальным диаметром 2; тогда граф-звезда k > 2 имеет k — 1 листьев.
Граф-звезда с тремя ребрами называется лапа или клешня[2] (англ. claw).
Граф-звезда Sk обладает изящество вершин, когда k четно, и не обладает, если к нечетно.
Граф-звезда также может быть описан как связный граф, в котором не более одной вершины имеет степень больше единицы.
Отношение к другим видам графов
Графы-клешни важны в определении графов без клешней, графов, которые не имеют подграфов, являющихся клепнями[3][4].
Граф-звезда является особым видом дерева. Как и любое дерево, граф-звезда может быть закодирован при помощи последовательность прюфера (англ. Prüfer sequence); Последовательность прюфера для графа-звезды K1,k состоит из k − 1 копий центральной вершины[5].
Другие применения
Множество расстояний между вершинами графа-клешни представляет собой пример метрического пространства, которое не может быть встроено изометрически в евклидово пространство любой размерности[6].
Топология компьютерной сети «Звезда», построенная в виде графа-звезды, играет важную роль в распределенных вычислениях.
Примечания
- ↑ Публичные учебные материалы ВГУЭС
- ↑ В.А. Евстигнеев, В.Н. Касьянов. Словарь по графам в информатике. — Новосибирск. — (Конструирование и оптимизация программ). — 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.
- ↑ 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