Деревья и лес

Граф без циклов называется лесом. Связные компоненты леса называются деревьями.

Связный граф, у которого все ребра ациклические, называется деревом.

· Несвязный граф, компонентами связности которого являются деревья, называется лесом.

· Чтобы простой связный граф был деревом, необходимо и достаточно, чтобы число вершин было больше числа ребер на один.

· Чтобы граф был деревом, необходимо и достаточно, чтобы любые две вершины его соединялись единственным маршрутом.

· Граф будет деревом тогда и только тогда, когда добавление любого нового ребра приводит к появлению ровно одного цикла.

· Удаление любого ребра приводит к несвязному графа

Деревья особенно часто возникают на практике при изображении различных иерархий. Например, популярны генеалогические деревья. На рисунке показано библейское генеалогическое дерево

Теория перечисления графов занимается разработкой методов подсчёта числа неизоморфных графов, обладающих тем или иным свойством. Решены задачи о числе графов, орграфов, связных графов, эйлеровых графов и деревьев, содержащих данное число вершин и рёбер. Однако соответствующие результаты для планарных и гамильтоновых графов не получены.

Теорема Кэли (1889): существует ровно n^n-2 различных помеченных деревьев с n вершинами.