2
$\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?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\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/

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .