| Thread Closed |
A question about graph algorithm |
Share Thread | Thread Tools |
| Apr29-05, 06:20 AM | #1 |
|
|
A question about graph algorithm
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
|
| Apr29-05, 04:10 PM | #2 |
|
|
Edited: Not really sure if that's what he was after so I deleted it.
|
| Apr29-05, 04:40 PM | #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) |
| May1-05, 02:58 AM | #4 |
|
|
A question about graph algorithm
Thank you, snoble!
|
| May1-05, 03:00 PM | #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... |
| May1-05, 03:51 PM | #6 |
|
|
I think the key is that each node has a maximum edge degree of 2. emphasis on maximum.
|
| May1-05, 03:52 PM | #7 |
|
|
|
| May1-05, 08:51 PM | #8 |
|
|
wups my bad...thoght it said exactly two =]
the question shouhld be easy then |
| Thread Closed |
| Thread Tools | |
Similar Threads for: A question about graph algorithm
|
||||
| Thread | Forum | Replies | ||
| Odd Graph Algorithm assignment | Programming & Comp Sci | 10 | ||
| modular algorithm question | Linear & Abstract Algebra | 6 | ||
| algorithm for path in graph | Programming & Comp Sci | 3 | ||
| Graph algorithm | Programming & Comp Sci | 25 | ||
| Graph Theory: Dijkstra's Algorithm | General Math | 2 | ||