casais@uni2a.unige.ch (09/28/90)
I need some help in finding references on the following problem:
Let us consider a directed graph without circuits. Is there a
mathematical characterization of the length and number of paths
(that respect the edge directions) between two nodes x and y of the
graph such that y is reachable from x ?
Specifically, let us consider a trivial kind of graph, the
chain:
A --> B --> C --> D --> E
5 4 3 2 1
It is easy to see that there is always only one possible path
between two nodes, and that for a node at level i (i=1..5) the
length of paths correspond to the following matrix:
A B C D E Average So for node at level i,
A 0 1 2 3 4 2 the average length of a
B - 0 1 2 3 1.5 path to another reachable
C - - 0 1 2 1 is (i - 1) / 2, and for
D - - - 0 1 0.5 a node taken at random:
E - - - - 0 0 (n - 1) / 4 (here n = 5).
Trees are easy to characterize in the same way, but are there
similar (not necessarily identical) kinds of results for other classes
of graphs ? I would appreciate pointers to the literature presenting
such results, including the assumptions made on the graph structures
(demonstrations are not primordial). If there is interest, I will
summarize the responses to the net.
Many thanks in advance
Eduardo Casais
Centre Universitaire d'Informatique EARN/BITNET: casais@cgeuge51.bitnet
12, rue du Lac EAN/MHS: casais@cuisun.unige.ch
1207 Geneve UUCP: mcsun!cui!casais
SUISSE mcsun!chx400!cui!casais
Telephone: (41) (22) 787.65.86
Telefax: (41) (22) 735.39.05