Сколько компонент связности имеет лес , содержащий 12 вершин и 10 рёбер?

+403 голосов
3.0m просмотров

Сколько компонент связности имеет лес , содержащий 12 вершин и 10 рёбер?


Алгебра (13 баллов) | 3.0m просмотров
Дан 1 ответ
+136 голосов
Правильный ответ

Каждая компонента связности леса - дерево.

Каждое дерево на n вершинах имеет n-1 ребро.

А значит число компонент связности леса - это разность между числом вершин и числом ребер. В данном случае 12 - 10 = 2 компоненты связности

(11.1k баллов)