Здравствуйте! Помогите, пожалуйста, найти плотность двух графов: 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

изменен 15 Янв '14 18:22

Здесь сам подсчёт никаких проблем не представляет, но нужно знать, что авторы задачи в данном случае подразумевают под плотностью. Единого толкования нет, и в разных ситуациях под этим могут пониматься разные характеристики графа.

(15 Янв '14 18:40) falcao

Спасибо! Мне нужно еще найти цикломатическое число. Но оба графа не являются связными. По формуле для связного графа цикломатическое число равно m−n+p (m-ребра, n-вершины, p-число компонент связности). Чему тогда будет равно число компонент свзяности?

(15 Янв '14 20:24) Inna

Если граф связный, то число компонент связности равно 1, то есть p=1. Формула m-n+p действует в общем случае. На самом деле, надо просто сложить эти числа для каждой компоненты связности -- будет то же самое.

Для ориентированных графов это понятие выглядит противоестественно, и я не знаю, есть ли у него разумные аналоги для такого случая.

(15 Янв '14 20:35) falcao

Для неориентированного графа p = 2?

(15 Янв '14 20:40) Inna

Да, там p=2, но проще всего сосчитать общее число независимых циклов. Они там все сразу видны. Оформлять, конечно, лучше по-другому, то есть через формулу.

(15 Янв '14 20:57) falcao

m-n+p = 12-8+2=6, то есть 6 ребер надо удалить, чтобы граф стал ациклическим. Странно, вроде 4 ребра можно удалить для этого.

(15 Янв '14 21:10) Inna

Там получается 6, по числу независимых циклов. Как Вы предлагаете 4 ребра удалить? Надо ведь, чтобы циклов не осталось ни в одной из компонент связности.

(15 Янв '14 21:35) falcao
показано 5 из 7 показать еще 2
10|600 символов нужно символов осталось
Знаете, кто может ответить? Поделитесь вопросом в Twitter или ВКонтакте.

Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×1,654

задан
15 Янв '14 18:21

показан
3709 раз

обновлен
15 Янв '14 21:35

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru