На рисунке 11 показано дерево. Рассмотрите цепи, соединяющие начальную вершину S с концевыми. Сколько таких цепей имеют длину 2; длину 3; длинк 4?

Давай попробуем вместе разобраться с этой задачей.

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

Теперь нам нужно посчитать количество путей от вершины S до всех остальных вершин, имеющих длину 2, 3 и 4. Длина пути — это количество рёбер, которое нам нужно пройти, чтобы добраться от одной вершины к другой.

На рисунке а) очевидно, что вершины, находящиеся непосредственно рядом с S, связаны с ней путём длины 1. Чтобы найти пути длины 2, нужно рассмотреть вершины на один уровень ниже. Аналогично с путями длины 3 и 4 — это будут соответственно вершины через два и через три "уровня".

Итак, посмотрим на рисунок а):

1. Пути длины 2: от S можем пойти к любой из ближайших к ней вершин (их три), и от каждой из них можем идти к вершинам следующего уровня (для каждой по две). Итого получаем 3 * 2 = 6 путей длины 2.
2. Пути длины 3: таких путей нет, так как дальше второго уровня вершин дерево не идёт.
3. Пути длины 4: также их нет по той же причине, что и для пут