|
Здравствуйте! Помогите, пожалуйста, найти плотность двух графов: http://savepic.net/4320967.htm Слева граф ориентированный, а справа неориентированный. Для неориентированного нашел формулу в википедии: http://ru.wikipedia.org/wiki/Плотный_граф D = 2E/(V(V−1)) = 2·12/(8·7) = 0,428 задан 15 Янв '14 18:21 
Inna
показано 5 из 7
показать еще 2
|
Здравствуйте
Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.
Присоединяйтесь!
отмечен:
задан
15 Янв '14 18:21
показан
3781 раз
обновлен
15 Янв '14 21:35
Связанные вопросы
Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Здесь сам подсчёт никаких проблем не представляет, но нужно знать, что авторы задачи в данном случае подразумевают под плотностью. Единого толкования нет, и в разных ситуациях под этим могут пониматься разные характеристики графа.
Спасибо! Мне нужно еще найти цикломатическое число. Но оба графа не являются связными. По формуле для связного графа цикломатическое число равно m−n+p (m-ребра, n-вершины, p-число компонент связности). Чему тогда будет равно число компонент свзяности?
Если граф связный, то число компонент связности равно 1, то есть p=1. Формула m-n+p действует в общем случае. На самом деле, надо просто сложить эти числа для каждой компоненты связности -- будет то же самое.
Для ориентированных графов это понятие выглядит противоестественно, и я не знаю, есть ли у него разумные аналоги для такого случая.
Для неориентированного графа p = 2?
Да, там p=2, но проще всего сосчитать общее число независимых циклов. Они там все сразу видны. Оформлять, конечно, лучше по-другому, то есть через формулу.
m-n+p = 12-8+2=6, то есть 6 ребер надо удалить, чтобы граф стал ациклическим. Странно, вроде 4 ребра можно удалить для этого.
Там получается 6, по числу независимых циклов. Как Вы предлагаете 4 ребра удалить? Надо ведь, чтобы циклов не осталось ни в одной из компонент связности.