Будет ли этот набор степеней вершин графов деревом

@Витaлиk · Регистрация: 25.10.2011

Author24 — интернет-сервис помощи студентам

{3,2,2,2,1,1,1,1,1,1}

Байт · 13.12.2011, 23:24

Сообщение от Витaлиk

{3,2,2,2,1,1,1,1,1,1}

Увы! Даже графом не будет. Сумма степеней вершин = 2*(число ребер) - число четное.

Добавлено через 2 минуты
А у дерева (число вершин) = (число ребер) + 1.
При связности это необходимо и достаточно

@Витaлиk · 14.12.2011, 00:20 **[ТС]**

а среди этих этих есть дерево?
{2,2,2,2,2,2,2,2,2,2}
{1,2,2,2,2,2,2,2,2,1}
{6,6,6,7,4,4,4,5,5,5}
{4,3,6,5,3,6,6,8,7,6}
{4,3,3,6,3,4,5,4,4,4}
??

Байт · 14.12.2011, 11:10

Витaлиk, Подсчитай число ребер, раздели на 2, вычти 1. Ели то, что получится = числу вершин, то да, такое дерево можно построить. Если же нет, тогда прости....

Добавлено через 1 час 0 минут
Ошибочка моя. Не ребер а сумму степеней вершин Вот она-то деленная на 2 и дает число ребер

@Витaлиk 1 / 1 / 0 Регистрация: 25.10.2011 Сообщений: 49
		1
	Будет ли этот набор степеней вершин графов деревом 13.12.2011, 21:23. Показов 3577. Ответов 3 Метки нет (Все метки) {3,2,2,2,1,1,1,1,1,1} 0

Байт Диссидент 27706 / 17322 / 3812 Регистрация: 24.12.2010 Сообщений: 38,979
	13.12.2011, 23:24	2
	Сообщение от Витaлиk {3,2,2,2,1,1,1,1,1,1} Увы! Даже графом не будет. Сумма степеней вершин = 2(число ребер) - число четное. Добавлено через 2 минуты* А у дерева (число вершин) = (число ребер) + 1. При связности это необходимо и достаточно 1

@Витaлиk 1 / 1 / 0 Регистрация: 25.10.2011 Сообщений: 49
	14.12.2011, 00:20 [ТС]	3
	а среди этих этих есть дерево? {2,2,2,2,2,2,2,2,2,2} {1,2,2,2,2,2,2,2,2,1} {6,6,6,7,4,4,4,5,5,5} {4,3,6,5,3,6,6,8,7,6} {4,3,3,6,3,4,5,4,4,4} ?? 0

Байт Диссидент 27706 / 17322 / 3812 Регистрация: 24.12.2010 Сообщений: 38,979
	14.12.2011, 11:10	4
	Сообщение было отмечено как решение Решение Витaлиk, Подсчитай число ребер, раздели на 2, вычти 1. Ели то, что получится = числу вершин, то да, такое дерево можно построить. Если же нет, тогда прости.... Добавлено через 1 час 0 минут Ошибочка моя. Не ребер а сумму степеней вершин Вот она-то деленная на 2 и дает число ребер 3

Будет ли этот набор степеней вершин графов деревом

Решение