|
В дepeвe нa 2014 вepшинax рoвнo три вepшины имeют cтeпeнь 1. Скoлькo вepшин имeют стeпeнь 3? Я уверен, что здесь ответ - 1. Даже пример могу привести Как строго доказать, что ответ 1? задан 16 Ноя '14 18:36 
Leva319 |
|
По крайней мере 1 вершина степени 3 существует. Иначе будет меньше трех висячих вершин, или же больше трех (т.к. после удаления этой вершины останется больше трех компонент связности, и в исходном дереве должно быть больше 3-х висячих вершин). Удалим вершину степени 3. Тогда дерево распадается на 3 связные компоненты, которые в совокупности имеют 6 вершин степени 1. У каждой связной компоненты - как минимум две вершины степени 1. Поэтому каждая компонента связности, полученная после удаления вершины - имеет наипростейший вид ("линейный") - с двумя висячими вершинами. Отсюда ясно, что других вершин степени 3 быть не может. отвечен 16 Ноя '14 18:48 
cartesius Спасибо. И вопрос - Что значит "висячая вершина"?
(16 Ноя '14 20:42)
Leva319
Почему как минимум? Разве не в точности две?
(16 Ноя '14 20:53)
Leva319
Висячая вершина - вершина степени 1. У того, что Вы нарисовали (а это связный граф) - три висячие вершины. То есть может быть и больше.
(16 Ноя '14 20:59)
cartesius
У того, что я нарисовал, если удалить вершину степени три, то останется 2 вершины степени 1, а не 6.
(16 Ноя '14 21:01)
Leva319
Нет, удалить - имеется ввиду "разъединить в этой точке". На Вашей картинке - на 3 части. То есть ребра не удаляются, а дополняются конечной вершиной.
(16 Ноя '14 21:15)
cartesius
Теперь понятно, но я до сих пор не понимаю, почему КАК МИНИМУМ две вершины степени 1 у каждой связной компоненты после удаления вершины степени 3. Разве не в точности?
(16 Ноя '14 21:29)
Leva319
В данном случае - в точности. А вообще у дерева - как минимум 2.
(16 Ноя '14 21:44)
cartesius
показано 5 из 7
показать еще 2
|
Еще вопрос. Я не понял вторую часть доказательства того, что существует по крайне мере 1 вершина степени 3. Как может быть в противном случае БОЛЬШЕ трех висячих вершин?
@Leva319: тут можно рассуждать так. Рассмотрим вершину наибольшей валентности и "подвесим" дерево в этой точке. Тогда из неё расходится, скажем, $%k$% рёбер. По каждому из $%k$% направлений точно есть хотя бы одна висячая вершина. Отсюда ясно, что $%k$% не больше трёх, а также ясно, что если $%k=3$%, то ни в одном из трёх поддеревьев нет дальнейших "ветвлений". Значит, общий вид дерева здесь такой: точка степени 3, и от неё отходят три неразветвлённых пути (вообще говоря, разной длины).