Tournament graph

2
votes

A tournament is a directed graph (digraph) obtained by assigning a direction for each edge in an undirected complete graph. That is, it is a directed graph in which every pair of vertices is connected by a single directed edge.

Data structure is adjacency matrix.

What s an algorithm to find if the graph is a tournament graph?

3
algorithmgraph
This sounds like a homework problem. Perhaps you could elaborate on your own thoughts regarding the problem and we could assist you wherever you've gotten stuck? - Amber
That guarantee is only true if every node can be reached from your starting node - which isn't necessarily the case here (envision a trivial example where all of the edges connected to your chosen starting node are directed towards it rather than away). - Amber
Also, @unknown: keep in mind that your data structure here is an adjacency matrix; it takes O(n) time to look up the edges for a node. Thus just traversing the graph would still take O(n^2) time. - Amber
Yes. But if your traversal takes O(n^2) - which it will, due to the need to look up edges in the adjacency matrix - then it doesn't matter if the back-edge check is constant time, the overall algorithm is still O(n^2). - Amber
Yet another way to look at this problem: since the number of edges is equal to the number of possible pairs of vertices, there will be n*(n-1)/2 edges, which is O(n^2). Your traversal is O(V+E), which thus is O(n+n^2), and thus is O(n^2). - Amber

3 Answers

5
votes

There are n^2 entries in the adjacency matrix, and you need the info that is in all of the entries to solve the problem. (You need the 1's to check that the proper edges exist, and the 0's to check that the back-edges don't exist.) Thus since you have to read at least N^2 entries from the matrix, the overall problem must take at least O(N^2) time.

Regarding BFS search attempts: if your traversal takes O(n^2) - which it will, due to the need to look up edges in the adjacency matrix - then it doesn't matter if the back-edge check is constant time, the overall algorithm is still O(n^2).

Yet another way to look at this problem: since the number of edges is equal to the number of possible pairs of vertices, there will be n*(n-1)/2 edges, which is O(n^2). Your traversal is O(V+E), which thus is O(n+n^2), and thus is O(n^2).

Since the best-case time for this algorithm is O(n^2), you might as well simply loop through the upper-right half of matrix (above the diagonal) and check that for each of those entries, either a) it is 1, or b) its transpose equivalent is 1.

2
votes

Edit: missed the part where the graph was complete.

If M is your adjacency matrix, Mt is the transposed matrix, ~M is the matrix with all the "bits" inverted, and A^B is the xor bit by bit between the two matrix.

Then the matrix is a tournament iff:

~(M^Mt) = I

2
votes

To add to tonfa's comment:

Brief: The algorithm "for each i ≠ j, check to see that exactly one of (i,j) and (j,i) is in your graph" is asymptotically optimal.

More detail: To just read in the adjacency matrix is going to take you Ω(n2) time. So there is no way to solve this problem in o(n2) time. But let's ignore the input.

Suppose that the matrix is already in memory. To ensure that the undirected version of your graph is complete, you have to somehow determine that, for each i ≠ j, at least one of the edges (i,j) and (j,i) is in your graph. As you have only the adjacency graph, this means you will have to at some point visit at least one of (i,j) or (j,i) for each i ≠ j. There is no other way to guarantee completeness. Verifying this will take n(n+1)/2 = O(n2) steps.