|
Докажите, что при любых $%0 <= k <= n$% таких, что $%kn$% - четное, существует граф на $%n$% вершинах, степни которого равны $%k$%. Возьмем: $%k = 8, n = 8$%. Нельзя построить граф с $%8$% вершинами, чтобы степень хотя бы одной вершины была равна $%8$%. Я прав? задан 17 Ноя '14 0:35 
Leva319 |
Здравствуйте
Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.
Присоединяйтесь!
отмечен:
задан
17 Ноя '14 0:35
показан
1429 раз
обновлен
17 Янв '15 18:48
Связанные вопросы
Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Здесь не сказано, что граф простой, то есть формально всё корректно. Другое дело, что в таком виде задача не слишком интересна. Если чётно n, то разбиваем вершины на пары, и в каждой паре рассматриваем k соединений. А если чётно k, то у каждой вершины рисуем k/2 петель.
Можно, наверное, рассмотреть такую версию задачи, когда граф простой, и k<n.
Если граф не является простым, значит я могу использовать петли? Вы это имели в виду?
Да, петли и кратные рёбра можно использовать, если нет ограничений. Но тогда даже условие k<=n делается лишним. Мне кажется, подразумевался всё-таки простой граф, но неравенство по недосмотру написали как нестрогое. С другой стороны, за это отвечают только составители, поэтому можно ответить формально. Не сказали, что граф простой -- сами виноваты.