К содержанию
Quantoros

В неориентированном лесе 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

Похожие вопросы