Дървета, техните характеристики, рамки (скелети)

Определение: Дървото е свързана графика, която няма цикли. Гора - много дървета.

Определение: Ръб e в графика G се нарича цикличен, ако принадлежи към някакъв цикъл на графика G, а в противен случай ацикличен. Графика G е ациклична, ако всеки от нейните ръбове е ацикличен. (G - няма цикли.)

Коментирайте: когато цикличен ръб е премахнат от свързана графика, графиката остава свързана; когато ацикличен ръб е премахнат, той остава изключен. Всеки компонент на горната свързаност е дърво. Нека G е свързана графика, след това изявленията за следствие са еквивалентни.
1) Графика G е дърво.
2) Графика G - няма цикли.
3) Графика G няма циклични ръбове.
4) Всички ръбове на графиката G са ациклични.

---