Как доказать, что $%G$% граф при $%n$% вершинах и $%m > \frac {(n-1)!}{k!(n-1-k)!}$% рёбрами является связанным?

задан 2 Фев '15 21:02

изменен 2 Фев '15 21:46

%D0%92%D0%B8%D1%82%D0%B0%D0%BB%D0%B8%D0%BD%D0%B0's gravatar image


9917

1

А что такое $%k$%?...

(2 Фев '15 21:52) all_exist

Поправка насчёт терминологии: не связанным, а связным.

(3 Фев '15 0:46) falcao

k- любое натуральное число

(3 Фев '15 14:11) Алена1
10|600 символов нужно символов осталось
1

любое натуральное число - Хм... то есть если взять $%k=1$%, то по условию $%m>n-1$%...

Если взять $%n=6$% и $%m=6>n-1$%, то можно построить два отделённых треугольника... Получается, что утверждение в условии неверно... Или я чего-то недопонял...

ссылка

отвечен 3 Фев '15 19:14

изменен 3 Фев '15 19:14

В условии явно что-то не так: если k -- любое фиксированное число, то можно положить k=n-1. Это даст неравенство m>1, из которого связность графа заведомо не следует.

Может быть, рассматривается k-регулярный граф? Так или иначе, условие надо уточнить.

(3 Фев '15 19:22) falcao
10|600 символов нужно символов осталось
Ваш ответ

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

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

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

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

отмечен:

×1,505
×560

задан
2 Фев '15 21:02

показан
809 раз

обновлен
3 Фев '15 19:22

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

по почте:

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

по RSS:

Ответы

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

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