Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

So i am reading up on some interesting network topologies for a CS course and what i am reading is $r$-dimensional meshes of tree's.

An $r$-dimensional mesh of trees is formed by adding complete binary tree's to an $N$-sided $r$-dimensional grid where the grid vertices act as the leafs of each binary tree.

Something like this:

alt text

This book says this about the graph $G = (V, E)$

$|V| = (r+1)N^r - rN^{r-1}$
$|E| = 2rN^r - 2rN^{r-1}$

And the diameter of this graph (the longest path) is $2rlogN$

How did they come about getting this result? The book does not explain it at all and i do not see how they calculated it.

The book i am reading is: Introduction to Parallel Algorithms and Architectures: Arrays, Trees, Hypercubes is any of you are interested.

EDIT:
I have tried to derive this myself by first finding $|V|$ when $r=2$ which would make it a 2-dimensional mesh of trees.

For this i know there are $2n$ complete binary tree's. Each binary tree have $2^{n-1}-1$ vertices. So this means $2n * 2 ^{n-1} -1$ vetices but we are double counting some because there is a binary tree for every row and column. Therefore we can minus out all the leaves of the column binary trees and they will be accounted in the row binary tree's. So that gives us $n * 2^{n-2}$ vertices to minus from the original.

$2n * (2^{n-1} - 1) - n2^{n-2}$

From this can i just times it by $n$ for 3 dimensions and $n^2$ for 4 dimensions? Then up to $n^{r-2}$ to find the total in $r$-dimensions? Was i calculating this correct for $r=2$? I read somewhere else that when $r=2$ $|V| = 3n^2 - 2n$

Second Edit
Maybe i should use the fact that i know the leafs of each complete binary tree have $n$ vertices which means each binary tree is made out of $n + (n-1)$ vertices.

There are $2n$ complete binary tree's which gives me: $2n(n + (n - 1))$ total vertices which contains a few we counted twice. A total of $n^2$ we counted twice. So

$2n(n + (n-1)) - n^2 = 2n^2 + 2n^2 - 2n - n^2 = 3n^2 - 2n$
That looks right, doesn't it?

So now how would I apply this for 3 dimensions, 4, 5 ect.. all the way to $r$-dimensions?

share|improve this question
    
Have you tried deriving it yourself and seeing if you get the same result? What have you got so far? –  Rahul Oct 11 '10 at 17:03
    
yes, i edited my post to show you how i started to derive a solution but got lost... –  gprime Oct 11 '10 at 17:31
    
Your question is not clear. How exactly do you add binary trees so that the grid vertices are the leaves? For instance what leaves are part of the same tree? –  Aryabhata Oct 11 '10 at 18:31
    
Check out this picture users.atw.hu/parallelcomp/files/02fig48.gif which shows a 2-dimensional mesh of trees –  gprime Oct 11 '10 at 18:38
add comment

1 Answer

up vote 1 down vote accepted

You seem to have mixed up two different formulas for the number of nodes in a complete binary tree. If the height of the tree is $h$, it has $2^h-1$ nodes. But in this case, $N$ is not the height but the number of leaves, so the tree has $N-1$ internal nodes, and the total number of nodes is $2n-1$.

From here you get, for $r = 2$, a total of $2N\cdot(2N-1)$ vertices in each tree, less the overcounting of shared leaves, $N\cdot N$, equalling $|V| = 2N(2N-1) - N^2 = 3N^2 - 2N$, which also agrees with the formula $|V| = (r+1)N^r - rN^{r-1}$.

A better way to do it would be to notice that the shared nodes are simply the nodes in the grid, and count them once: $N^r$. The internal nodes of the trees are not shared, there are $N-1$ of them for each tree, and there are $rN^{r-1}$ trees (see below). Add this up and you'll get your solution without worrying about overcounting.

The number of trees is $rN^{r-1}$ because along any direction, a tree connects $N$ nodes, so you need $N^{r-1}$ of them to cover the grid. And the graph contains $r$ copies of this arrangement, one each for the $r$ directions along the grid.

A similar approach should work for counting the number of edges in the graph -- count the edges in the trees and the edges in the grid separately.

For the diameter, first think about what the shortest path between two nodes is in a traditional mesh (without trees), then consider how the additional tree structure shortens this path. Then it should be clear which pair of nodes remains the farthest apart; their distance is the diameter of the graph.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.