• Предмет: Математика
  • Автор: frendertop
  • Вопрос задан 2 года назад

Сколько существует различных гамильтоновых циклов в полном графе двудольномна 2n вершинах, где в каждой доли по n вершин? Предполагайте, что разные смена начали направления цикла не меняют цикл

Ответы

Ответ дал: malinovskaav8
0

Ответ:

1

В цикл входит вершина номер 1 из первой доли. За неё следует любая из n вершин второй доли. После неё n-1 способом выбирается вершина первой доли, затем n-1 способом вершина второй доли, и так далее. По правилу произведения, получается n!(n−1)!.

Похожие вопросы