2 вариант 1. Рассмотрите рисунок: а) Сколько концевых вершин имеет граф? б) Какую максимальную длину имеют цепи в этом графе? в) Сколько цепей, соединяющих начальную точку с концевой, имеют длину равную 3? 2. Сколько вершин в дереве, в котором 37 ребер? 3. Постройте дерево в котором 7 вершин, причем 4 из них концевые.

1. Рассмотрите рисунок: а) Концевые вершины - это вершины, из которых выходит только одно ребро. На рисунке концевых вершин 6. б) Максимальная длина цепи в этом графе - 3. в) Цепей, соединяющих начальную точку с концевой и имеющих длину 3, - 4. 2. В дереве с n вершинами всегда n-1 ребро. Если в дереве 37 ребер, то количество вершин равно 37 + 1 = 38. 3. Дерево, в котором 7 вершин, причем 4 из них концевые: * / | \ * * * / / \ * * * 1. а) Ответ: 6 2. б) Ответ: 3 3. в) Ответ: 4 4. Ответ: 38 5. Ответ: (см. ASCII-графику в ответе)