В неориентированном лесе v вершин и e рёбер, изолированные вершины учитываются. Сколько компонент связности?
Quant ResearchУровень: ПрактикаForest accounting
В неориентированном лесе v вершин и e рёбер, изолированные вершины учитываются. Сколько компонент связности?
Подсказки
- Посчитайте рёбра каждой компоненты.
- Одиночная вершина — дерево с нулём рёбер.
Ответ
У компоненты-дерева с v_i вершинами v_i-1 рёбер. Суммируя по c компонентам, получаем e=v-c и c=v-e. Для графов с циклами формула без поправки неверна.
Источник и лицензия: Oscar Levin — Discrete Mathematics: An Open Introduction, 3rd edition · CC-BY-SA-4.0 · ответ: редакция Quantoros · перевод: Quantoros