wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> medium >> Maximum number of 'levels' in a graph
        
(Message started by: towr on Aug 2^nd, 2007, 6:15am)

Title: Maximum number of 'levels' in a graph
Post by towr on Aug 2^nd, 2007, 6:15am

Let's define a level as the set composed of all the nodes of a graph that can be reached from a given node in the same number of steps.
Then how many distinct 'levels' can there be at most for a graph with n nodes?

In a more mathematical notation: if we have levels
L_i(r) = { x | Rⁱ(r,x)}
What is the maximum k for which we can have all L_i(r) and L_j(r) distinct for some r and i < j http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/le.gif k

Obviously there are at most 2ⁿ different possible L_i's, but can k be that big?

Title: Re: Maximum number of 'levels' in a graph
Post by Grimbal on Aug 2^nd, 2007, 7:47am

As I understand the problem, an upper bound would be n²+1. There are n starting nodes, and the distance between nodes ranges from 0 to n-1. One more for the empty set. It is easy to see that even that maximum cannot be reached for n>1.

I think n(n+1)/2 can be reached.

In your definition, does the set include those nodes that can be otherwise reached in less than i steps?

Title: Re: Maximum number of 'levels' in a graph
Post by towr on Aug 2^nd, 2007, 9:02am

on 08/02/07 at 07:47:15, Grimbal wrote:

In your definition, does the set include those nodes that can be otherwise reached in less than i steps?

No, they're only in the set if they can be reached in exactly i steps.

Title: Re: Maximum number of 'levels' in a graph
Post by towr on Aug 2^nd, 2007, 9:36am

It seems you can get at least (n-1)²+1 levels, if you take a string of nodes of which the last two elements are connected to the start.
That the best I've found.

Title: Re: Maximum number of 'levels' in a graph
Post by Grimbal on Aug 2^nd, 2007, 2:58pm

on 08/02/07 at 09:02:59, towr wrote:

No, they're only in the set if they can be reached in exactly i steps.

I expected "yes, I include all nodes that can be reached in exactly i steps" or "no, I include only nodes that can be reached in i steps an not in less".

Let's take an example. If you have a list of 7 nodes, r is the 3rd and i increases from 0, do you get:
--x----
-x-x---
x---x--
-----x-
------x
or
--x----
-x-x---
x-x-x--
-x-x-x-
x-x-x-x
?

Anyway, it seems to be the 2nd option. And it is a bit messy to count.

Title: Re: Maximum number of 'levels' in a graph
Post by towr on Aug 2^nd, 2007, 3:28pm

on 08/02/07 at 14:58:43, Grimbal wrote:

I expected "yes, I include all nodes that can be reached in exactly i steps" or "no, I include only nodes that can be reached in i steps an not in less".

I would hope my reply would be consider equivalent to the former.

L_i(r) = { x | Rⁱ(r,x)}

R⁰(r,r)
R¹(r,x) iff R(r,x)
i>1: Rⁱ(r,x) iff http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/exists.gif _v R(r,v) http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/wedge.gif R^i-1(v,x)

R(r,x) iff there is a connection from r to x.

Quote:

Let's take an example. If you have a list of 7 nodes, r is the 3rd and i increases from 0, do you get:
--x----
-x-x---
x---x--
-----x-
------x

If the connection are uni-directional away from the third node, yes.

If they are bidirectional you'd have:

Quote:

--x----
-x-x---
x-x-x--
-x-x-x-
x-x-x-x

I suppose I left it in the middle a bit whether it should be a directed graph or not. Of course, an undirected graph is really just a directed graph with symmetric connectivity.

Quote:

Anyway, it seems to be the 2nd option. And it is a bit messy to count.

Yes, that's why I posted it here.
It came up in programming project I'm working on, and I was worried it might be exponential or at least much worse than quadratic.

And it seemed to make an interesting puzzle.