Известно, что в графе 8 вершин и 10 рёбер. Какое наименьшее количество циклов может быть в этом графе?
С подробным решением, пожалуйста.
Ответы
Ответ дал:
0
Ответ:
Пошаговое объяснение:
По формуле Эйлера для связного графа с $n$ вершинами и $m$ ребрами, $n-m+f=2$, где $f$ - количество граней (включая внешнюю грань).
Так как в данном графе 8 вершин и 10 рёбер, то n=8 и m=10 .Подставим эти значения в формулу Эйлера:
8
−
10
+
�
=
2
⇒
�
=
4
8−10+f=2⇒f=4
Так как каждый цикл в графе образует грань, то количество циклов равно количеству граней. Значит, в данном графе наименьшее количество циклов равно 4.
Вас заинтересует
3 месяца назад
3 месяца назад
3 месяца назад
3 месяца назад
1 год назад