Консультация № 189266
25.04.2016, 17:22
0.00 руб.
0 1 1
Уважаемые эксперты! Пожалуйста, ответьте на вопрос:
В графе Г 50 вершин, степень каждой вершины равна трём. Чему равно цикломатическое число графа Г?
Заранее спасибо!

Обсуждение

давно
Старший Модератор
312929
1973
26.04.2016, 06:19
общий
это ответ
Здравствуйте, plaob!

Пусть имеем граф [$915$], содержащий n вершин, r рёбер и состоящий из p компонент связности. Тогда цикломатическое число графа, определяется формулой:

Для графа, степень каждой вершины которого равна k (k-регулярного графа) выполняется соотношение

откуда

и

В данном случае n = 50, k = 3, число компонент связности не указано, поэтому предположим, что p = 1 (связный граф). Тогда
5
Форма ответа