Дано: граф G без циклов с количеством вершин V и количеством рёбер E, а также число компонент связности k.
Найти: доказательство того, что V - E = k.
Решение:
1. Граф без циклов является лесом. Лес — это объединение одного или нескольких деревьев, которые могут быть несвязанными.
2. Каждый компонент связности в лесу является деревом (или отдельной вершиной). Для дерева с n вершинами количество рёбер равно n - 1.
3. Пусть у нас есть k компонент связности. Обозначим количество вершин в каждой компоненте i как V_i и количество рёбер в каждой компоненте как E_i.
4. Для каждой компоненты дерева (i = 1, 2, ..., k) имеет место следующее равенство:
E_i = V_i - 1.
5. Подсчитаем общее количество вершин и рёбер во всем графе G:
V = V_1 + V_2 + ... + V_k,
E = E_1 + E_2 + ... + E_k.
6. Подставим выражение для количества рёбер каждой компоненты в общее количество рёбер:
E = (V_1 - 1) + (V_2 - 1) + ... + (V_k - 1)
= (V_1 + V_2 + ... + V_k) - k
= V - k.
7. Перепишем это уравнение:
V - E = k.
8. Таким образом, мы доказали, что для графа без циклов число V - E равно числу компонент связности.
Ответ:
В графе без циклов число V - E равно числу компонент связности k.