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