CODEWITHSUNDEEP
algorithmgraphgraph-theorybacktracking
user3160055
user3160055

Reputation: 121

How to create all different combination undirected graphs with sum of any two adjacent vertices equal to prime numbers

How to create all different combination undirected graphs with sum of any two adjacent vertices equal to prime numbers. The number set is [1….10]

example:- undirected graph for number set [1...4]

 1------2     2)   3---2
 |      |           |
 |      |           |
 4      3           4
                    |
                    |
                    1

appreciate your help.

Thanks.

Upvotes: 0

Views: 738

Answers (3)

Alexandru Barbarosie
Alexandru Barbarosie

Reputation: 3002

As a general approach you can reform your problem as follows: find all possible prime numbers which can be generated as sum of values from [k..n] (k<=n). After finding all those combinations you have to take all possible subsets of those combinations. So your solution will be the set of all those subsets.

In pseudo code:

  • Step1: generate a Sieve of prime numbers from k to (k+n+1)(k+n)/2(sum of all numbers from k to n)
  • Step2: check for every prime if it can be generated as sum of the numbers you have. Store every possible combination. You can write a recursive function to do it.
  • Step3: find all subsets of the set generated from combinations in Step2.
  • Step4: output all those subsets.

Upvotes: 0

Paul Hankin
Paul Hankin

Reputation: 58339

All possible (undirected) edges are:

1-2, 1-4, 1-6, 1-10, 2-3, 2-5, 2-9, 3-4, 3-8, 3-10, 4-7, 4-9, 5-6, 5-8, 6-7, 7-10, 8-9, 9-10

All possible graphs are subsets of this set of edges. There's 18 edges, so there's 218 possible graphs.

Upvotes: 0

Mark Amery
Mark Amery

Reputation: 155004

From a high level, your algorithm looks something like this:

  1. Construct the set of all permitted edges by iterating over all the pairs of distinct numbers in your set of vertices and testing if they sum to a prime.
  2. Construct the set of all permitted graphs by taking all possible subsets of the set of permitted edges.

Upvotes: 0

Related Questions