Сколько различных простых циклов содержится в графе Kn,m (n < m)?

Где Kn,m - полный двудольный граф.

задан 27 Янв '18 21:13

10|600 символов нужно символов осталось
1

Можно рассмотреть более общий случай $%n\le m$%. Если $%n=1$%, то циклов нет. Пусть $%m\ge2$%. Ясно, что в цикле чередуются вершины той и другой доли, поэтому их одинаковое количество. Пусть оно равно $%2\le k\le n$%. Начнём проходить цикл длиной $%2k$% с некоторой вершины первой доли. Тогда последовательность проходимых вершин имеет вид $%x_1,y_1,\ldots,x_k,y_k$%, где "иксы" берутся из первой доли, а "игреки" из второй. Выбрать последовательность "иксов" можно $%A_n^k=n(n-1)\ldots(n-(k-1))=\frac{n!}{(n-k)!}$% способами. Выбрать "игреки" можно $%A_m^k=\frac{m!}{(m-k)!}$% способами. Понятно, что выбирать можно любые вершины -- по ним строится простой цикл, так как граф у нас полный двудольный. Тот же самый цикл (как циклический подграф) получится при чтении с любой из выбранных $%k$% вершин первой доли, в любом из двух направлений. Поэтому числа размещений надо перемножить, разделить на $%2k$% и просуммировать. Это даст $%\sum\limits_{k=2}^n\frac{n!m!}{2k(n-k)!(m-k)!}$%.

ссылка

отвечен 27 Янв '18 23:03

10|600 символов нужно символов осталось
Ваш ответ

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

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

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

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

отмечен:

×552

задан
27 Янв '18 21:13

показан
745 раз

обновлен
27 Янв '18 23:03

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

по почте:

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

по RSS:

Ответы

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

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