Graph Theory Problem

Matthew Walker mwalker at kydance.net
Fri Dec 12 22:08:07 MST 2008


On Fri, December 12, 2008 10:04 pm, Levi Pearson wrote:
> On Fri, Dec 12, 2008 at 9:50 PM, Dave Smith <dave at thesmithfam.org> wrote:
>> I came across a graph theory problem at work today, and I decided to write
>> it up to sort out the details. In the mean time, I challenge you to solve
>> it:
>>
>>  http://thesmithfam.org/blog/2008/12/12/graph-theory-problem/
>>
>> For those who can't be troubled to follow links, here's the problem
>> summarized: Given any directed graph as a set of edges, find the parent most
>> node or nodes (e.g., the nodes that have the most ancestors).
>
> The nodes that have the most descendants, I think you mean.  Looks
> like an interesting problem!

Interestingly, as presented on his blog, A and B have an infinite number of descendants,
unless you impose an 'only traverse once' rule for nodes. :)


-- 
Matthew Walker
Kydance Hosting & Consulting, Inc. - http://www.kydance.net/
PHP, Perl, and Web Development - Linux Server Administration



More information about the PLUG mailing list