задан 23 Июн '17 11:59

Рассмотрите два полных графа с $%n$% и $%(15-n)$% вершинами... если вычислить число рёбер, то получим, что максимум в случае двух графов достигается на паре графов с одной и четырнадцатью вершинами... посчитайте это число и сравните с исходным количеством...

Понятно, что разбиение на большее число графов только уменьшает общее число рёбер... поэтому рассмотрение двух будет достаточным...

(23 Июн '17 12:49) all_exist

Получается, что может? Первая компонента связности — граф K_{14}, а вторая — вершина с петлей?

(23 Июн '17 13:06) olga5

@olga5: граф здесь должен подразумеваться простым -- если допустить петли или кратные рёбра, то никакого количества рёбер для связности не будет достаточно.

(23 Июн '17 13:17) falcao

Идея рассуждения здесь та же, что у @all_exist. Если есть как минимум две связные компоненты, то между вершинами разных компонент рёбер нет, и тогда по меньшей мере n(15-n) рёбер полного графа отсутствует. Эта величина не меньше 14 при 1<=n<=14, так как n^2-15n+14=(n-1)(n-14)<=0. Значит, из общего количества 15*14/2=105 рёбер в несвязном графе присутствуют не более 105-14=91, а тогда граф из условия связен.

(23 Июн '17 13:32) falcao

@falcao, а я Вашу формулу оценки нашла и подставила )) math.hashcode.ru/questions/118312/

(23 Июн '17 16:28) olga5

Получилось так: http://savepic.ru/14556645.jpg

(23 Июн '17 16:30) olga5

@olga5: пользоваться общей формулой, наверное, можно, но надо тогда быть готовым к тому, что её могут попросить доказать. Здесь случай более простой, когда речь идёт о том, одна у нас компонента или больше. То есть это задача о максимизации числа рёбер несвязного графа. Её решение основано на более простом вычислении, когда число вершин делится всего на 2 части, и далее в каждой части берётся полный граф. Поэтому разумно не привлекать усложнённых аргументов.

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

Ваш ответ

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

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

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

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

отмечен:

×552

задан
23 Июн '17 11:59

показан
380 раз

обновлен
23 Июн '17 21:10

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

по почте:

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

по RSS:

Ответы

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

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