A graph with n vertexes- how to print all possible graph combinations

Page 1 of 1

1 Replies - 638 Views - Last Post: 06 June 2012 - 10:29 PMRate Topic: 2 Votes //<![CDATA[ rating = new ipb.rating( 'topic_rate_', { url: 'https://www.dreamincode.net/forums/index.php?app=forums&module=ajax&section=topics&do=rateTopic&t=282001&amp;s=9b304d97ac6373cf7226dc99e454177a&md5check=' + ipb.vars['secure_hash'], cur_rating: 3, rated: 0, allow_rate: 0, multi_rate: 1, show_rate_text: true } ); //]]>

#1 ellenwindsor199

Reputation: 0
• Posts: 1
• Joined: 06-June 12

A graph with n vertexes- how to print all possible graph combinations

Posted 06 June 2012 - 10:03 PM

Suppose that we set the number of vertexes in a graph as n. (we can set this by user inputs etc.)

I'd like to print all possible cases of connecting vertexes using edges. (So, I'd like to print all possible (simple) connected graphs of n vertexes.)

Also, for each case, I'd like to print degree of each vertex in each case.
Is This A Good Question/Topic? 0

Replies To: A graph with n vertexes- how to print all possible graph combinations

#2 Salem_c

• void main'ers are DOOMED

Reputation: 2185
• Posts: 4,249
• Joined: 30-May 10

Re: A graph with n vertexes- how to print all possible graph combinations

Posted 06 June 2012 - 10:29 PM

So start with a piece of paper and a pencil and start drawing lots of simple graphs based on increasing numbers of points. I guess 1 and 2 points are very simple, as perhaps 3 points might be.

Maybe you can spot a relationship between generating graphs for N points and generating a single instance of graphs for N-1 points.

When you understand how it works on paper, then you can try writing some code.