1 Какие из графов на рисунке 5 являются деревьями? a) 6) 8) г) д) Рисунок 5

Деревом называется граф, не содержащий циклов и петель, то есть любые две вершины которого соединены ровно одним путём.

На рисунке 5 деревьями являются графы:

• г)
• д)

Графы а) и б) не являются деревьями, так как содержат циклы.

Граф в) не является деревом, так как содержит петли.

Ответ: г) и д)