I\'m playing around with tournaments and currently have the problem that I need
ID: 657205 • Letter: I
Question
I'm playing around with tournaments and currently have the problem that I need to check whether a given subset of the edges of a tournament is transitive (it need not be acyclic). I'm aware that I can always take the transitive closure of the edge set and see whether it terminates without adding a single edge or not, but I was wondering if there might be a simpler way than that.
Note that I'm specifically going for simplicity, not efficiency; the tournaments I want to check are over a maximum of 7 vertices, so complexity really isn't an issue. I would prefer simple, easy to implement ways. The simplest I could find so far is Floyd-Warshall, but maybe someone knows anything that's simpler still.
Explanation / Answer
There's a very simple algorithm for this:
for each edge (u,v) in the graph:
for each edge (v,w) in the graph:
if (u,w) is not in the graph, return "Not transitive"
return "Transitive"
Basically, if the graph is not transitive, then you can always find some path of length two u?v?w such that the edge u?w is not present in the graph. If the graph is transitive, there won't be any such path of length 2. So, just check this condition.