0
1

Каково наименьшее возможное число ребер в графе с n вершинами, среди любых k вершин которого найдется одна, соединенная с остальными k-1 из них?

У меня получился ответ (индукцией по количеству вершин): $$\frac{(k-1+n-1)(n-(k-1))}{2}$$

задан 26 Май 23:59

изменен 27 Май 3:14

@andy: во второй скобке не n-k+1?

(27 Май 2:39) falcao

@falcao: да, опечатался. Если можно, строгое доказательство индукцией по вершинам.

(27 Май 3:13) andy

@andy: если не ошибаюсь, указанное Вами (исправленное) значение означает, что в дополнении графа число рёбер равно (k-1)(k-2)/2.

Такого значения можно достичь, если взять полный подграф на k-1 вершине, а остальные точки сделать изолированными. Но будет ли это экстремальным значением? Вот, например, если k=3, то формула даёт 1 ребро в дополнении, но их можно сделать примерно n/2, соединяя вершины ребром попарно. Мне кажется, тут общая ситуация сложнее.

(27 Май 3:26) falcao

@falcao: я получил данное значение, предположив, что при добавлении n-ой вершины, число рёбер увеличивается на n-1. Так как добавив меньшее число, можно найти k вершин, не удовлетворяющих условию. Итого, ребер: (k-1)+k+...+(n-1)=(k-1+n-1)(n-k+1)/2. Возможно, это неверно. Если так, то прошу привести правильное решение. Спасибо!

(27 Май 3:58) andy
10|600 символов нужно символов осталось
Знаете, кто может ответить? Поделитесь вопросом в Twitter или ВКонтакте.

Ваш ответ

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

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

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

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

отмечен:

×1,263
×1,120
×480
×58

задан
26 Май 23:59

показан
135 раз

обновлен
27 Май 3:58

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

по почте:

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

по RSS:

Ответы

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

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