1
$\begingroup$

I want to generate all strongly connected tournament of size $n \in \{4, 11\}$.
As a strongly connected tournament has an hamiltonian path I may assume that $v_i v_{i+1}$ is always an arc, and $v_n v_1$ is an arc. Thus, I have to decide the outcome of $m:= n\frac{(n-1)}{2} -n$ games, ie I have $2^m$ tournaments to study. \n However, it is clear some tournaments are generated multiple times.
From what I read here on similar questions it seems that finding an optimal way to do it is probably a very complicated question; but:

  1. Do you have guesses on what additional assumptions I may take?
  2. A completely different idea on how to do abord the question?

Bonus question: if I do not change my algorithm, can I know how many times each tournament is generated?

$\endgroup$

1 Answer 1

1
$\begingroup$

Brendan McKays program “gentourng” can generate all tournaments up to isomorphism - I recently used it for all 11-vertex tournaments.

It is part of the nauty package:

https://users.cecs.anu.edu.au/~bdm/nauty/

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.