Назовем простым циклом с листом граф, полученный объединением простого цикла и одной вершины, которая соединена ровно одним ребром с ровно одной вершиной цикла (число вершин и число ребер такого графа совпадают). Сколько различных простых циклов с листом содержится в Kn?

Где Kn - полный граф на n вершинах. В ответе написано, что alt text

Но ведь известен факт, что различных простых циклов на k вершинах имеется (k−1)!/2.

задан 25 Янв '18 17:58

1

@worker: случай k=n даёт нулевое слагаемое. Его можно не учитывать. При 3<=k < n загадываем k вершин из n, которые войдут в простой цикл. Далее n-k способами загадаем будущий "лист". Он соединён с одной из k вершин. Остальные вершины цикла нумеруем (k-1)! способами. Из-за двух возможных порядков следования, делим на 2. В итоге это и получается. Саму формулу можно слегка упростить.

(25 Янв '18 18:24) falcao

@falcao: 1) Первый множитель: При 3<=k < n загадываем k вершин из n, которые войдут в простой цикл - [Число сочетаний из n по k] 2) Второй множитель: [n-k] - это число способов загадать "лист" 3) Третий множитель: [k] - это число способов его соединить с циклом 4) Четвертый множитель: [(k−1)!/2] - число способов выбрать цепь - цепью она становится после выдергивания из нее одной вершины, соединенной с "листом"

Так?

(25 Янв '18 18:56) worker
1

@worker: Вы повторили мои слова. Не вижу никакой разницы. Конечно, всё так.

(25 Янв '18 19:18) falcao
10|600 символов нужно символов осталось
Знаете, кто может ответить? Поделитесь вопросом в Twitter или ВКонтакте.

Ваш ответ

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

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

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

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

отмечен:

×548

задан
25 Янв '18 17:58

показан
1569 раз

обновлен
25 Янв '18 19:18

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

по почте:

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

по RSS:

Ответы

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

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