|
Любой граф на $%n$% вершинах, имеющий меньше чем $%n-1$% ребро, обязательно является несвязным. В случае, когда количество ребер в графе больше или равно $%n-1$%, граф может быть как связным, так и несвязным. Какое минимальное количество ребер должен иметь простой граф на $%n$% вершинах, чтобы он гарантированно был связным? задан 26 Окт '15 11:30 
a2g |
|
Ответ здесь не такой будет. Пусть $%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 
falcao |
|
Максимальный несвязный граф - это когда в нем имеются две компоненты связности, каждая является полным графом. Соответственно, если в одной $%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 
knop Я правильно понимаю, что если n = 100, то n = 2 * 50, k = 50. А минимальное количество ребер будет равно 50 * 49 + 1 = 2451?
(26 Окт '15 11:59)
a2g
К сожалению, проверяющая система не считает такой ответ правильным. Нужно найти необходимое количество ребер для графа, построенного на 100 вершинах.
(26 Окт '15 12:09)
a2g
|