Дано: конечный связный граф G с количеством вершин V и количеством рёбер E.
Найти: доказательство того, что граф G является деревом тогда и только тогда, когда V - E = 1.
Решение:
1. Дерево — это связный ацикличный граф. Для дерева с n вершинами существует следующее свойство: число рёбер E в дереве всегда равно V - 1, где V — количество вершин в дереве.
2. Если граф G является деревом, то по определению у него имеется:
- Связность: между любыми двумя вершинами существует путь.
- Ацикличность: в графе нет циклов.
3. Поскольку граф G является деревом и имеет V вершин, тогда по свойству деревьев:
E = V - 1.
4. Мы можем переписать это уравнение как:
V - E = 1.
5. Теперь докажем обратное утверждение. Пусть V - E = 1. Тогда мы имеем:
E = V - 1.
6. Если количество рёбер E равно V - 1, то граф может быть связанным и ацикличным.
7. Чтобы показать, что такой граф обязательно свяжет все вершины и не будет содержать циклов, можно применить принцип индукции:
- При n = 1 (граф с одной вершиной) очевидно, что он является деревом — нет рёбер и есть одна вершина.
- Предположим, что для любого связного графа с k вершинами, где k >= 1, выполняется V - E = 1. Рассмотрим добавление одной вершины к этому графу, соединённой с одной из существующих вершин. Теперь у нас V = k + 1 и E = E + 1. Следовательно,
V - E = (k + 1) - (E + 1) = k - E = 1, что доказывает, что наш граф остаётся деревом и при увеличении числа вершин.
8. Таким образом, если V - E = 1, то граф G является деревом.
Ответ:
Конечный связный граф является деревом тогда и только тогда, когда V - E = 1.