Вопрос 10. Деревья. Определения.
Опр.: Связный ациклический граф наз. деревом.
Ациклический граф это граф без циклов.
Опр.: Ациклический несвязный граф наз. лесом.
Теор.: Следующие утверждения эквивалентны:
1) Граф G – дерево.
2) Граф G связный и m=n-1
3) G ациклический и m=n-1
4) Для любых двух вершин u, v принадлежащих X существует (u,v)-цепь.
5) Граф G ациклический и при добавлении ребра между двумя несмежными вершинами образуется граф, в котором существует единственный цикл (G+e сущ. цикл).