Разделы 
Дополнительно
Задача по математике - 3532
2019-06-12 
$n$ точек соединены непересекающимися отрезками так, что из каждой точки можно пройти в каждую из остальных по этим отрезкам, причем нет таких двух точек, которые соединялись бы двумя разными путями. Докажите, что общее число отрезков равно $n - 1$.
Решение:
Назовем одну из $n$ точек «корнем». Поставим в соответствие каждой из остальных $n - 1$ вершин последний отрезок (единственного по условию) пути, ведущего в эту точку из «корня». Это соответствие между множеством из $n - 1$ вершин и множеством всех отрезков будет взаимно однозначным.
Чтобы сделать это совсем очевидным, удобно расставить на всех отрезках стрелки, ведущие от корня (рис.); тогда в каждую точку, кроме вершины, ведет одна стрелка.
Граф, который рассматривается в этой задаче, называется деревом; мы превратили дерево, выделив в нем одну точку, в корне вое ориентированное дерево.
Задачу можно решить также методом математической индукции.
$n$ точек соединены непересекающимися отрезками так, что из каждой точки можно пройти в каждую из остальных по этим отрезкам, причем нет таких двух точек, которые соединялись бы двумя разными путями. Докажите, что общее число отрезков равно $n - 1$.
Решение:
Назовем одну из $n$ точек «корнем». Поставим в соответствие каждой из остальных $n - 1$ вершин последний отрезок (единственного по условию) пути, ведущего в эту точку из «корня». Это соответствие между множеством из $n - 1$ вершин и множеством всех отрезков будет взаимно однозначным.
Чтобы сделать это совсем очевидным, удобно расставить на всех отрезках стрелки, ведущие от корня (рис.); тогда в каждую точку, кроме вершины, ведет одна стрелка.
Граф, который рассматривается в этой задаче, называется деревом; мы превратили дерево, выделив в нем одну точку, в корне вое ориентированное дерево.
Задачу можно решить также методом математической индукции.
