Граф-звезда: различия между версиями

В [[Теория графов|теории графов]] '''граф-звезда''' ''S''_k — это полный [[Двудольный граф|двудольный граф]] ''K''_1,''k'': [[Дерево (теория графов)|дерево]] с одним внутренним узлом и ''k'' листьями. Кроме того, некоторые авторы определяют ''S''_k как дерево порядка ''k'' с максимальным диаметром — 2; откуда граф-звезда ''k'' > 2 имеет ''k'' — 1 листьев.

Граф-звезда ''S''_k называется '''изящным''', когда ''k'' четно и не является таковым при нечетных ''k''. Граф-звезда также может быть описан как [[связный граф]], в котором не более одной вершины может имеет [[Степень вершины (теория графов)|степень]] больше единицы.