Деревья (теория графов)

[MestnyBomzh]

Задача: В дереве $2014$ листьев и нет вершин степени $2$. Докажите, что в нем не больше $5000$ врешин.
Я не понимаю, почему вершин не может быть больше, чем $5000$? Например, возьмем два множества вершин $A, |A|=3000$ и $B, |B|=2014$. Теперь каждую вершину из $A$ cоединим с каждой вершиной из $B$. Таким образом, получим $2014$ листьев - все вершины из $B$. Вершин степени $2$ тоже нет, в чем мой контрпример неверен?

[ИСН]

Вы что называете деревом? По-моему, это должен быть граф без циклов.

[MestnyBomzh]

Дерево - связный граф без циклов. А лист - вершина без потомков. Насколько я понимаю, про листья можно говорить только в случае ориентированного дерева

[provincialka]

Хм... А я думала, что "листья" - это вершины степени 1. Ориентированность вроде ни при чем.

[MestnyBomzh]

Тогда у меня есть предположение по поводу максимально возможного количества вершин:
$2014+[\frac{2014}{2}]+[\frac{1007}{2}]+[\frac{503}{2}]+...$

-- 22.12.2014, 15:56 --

О, и последняя вершина хорошей получилось: ее кратность три. Итого у меня получилось: $4019$

[ИСН]

Ну вот. Это же не больше 5000?

[MestnyBomzh]

Но это лишь предположение )

[ИСН]

1. Как количество рёбер связано с количеством вершин?
2. Как оно связано со степенью вершин?

[MestnyBomzh]

1) можно оценить сверху: $\frac{n(n-1)}{2}$.
2) лемма о рукопожатиях

[Pphantom]

MestnyBomzh в сообщении #950744 писал(а):

1) можно оценить сверху: $\frac{n(n-1)}{2}$.

Это очень завышенная оценка. Лучше воспользоваться теоремой Эйлера (ну или просто мысленно "разобрать" дерево, результат получится таким же).

[ИСН]

Не то и не то. Сколько рёбер у дерева из 3 вершин? Неужели 3?
Рукопожатия тут тоже ни к селу ни к городу.

[sqribner48]

Количество $k_T$ висячих вершин дерева определяется количеством $k_B$ вершин ветвления (вершин со степенью 3 и более) по следующему выражению $k_T= k_B +2$.
Таким образом, наибольшее количество вершин ветвления $k_B$ дерева, в котором $k_T= 2014$ и нет вершин степени 2, определяется как $k_B =2012$. При этом все вершины ветвления имеют степень 3, а искомое дерево представляет собой гусеницу, имеющее 4026 вершин $(4026 = 2012 + 2012 +2)$.
Что и требовалось доказать.

[sqribner48]

не успел отредактировать... Вместо первого предложения следует читать:
Общее количество вершин $n$ дерева определяется суммой количества $k_T$ висячих вершин, количества $k_B$ вершин ветвления (вершин со степенью 3 и более) и количества $n_2$ вершин степени 2, то есть $n = k_T + k_B + n_2$.
Ясно, что количество $k_T$ висячих вершин дерева не меньше, чем количество $k_B$ вершин ветвления, то есть $k_T \geqslant k_B +2$.
Нам надо найти граф с максимальным количеством вершин с фиксированным количеством висячих вершин (2014) и без вершин степени 2.
Таким графом будет дерево, которое имеет наибольшее количество вершин ветвления, (имеющих степень 3). В этом графе количество $k_T$ висячих вершин и количество $k_B$ вершин ветвления связаны соотношением $k_T = k_B +2$.
далее по тексту...

[provincialka]

sqribner48, не слишком увлекайтесь конкретикой. ТС должен сам решить.

Но сама идея выделить вершины разного типа и составить для них неравенства - хорошая.

[sqribner48]

provincialka. Да я немного поторопился. Уж больно задача хороша. Надеюсь, что MestnyBomzh не просто прочитает, а сам разберется в этом