Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

(old image at bayimg.com/image/iaeidaacn.jpg just there for the post to still make sense)

Both graphs have a braching factor of 3. Graph A is a "tree". Is there a name for the type of graphs as B? (you can ignore the colours)

ps could somebody please change the link into an image?

edit ok, my bad. Clearly I have not as much knowledge of graphs. I am indeed referring to graph searching, as that is something I have more knowledge of. So I suppose I should have drawn arrows, as the graphs are directed from left to right.

  • Is it correct that the first graph is called a tree?
  • Then, the second graph was supposed to be analogous to a tree. Only with the childnodes of sibling nodes merged, so that the number of nodes grows at a constant rate (3 in my example, but $n$ in the general case) rather than exponential as is the case in the tree.
  • I've drawn a new graph image to illustrate more clearly what I mean. Also left out the left-most single node as I think this is a more general graph.

I hope this clears up my drawings a bit.

share|improve this question

closed as no longer relevant by Scott Morrison Nov 13 '09 at 20:06

This question is unlikely to help any future visitors; it is only relevant to a small geographic area, a specific moment in time, or an extraordinarily narrow situation that is not generally applicable to the worldwide audience of the internet. For help making this question more broadly applicable, visit the help center.If this question can be reworded to fit the rules in the help center, please edit the question.

1  
The branching factor that you refer to is called the degree of a vertex of a graph. Graphs whose vertices all have the same degree are called regular. 3-regular graphs are often called "cubic" graphs. You probably want to read this en.wikipedia.org/wiki/Glossary_of_graph_theory –  j.c. Nov 13 '09 at 18:46
1  
You really need to say what you mean, rather than saying "the type of graphs as B". There's no way we can guess from B what class of graphs you have in mind. –  Reid Barton Nov 13 '09 at 18:57
1  
Actually, these are not 3-regular graphs. In graph B, the middle three vertices have degree 4, not 3. I am guessing that branching factor means something like the number of times a breadth first search branches, but I don't know. –  David Speyer Nov 13 '09 at 19:10
    
Seems to be a terminology question which has now been cleared up, so I've closed. Feel free to disagree (preferably at meta, or by flagging for moderator attention). –  Scott Morrison Nov 13 '09 at 20:07

2 Answers 2

up vote 0 down vote accepted

You mean a k-partite graph then, although in this case it isn't exactly a complete k-partite graph because your sets 1 and k are not connected.

share|improve this answer

The second graph is the complete bipartite graph K_4,3. The point on the extreme left could be moved to join the three points on the right to make this clearer.

share|improve this answer
    
I'm not sure, but I think this is a coincidence. But it illustrates perfectly my comment above. –  Reid Barton Nov 13 '09 at 19:14
    
That is indeed a coincidence. I will try to draw more precisely what I mean. –  user1768 Nov 13 '09 at 20:01

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