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

Решение:

а) Деревьями являются графы, в которых нет циклов и они связные. Из представленных графов деревьями являются графы 1 и 3.

б) Цепями (или простыми путями) являются графы, в которых нет циклов и степень каждой вершины не более 2. Из представленных графов цепями являются графы 1, 2 и 3.

Ответ: а) 1, 3; б) 1, 2, 3.