Question

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

Answer 1

Ответ:

1

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