Консультация № 188165
31.10.2015, 16:17
0.00 руб.
0 3 1
Уважаемые эксперты! Пожалуйста, ответьте на вопрос:
Найти в орграфе компоненты связности,цикломатическое число и плотность.
Заранее спасибо!

Обсуждение

давно
Профессор
230118
3054
31.10.2015, 17:09
общий
это ответ
Здравствуйте, Трошков Владимир!

В графе 2 компоненты связности по 3 вершины и 1 компонента по 1 вершине.

В графе 9 вершин и 11 ребер. Максимальное количество ребер в плотном графе было бы 36. Плотность графа равна 11/36.

Наименьшее количество рёбер, после удаления которых в графе не содержится ни одного цикла, называется цикломатическим числом γ(G).
Цикломатическое число определяется по формуле
γ(G) = r - n + p=11-9+1=3

Цикломатическое число равно 3.
давно
Посетитель
399077
12
31.10.2015, 19:10
общий
Адресаты:
Спасибо большое!
Хотел бы спросить,а при расчете плотности случайно используется не эта формула?
D = 2E/(V(V−1))
давно
Профессор
230118
3054
31.10.2015, 19:23
общий
Адресаты:
Если бы был неориентированный, то использовалась бы. Но тут можно проводить ребра в обе стороны, поэтому лучше E/(V(V−1))
Форма ответа