Рассмотри созвездия, представленные в виде графов. Определи, какие графы являются деревьями. Выбери верные варианты.

Решение:

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

Рассмотрим представленные графы:

• 1. Лебедь: Граф связный, циклов нет. Это дерево.
• 2. Лев: Граф связный, циклов нет. Это дерево.
• 3. Цефей: Граф связный, циклов нет. Это дерево.
• 4. Рак: Граф связный, циклов нет. Это дерево.
• 5. Лира: Граф связный, но содержит цикл (четырехугольник). Это не дерево.

Ответ: 1, 2, 3, 4.