Рассмотри изображённое на рисунке дерево и определи, сколько цепей, соединяющих начальную вершину S с концевыми, имеют длину 2
Привет! Давай посмотрим на рисунок и решим задачу вместе.
Тебе нужно найти количество цепей (путей), начинающихся в вершине S и заканчивающихся на какой-либо концевой вершине, длина которых равна двум. Под длиной пути в графе понимается количество рёбер, составляющих этот путь.
Чтобы решить задачу, давай посмотрим на каждое ребро, выходящее из начальной вершины S и увидим, сколько раз оно ведет к концевой вершине через ровно одно ребро.
Теперь пройдемся по каждому ребру и посчитаем:
Слева от вершины S три ребра идут напрямую к конечным вершинам. То есть у нас уже есть три пути длины 1, до концевых вершин.
Справа от вершины S есть одно ребро, которое далее ветвится на два ребра, идущих к концевым вершинам. Это еще два пути длины 2.
Справее от предыдущего ребра также одно ребро, ведущее к двум другим рёбрам. Считаем их: плюс два пути длины 2.
Самое правое ребро, так же ветвится на два ребра, ведущих к концевым вершинам. Добавляем еще два пути.
Если мы сложим количество путей, идущих к конечным вершинам напрямую (3 пути) с теми, что идут
