Skip to main content
1 of 2
Bjørn Kjos-Hanssen
  • 24.8k
  • 3
  • 58
  • 114

I don't know that your characteristic has been explicitly studied before, nor would I be surprised if it has, but here is a more general setting.

The directed graph distance $d(a,b)$ from vertex $a$ to $b$ is the minimum length of a directed path from $a$ to $b$. (Of course, $d(a,b)\ne d(b,a)$ in general.)

Then the distance from a vertex to a set of vertices is also often defined, but in the directed case there are two versions: $$d(a,B)=\min\{d(a,b):b\in B\},$$ $$d(B,a)=\min\{d(b,a):b\in B\},$$ where again typically $d(a,B)\ne d(B,a)$.

You're looking at the case where $B$ is the set of all sources or the set of all sinks.

And then, upon picking an edge $(v_0,v_1)$ at random, $d(v_0,B)-d(v_1,B)$ tells you how much closer to $B$ you got.

Bjørn Kjos-Hanssen
  • 24.8k
  • 3
  • 58
  • 114