Какие графы являются деревьями

Чтобы понять, какие графы являются деревьями, необходимо проверить два основных условия: граф должен быть связным и не содержать циклов. Деревом называется любой связный ациклический граф. В таком графе между любыми двумя вершинами существует ровно один простой путь. Если связный граф с $n$ вершинами имеет ровно $n - 1$ ребер, то такие графы являются деревьями по всему определению.

$|E| = |V| - 1$

Разбор по случаям

Примеры

Проверка графа на дерево по числу ребер. Задан связный граф, содержащий $V = 6$ вершин и $E = 5$ ребер. Проверим критерий дерева. Для связного графа равенство $E = V - 1$ является необходимым и достаточным условием отсутствия циклов. Подставим значения: $5 = 6 - 1$, что дает верное равенство $5 = 5$. Следовательно, данный связный граф не имеет циклов и является деревом.

Определение количества ребер в лесе. Задан граф без циклов, имеющий $V = 10$ вершин и состоящий из $k = 3$ компонент связности. Каждая компонента представляет собой отдельное дерево. Число ребер в каждой компоненте равно $V_i - 1$. Общее количество ребер вычисляется по формуле $E = V - k$. Подставляем данные: $E = 10 - 3 = 7$. Граф содержит ровно 7 ребер.

Частые ошибки

• Считать деревом любой ациклический граф, забывая про обязательное условие связности.
• Путать дерево с произвольным связным графом, в котором могут присутствовать замкнутые циклы.
• Применять формулу $E = V - 1$ к несвязным графам без предварительной проверки количества компонент.

Коротко

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