Рассмотри изображённые на рисунке дерево и определи сколько цепей, соединяющих начальную вершину S с концевыми, имеют длину четыре

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

Нам нужно посчитать, сколько есть цепей длиной четыре, соединяющих начальную вершину S с какой-либо концевой вершиной.

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

1. Из S мы можем пойти влево или направо, рассмотрим сначала левую часть.
2. Идя налево, следующей вершиной будет только одна вершина.
3. Оттуда возможны два пути: к вершине слева или справа.
4. Обе эти вершины имеют по две ветви, ведущие к концевым вершинам.

Следовательно, с левой стороны получается 4 цепи длиной четыре (2 пути от второй вершины, умноженные на 2 завершающих ветви каждой из них).

Теперь рассмотрим правую часть:

1. С вершины S в правую сторону мы можем пойти двумя путями.
2. Один путь ведёт на вершину с тремя ветвями, по которым можно пойти к концевым вершинам, образуя три цепи длиной четыре.
3. Другой путь ведёт к вершине с двумя ветвями, причём одна из них ведёт к концевой вершине напрямую, что даёт ещё одну цепь, а другая сначала ведёт к вершине с двумя концевыми ветвями, добавляя ещё две цепи.

Итак, с правой стороны у нас получается 3 + 1 + 2 = 6 цепей длиной четыре.

Суммируем цепи с обеих сторон, и получаем 4 + 6 = 10 цепей длиной четыре.

Правильный ответ — 10.