Номер 12, страница 8, часть 2 - гдз по алгебре 7-9 класс учебник Высоцкий, Ященко

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

a) б) Рисунок 11

В задаче требуется найти количество цепей (путей) определённой длины от начальной вершины S до концевых вершин (вершин со степенью 1, т.е. "листьев" дерева). Длина цепи определяется количеством рёбер в ней.

Рассмотрим дерево, изображенное на рисунке 11а.

Сколько цепей имеет длину 2?
От вершины S отходят две ветви.

• По левой ветви: проходим одно ребро до промежуточной вершины, от которой отходят два ребра к двум концевым вершинам. Это 2 цепи длины 2.
• По правой ветви: проходим одно ребро до промежуточной вершины, от которой отходит одно ребро к концевой вершине. Это 1 цепь длины 2.

Всего цепей длины 2: $2 + 1 = 3$.

Сколько цепей имеет длину 3?

• На левой ветви все концевые вершины находятся на расстоянии 2 от S, поэтому цепей длины 3 здесь нет.
• На правой ветви от промежуточной вершины на расстоянии 1 от S отходит ребро к другой промежуточной вершине (на расстоянии 2 от S). От этой, в свою очередь, отходят два ребра к двум концевым вершинам. Это 2 цепи длины 3.

Всего цепей длины 3: $0 + 2 = 2$.

Сколько цепей имеет длину 4?
Максимальная длина цепи от вершины S до любой концевой вершины в этом дереве равна 3. Следовательно, цепей длины 4 не существует. Всего цепей длины 4: 0.

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

Рассмотрим дерево, изображенное на рисунке 11б.

Сколько цепей имеет длину 2?
От вершины S отходят две ветви.

• По левой ветви: от промежуточной вершины на расстоянии 1 от S отходят рёбра к двум концевым вершинам. Это 2 цепи длины 2.
• По правой ветви: от промежуточной вершины на расстоянии 1 от S отходит ребро к одной концевой вершине. Это 1 цепь длины 2.

Всего цепей длины 2: $2 + 1 = 3$.

Сколько цепей имеет длину 3?

• По левой ветви: от промежуточной вершины на расстоянии 2 от S отходят рёбра к двум концевым вершинам. Это 2 цепи длины 3.
• По правой ветви: от промежуточной вершины на расстоянии 2 от S отходят рёбра к двум концевым вершинам. Это 2 цепи длины 3.

Всего цепей длины 3: $2 + 2 = 4$.

Сколько цепей имеет длину 4?

• По левой ветви: от промежуточной вершины на расстоянии 3 от S отходят рёбра к двум концевым вершинам. Это 2 цепи длины 4.
• По правой ветви: максимальная длина цепи до концевой вершины равна 3. Цепей длины 4 здесь нет.

Всего цепей длины 4: $2 + 0 = 2$.

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