Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Graph-Theory: Algorithm to Find Winner in Tournament Graph (if there is any)

In a tournament graph, how do I find whether there is a player who has dominated all the other players? What is the run-time of such algorithm?

Basically, I need to find if there is an element, from which I can reach to all the other elements, following the path of outlinks.

Clarification: Here; if 'a' beats 'b', and 'b' beats 'c', then a has dominated 'c'. Basically if 'a' beats 'c' directly OR indirectly, it has dominated 'c'. It might be possible that 'a' and 'b' have dominated each other indirectly, which is why the winner may or may not exist. There could also be more than one winners.

Tournament graph is a directed graph where each element has a directed edge with each of the rest of the elements. So there are n*(n-1)/2 directed edges, where n is the number of vertices(players). Wikipedia article on Tournament Graph

like image 971
dc95 Avatar asked Apr 12 '15 15:04

dc95


1 Answers

Let's call the original graph T with N vertices and M edges. First compute the condensation of T and let's call it G. Every vertex v of G represents several vertices of T; additionally, you can reach from any of this vertices to another in T. Also, G is a DAG. So, if there's only one vertex in G with in-degree equal to 0 (let's call it v0), that means that you can reach any vertex in the original graph starting from a vertex in v0. If v0 corresponds to a single vertex in T, then it is the vertex you are looking for already. The complexity is O(N+M).

like image 54
ale64bit Avatar answered Sep 28 '22 10:09

ale64bit