Задача 1.(У) Какие из графов, изображённые на рисунке являются деревьями.

Решение:

Дерево в теории графов — это связный неориентированный граф без циклов.

• а) Этот граф имеет цикл (например, А-Б-В-Г-Д-Е-А). Следовательно, это не дерево.
• б) Этот граф также содержит циклы. Например, если соединить точки, образующие два треугольника, то это будет цикл. Следовательно, это не дерево.
• в) Этот граф является связным и не содержит циклов. Это дерево.
• г) Этот граф также является связным и не содержит циклов. Это дерево.
• д) Этот граф содержит цикл (центральная точка связана с несколькими точками, которые, в свою очередь, связаны друг с другом, образуя круг). Следовательно, это не дерево.

Ответ: Графы в) и г) являются деревьями.