I have a directed graph with $n$ nodes.
for any paired of nodes $A,B$, there is a directed edge that goes in between, but it can't go both ways. i.e. $A \rightarrow B$ and $B \rightarrow A$ cannot exist at the same time.
Let the distance between $A$ to $B$ be the number of edges we travel. How do we arrange the edges, so that the average distance, between all ordered pairs of $A,B$ in the graph, is minimized?
This frankly seems like an simple setup that should come with some known answer, but googling couldn't give me anything useful.
I found http://mathworld.wolfram.com/WienerIndex.html though, but not sure where my example would fall..
Best Answer
For each pair of distinct vertices $(x,y)$, we have $$d(x,y) + d(y,x) \ge 3$$ because each distance is at most $1$, and both of the distances cannot be $1$ simultaneously: that would require an arc $x \to y$ and an arc $y \to x$ to exist at the same time. So the average $\frac{d(x,y) + d(y,x)}{2}$ is at least $\frac32$, and therefore the average over the whole graph is at least $\frac32$.
We achieve this average if we have a tournament in which $d(x,y) \le 2$ for all $x,y$: if the tournament has diameter $2$. In that case, for every pair of distinct vertices $(x,y)$, we either have an arc $x \to y$ (in which case $d(x,y) = 1$ and $d(y,x)=2$) or an arc $y \to x$ (in which case $d(x,y)=2$ and $d(y,x)=1$). Therefore the average $\frac{d(x,y) + d(y,x)}{2}$ is exactly $\frac32$, and this makes the average over the whole graph exactly $\frac32$.
For odd $n$, there is an easy construction: arrange the $n$ points in a circle, and from each point, draw an arc to the next $\frac{n-1}{2}$ points counter-clockwise from it. Here is an example (source):
For even $n \ge 6$, draw the $n-1$ configuration, then put a point in the center which mostly alternates "arc going in" and "arc going out" around the circle. We're going to have one place where the alternating pattern breaks, because $n-1$ is odd, but that's going to be fine for $n\ge 6$.
For $n=4$, unfortunately, diameter $2$ is impossible: there will be one distance of $3$, so the average of the distances will be $\frac32 + \frac1{12} = \frac{19}{12}$.