Дерево, в котором хотя бы две вершины, подвесили за вершину A . Выберите все гарантированно верные утверждения. Если у вершины, отличной от A , степень k , то она соединена ровно с k вершинами следующего уровня. Если у вершины, отличной от A , степень k , то она соединена ровно с k−1 вершиной следующего уровня. На последнем уровне все вершины висячие. На первом уровне нет висячих вершин. Самый длинный несамопересекающийся путь проходит через A . Количество рёбер в любом пути не больше удвоенного номера последнего уровня. Путь между двумя вершинами одного уровня состоит из чётного числа рёбер.

Разбираемся с деревом, корнем является вершина A. Первый уровень — это дети A; последний уровень — уровень самых глубоких вершин (листья). Пути считаются по количеству рёбер. Гарантированно верные утверждения: 2, 3, 6, 7. Обоснование по каждому пункту и короткие пояснения по остальным (контрпримеры): 1) Утверждение: “Если у вершины, отличной от A, степень k, то она соединена ровно с k вершинами следующего уровня.” - Это неверно. У не–корневой вершины есть одно ребро к_PARENT_, и остаток ребер ведут к детям. Число детей равно k − 1, а не k. Значит 1 неверно. 2) Утверждение: “Если у вершины, отличной от A, степень k, то она соединена ровно с k − 1 вершиной следующего уровня.” - Верно. Как объяснено выше, у не–корневой вершины есть один родитель, остальные k − 1 ребер идут к детям (следующему уровню). 3) Утверждение: “На последнем уровне все вершины висячие.” - Верно. По определению последнего уровня — это вершины без потомков, то есть висячие (листья). 4) Утверждение: “На первом уровне нет висячих вершин.” - Неверно. На первом уровне могут быть листья (например, звездообразное дерево: A — несколько листьев). Следовательно, на первом уровне могут быть висячие вершины. 5) Утверждение: “Самый длинный несамопересекающийся путь проходит через A.” - Неверно. Диаметр дерева (самый длинный простой путь) может лежать entirely внутри одной поддеревьевки потомков A. Например, A имеет одного потомка B, у которого две длинные ветви, длина между кончиками этих ветвей может быть больше любого пути, проходящего через A. Тогда Диаметр не проходит через A. 6) Утверждение: “Количество рёбер в любом пути не больше удвоенного номера последнего уровня.” - Верно. Пусть последний уровень имеет глубину h (то есть максимальная длина пути от A до глубокой вершины равна h). Любой путь между двумя вершинами имеет длину не более глубины одного конца плюс глубина другого конца, то есть ≤ h + h = 2h. Таким образом, он не длиннее 2 × (номер последнего уровня). 7) Утверждение: “Путь между двумя вершинами одного уровня состоит из чётного числа рёбер.” - Верно. Пути между вершинами на одной глубине d имеют длину 2(d − depth(LCA)), что всегда чётно, так как обе составляющие равны d и depth(LCA) — целые. Итого: верны утверждения 2, 3, 6 и 7. Остальные (1, 4, 5) могут быть неверны в общем случае.