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

Решение:

Длина цепи — это количество рёбер (отрезков) в ней.

На рисунке 11:

• Начальная вершина S.
• Концевые вершины — это вершины, у которых степень равна 1.

Цепи длиной 2:

Путь от S до концевой вершины, состоящий из 2 рёбер.

• S → вершина с 3 рёбрами → концевая вершина.
• Таких цепей 3 (по числу ветвей, исходящих из вершины с 3 рёбрами).

Цепи длиной 3:

Путь от S до концевой вершины, состоящий из 3 рёбер.

• S → вершина с 3 рёбрами → вершина с 2 рёбрами → концевая вершина.
• Таких цепей 4 (по числу ветвей, исходящих из вершины с 2 рёбрами).

Цепи длиной 4:

Путь от S до концевой вершины, состоящий из 4 рёбер.

• S → вершина с 3 рёбрами → вершина с 2 рёбрами → другая вершина с 2 рёбрами → концевая вершина.
• Таких цепей 2 (по числу ветвей, исходящих из второй вершины с 2 рёбрами).

Ответ: длиной 2 — 3 цепи; длиной 3 — 4 цепи; длиной 4 — 2 цепи.