Cheap and Secure Web Hosting Provider : See Now

[Solved]: Simplest way to check edge set for transitivity

, , No Comments
Problem Detail: 

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.

Asked By : G. Bach

Answered By : D.W.

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\to v \to w$ such that the edge $u \to 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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/16757

3.2K people like this

 Download Related Notes/Documents

0 comments:

Post a Comment

Let us know your responses and feedback