casais@uni2a.unige.ch (10/02/90)
I have already sent a message asking for information on this
problem last week, but I have not received any useful answer so far.
So, here it is again:
Is there a mathematical (statistical) characterization
of the length and number of paths between the nodes of
a directed graph without circuits ?
I would expect only very broad limits in the general case, but
I think there are more precise formulas (depending on the number of
vertices, edges, etc) for more restricted categories of graphs, like
trees, lattices, etc...
I need references to such results in order to analyze algorithms
working on graph data structures. The CS literature is full of methods
for finding the shortest or even all paths in graphs, but there is
apparently nothing describing the expected length of such paths, or
the average number of paths between two nodes. I would very much
appreciate any help for finding references on this topic in the graph
theory literature. I will post the results to the net (other people
are interested in them too).
Sorry if this looks like some trivial question for real mathematicians,
but I still hold that naive opinion that newsgroups are not just vectors
for social entertainment...
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