Граф - упорядоченная пара G =<V;E>, где V - непустое конечное множество (элементы V- вершины графа); E- конечное мультимножество неупорядоченных пар элементов V необязательно различных) (элементы E- ребра).
Граф, не содержащий циклов, называют ациклическим графом, или лесом. Заметим, что в ациклическом графе отсутствуют петли и кратные ребра, в силу чего он является простым графом. Дерево - это связный ациклический граф. Таким образом, компоненты связности леса являются деревьями, т.е. лес - дизъюнктное объединение деревьев.
Теорема. Граф является лесом тогда и только тогда, когда каждое ребро графа - мост.
Теорема. Дерево с n вершинами содержит n - 1 ребро.
Следствие 1. Пусть в лесе n вершин, m ребер и k компонент связности. Тогда m = n - k.
Следствие 2. Если в лесе число ребер на 1 меньше числа вершин, то этот лес является деревом. Следствие 3. В дереве, которое содержит по меньшей мере две вершины, не менее двух висячих вершин. Следствие 4. В лесе, содержащем хотя бы одно ребро, не менее двух висячих вершин.
Теорема 15. Пусть в связном графе число ребер на 1 меньше числа вершин. Тогда этот граф - дерево. Теорема 16. Граф является деревом тогда и только тогда, когда любые две его вершины соединены ровно одной простой цепью. Теорема 17. Лес является деревом в том и только в том случае, когда добавление любого ребра приводит к образованию ровно одного цикла. Обозначим через Pn число помеченных деревьев с n вершинами.