Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

A question about graph algorithm

  1. Apr 29, 2005 #1
    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 :!!)
  2. jcsd
  3. Apr 29, 2005 #2
    Edited: Not really sure if that's what he was after so I deleted it.
    Last edited: Apr 29, 2005
  4. Apr 29, 2005 #3
    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)
  5. May 1, 2005 #4
    Thank you, snoble!
  6. May 1, 2005 #5
    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...
  7. May 1, 2005 #6
    I think the key is that each node has a maximum edge degree of 2. emphasis on maximum.
  8. May 1, 2005 #7
    That's not true. End nodes would just have 1 edge. He said a maximum of 2, not exactly 2.
  9. May 1, 2005 #8
    wups my bad...thoght it said exactly two =]
    the question shouhld be easy then
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook