1. Рассмотрите рисунок: а) Сколько концевых вершин имеет граф? б) Какую максимальную длину имеют цепи в этом графе?

Решение:

• а) Концевые вершины графа - это вершины, из которых выходит только одно ребро. Подсчитаем количество таких вершин на рисунке: их 7.
• б) Длина цепи в графе - это количество ребер в этой цепи. Максимальная длина цепи в данном графе равна 3 (например, от верхней вершины до любой из крайних нижних вершин).