Открыть главное меню

Изменения

3 байта убрано, 6 лет назад
Нет описания правки
[[Файл: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''  — 1 листьев.
 
Граф-звезда с тремя ребрами называется ''лапа'' ({{lang-en|claw}}).
</ref>.
 
Граф-звезда является особым видом [[Дерево (теория графов)|дерева]]. Как и любое [[Дерево (теория графов)|дерево]], граф-звезда может быть закодирован при помощи {{не переведено 2|Prüfer sequence|Prüfer последовательности||Prüfer sequence}}; Prüfer последовательность для графа-звезды ''K''<sub>1,''k''</sub> состоит из ''k''&nbsp;&minus;&nbsp; − 1 копий центральной вершины<ref>{{citation
| last1 = Gottlieb | first1 = J.
| last2 = Julstrom | first2 = B. A.
</ref>.
 
[[ImageФайл:Star graphs.svg|thumb|600px|center|Графы ''S''<sub>3</sub>, ''S''<sub>4</sub>, ''S''<sub>5</sub> и ''S''<sub>6</sub>.]]
 
== Другие применения ==
</ref>.
 
[[Звезда (топология компьютерной сети)|"«Звезда"»]], компьютерная сеть, построенная по графу-звезде, играет важную роль в распределенных вычислениях.
 
== Примечания ==