Jump to content

Assign values from the range [.....N] to the vertices of the graph


RohanH

Recommended Posts

I have been given a task where, in an undirected graph consisting of N vertices, i.e; numbered from 1 to N , & M edges. Graph is described by two arrays, A & B, both length M,. A pair (A[K], B[K]), for K from 0 to M-1, describes edge among vertex A[K] & vertex B[K].

Task is to assign values from the range [1..N] to the vertices of the graph,giving 1 number to each of the vertices. Such that sum all over edges of the values at the edges endpoints is maximal.

For eg:
N =5, A=[2,2,1,3],B=[1,3,4,4], the graph has 4 edges: (2,1),(2,3),(1,4),(2,4). Inorder to obtain max sum of weights,we can assign following values to vertices : 3,5,2,4,1 (to vertices 1,2,3,4,5).
Thus sum of values at all edges 7+8+7+9=31:

edge(2,3) : 7 = 5 (vertex 2) + 2 (vertex 3)

edge(2,1) : 8 = 5 (vertex 2) + 2 (vertex 1)

edge(1,4) : 7 = 5 (vertex 1) + 2 (vertex 4)

edge(2,4) : 9 = 5 (vertex 2) + 2 (vertex 4)


Notice that the value assigned to vertex 5 did not have any effect on the final result as it is not an endpoint of any edge.


NOW, I need to write a functionthat, given a positive integer N and two arrays A, B of M positive integers, returns the maximum possible sum of values of the edges' endpoints.

For instance :

1. Given N = 5, A = [2, 2, 1, 2], B = [1, 3, 4, 4], the function should return 31, as explained above. 

Did not have much luck with this can anyone help me with the solution thanks in advance!

Link to comment
Share on other sites

2 minutes ago, Barand said:

Your example:

A=[2, 2, 1, 3]

   :  :  :  :

B=[1 ,3 ,4, 4]

the graph has 4 edges: (2,1),(2,3),(1,4),(2,4)

Why is the fourth edge (2,4) and not (3,4) ?

Since its a unidirectional graph. The image is w.r.t the example.

test.png

Link to comment
Share on other sites

OK, that answers that question.

Next, you say you want a function that ...

1 hour ago, RohanH said:

returns the maximum possible sum of values

The example you gave has only one sum (31). To find a maximum you need more than one.

To get more than one value, something is going to have to vary in value (presumably between fixed limits). So is there something else that you aren't telling us?

PS

Just seen your latest post. Is that 0.5pt text in your image supposed to be legible?

Link to comment
Share on other sites

The example test (5, [2, 2, 1, 2], [1, 3, 4, 4])
It shows an error 

PHP Warning: Invalid argument supplied for foreach() in func.php on line 10
Warning: Invalid argument supplied for foreach() in func.php on line 10

 

Link to comment
Share on other sites

Guest
This topic is now closed to further replies.
×
×
  • Create New...

Important Information

We have placed cookies on your device to help make this website better. You can adjust your cookie settings, otherwise we'll assume you're okay to continue.