Любой граф на $%n$% вершинах, имеющий меньше чем $%n-1$% ребро, обязательно является несвязным. В случае, когда количество ребер в графе больше или равно $%n-1$%, граф может быть как связным, так и несвязным. Какое минимальное количество ребер должен иметь простой граф на $%n$% вершинах, чтобы он гарантированно был связным?

задан 26 Окт '15 11:30

изменен 26 Окт '15 11:31

10|600 символов нужно символов осталось
2

Ответ здесь не такой будет. Пусть $%n > 1$%. Рассмотрим несвязный граф, в котором одна вершина ни с чем не соединена, а остальные соединены попарно. Тогда в графе $%(n-1)(n-2)/2$% рёбер, и он не связен. Если количество рёбер увеличить на единицу, то их получится $%(n-1)(n-2)/2+1$%, и здесь уже связность графа гарантирована. Действительно, если компонент связности как минимум две, и одна из них содержит $%k$% вершин, где $%1 < k < n$%, то количество отсутствующих рёбер не меньше $%k(n-k)$%. Эта величина не меньше $%n-1$% ввиду неравенства $%kn-k^2-n+1=(k-1)(n-(k+1))\ge0$%, а у нас отсутствует меньше рёбер.

ссылка

отвечен 26 Окт '15 12:23

10|600 символов нужно символов осталось
0

Максимальный несвязный граф - это когда в нем имеются две компоненты связности, каждая является полным графом. Соответственно, если в одной $%k$% вершин, а в другой $%n-k$%, то число ребер в таком графе в сумме равно $%k(k-1)/2 + (n-k)(n-k-1)/2$%. Максимум этого выражения достигается при $%k=[n/2]$%. А если увеличить найденное значение числа ребер на 1, то граф окажется гарантированно связным.

Итак, ответ равен $%k(k-1)+1$% для $%n=2k$% и $%k^2+1$% для $%n=2k+1$%.

ссылка

отвечен 26 Окт '15 11:48

Я правильно понимаю, что если n = 100, то n = 2 * 50, k = 50. А минимальное количество ребер будет равно 50 * 49 + 1 = 2451?

(26 Окт '15 11:59) a2g

@a2g, совершенно верно

(26 Окт '15 12:04) knop

К сожалению, проверяющая система не считает такой ответ правильным. Нужно найти необходимое количество ребер для графа, построенного на 100 вершинах.

(26 Окт '15 12:09) a2g
10|600 символов нужно символов осталось
Ваш ответ

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

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

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

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

отмечен:

×514
×489
×156
×130

задан
26 Окт '15 11:30

показан
5266 раз

обновлен
26 Окт '15 12:23

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

по почте:

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

по RSS:

Ответы

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

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