A question about graph algorithm

In summary, the conversation discusses the process of generating edges between nodes in a graph while satisfying two conditions: each node can have a maximum of two edges and there can be no loops in the graph. The question is asking for an algorithm to randomly generate such a graph. Suggestions for this algorithm include choosing a partition of 10, dividing the nodes into groups, and creating edges based on the order of the groups. The key is to ensure that each node has a maximum edge degree of 2.
  • #1
gimmytang
20
0
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 :!)
 
Mathematics news on Phys.org
  • #2
Edited: Not really sure if that's what he was after so I deleted it.
 
Last edited:
  • #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)
 
  • #4
Thank you, snoble!
 
  • #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 that's cyclic in <n nodes?

because with those 2 conditions you'll always get a loop...
 
  • #6
I think the key is that each node has a maximum edge degree of 2. emphasis on maximum.
 
  • #7
neurocomp2003 said:
because with those 2 conditions you'll always get a loop...

That's not true. End nodes would just have 1 edge. He said a maximum of 2, not exactly 2.
 
  • #8
wups my bad...thoght it said exactly two =]
the question shouhld be easy then
 

What is a graph algorithm?

A graph algorithm is a set of instructions or procedures used to solve problems related to graphs, which are mathematical structures used to represent relationships between objects.

What are some common types of graph algorithms?

Some common types of graph algorithms include breadth-first search, depth-first search, Dijkstra's algorithm, and Prim's algorithm.

How are graph algorithms used in real life?

Graph algorithms have a wide range of applications in real life, such as in social networks, transportation networks, and computer networks. They can be used to find the shortest path between two points, identify clusters or communities within a network, and optimize routes and networks.

What skills are required to understand and implement graph algorithms?

To understand and implement graph algorithms, one needs to have a strong understanding of data structures, algorithms, and mathematics. Knowledge of programming languages and problem-solving skills are also important.

Are there any common challenges or limitations when using graph algorithms?

Some common challenges or limitations when using graph algorithms include dealing with large datasets, identifying the most efficient algorithms for a specific problem, and handling complex and dynamic networks. Additionally, some algorithms may not work well for certain types of graphs or may have high time complexity.

Similar threads

  • General Math
Replies
8
Views
1K
  • Engineering and Comp Sci Homework Help
Replies
4
Views
1K
Replies
1
Views
785
  • Engineering and Comp Sci Homework Help
Replies
1
Views
1K
  • Programming and Computer Science
Replies
3
Views
713
  • Set Theory, Logic, Probability, Statistics
Replies
11
Views
496
Replies
1
Views
773
  • Atomic and Condensed Matter
Replies
2
Views
4K
  • Introductory Physics Homework Help
Replies
10
Views
704
Replies
5
Views
1K
Back
Top