A question about graph algorithm

gimmytang

Suppose there are 10 nodes in a graph, I need to generate edges between nodes, but there are two conditions to be satisfied:
1) each node can have maximize of two edges.
2) no loop in the graph.
The question is how to run a program which gives an algorithm to generate such a graph randomly?

gim

CrankFan

Edited: Not really sure if that's what he was after so I deleted it.

snoble

Oh this is easy... first you choose a partition of 10... ie a set of positive integers that add to ten.

Then for each number n in the partition pick n nodes. So you broken up your ten nodes into m groups where m is the amount of numbers in your partition.

Then for each group choose an order

Then your edges are just the edges so that each group is a line in the order. ie if one group has edges 6,3,8,2 in that order then your edges are (6,3), (3,8), (8,2)


This is just because if every node's edge degree is at most 2 and there are no loops then every connected set is just a line or a strip (or whatever the proper terminology is)

gimmytang

Thank you, snoble!

neurocomp2003

is that even possilbe?
or do you mean like a eulerian or hamiltonian...what is your definition of a loop-one that encompasses all the nodes or one thats cyclic in <n nodes?

because with those 2 conditions you'll always get a loop...

snoble

I think the key is that each node has a maximum edge degree of 2. emphasis on maximum.

Moo Of Doom

That's not true. End nodes would just have 1 edge. He said a maximum of 2, not exactly 2.

neurocomp2003

wups my bad...thoght it said exactly two =]
the question shouhld be easy then