RohanH Posted August 21, 2021 Share Posted August 21, 2021 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 https://forums.phpfreaks.com/topic/313584-assign-values-from-the-range-n-to-the-vertices-of-the-graph/ Share on other sites More sharing options...
Barand Posted August 21, 2021 Share Posted August 21, 2021 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) ? Link to comment https://forums.phpfreaks.com/topic/313584-assign-values-from-the-range-n-to-the-vertices-of-the-graph/#findComment-1589272 Share on other sites More sharing options...
RohanH Posted August 21, 2021 Author Share Posted August 21, 2021 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. Link to comment https://forums.phpfreaks.com/topic/313584-assign-values-from-the-range-n-to-the-vertices-of-the-graph/#findComment-1589273 Share on other sites More sharing options...
Barand Posted August 21, 2021 Share Posted August 21, 2021 Fine, but why is the 4th edge (2, 4) and not (3, 4) when the pattern appears to be Link to comment https://forums.phpfreaks.com/topic/313584-assign-values-from-the-range-n-to-the-vertices-of-the-graph/#findComment-1589274 Share on other sites More sharing options...
RohanH Posted August 21, 2021 Author Share Posted August 21, 2021 Ok, my bad it must have been A=[2, 2, 1, 2] and B=[1,3,4,4] Link to comment https://forums.phpfreaks.com/topic/313584-assign-values-from-the-range-n-to-the-vertices-of-the-graph/#findComment-1589275 Share on other sites More sharing options...
RohanH Posted August 21, 2021 Author Share Posted August 21, 2021 (edited) [screenshot of a description of the problem] Edited August 23, 2021 by requinix removing screenshots by request Link to comment https://forums.phpfreaks.com/topic/313584-assign-values-from-the-range-n-to-the-vertices-of-the-graph/#findComment-1589276 Share on other sites More sharing options...
RohanH Posted August 21, 2021 Author Share Posted August 21, 2021 (edited) [screenshot of a description of the problem] [screenshot giving some sample inputs and outputs] Edited August 23, 2021 by requinix removing screenshots by request Link to comment https://forums.phpfreaks.com/topic/313584-assign-values-from-the-range-n-to-the-vertices-of-the-graph/#findComment-1589277 Share on other sites More sharing options...
Barand Posted August 21, 2021 Share Posted August 21, 2021 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 https://forums.phpfreaks.com/topic/313584-assign-values-from-the-range-n-to-the-vertices-of-the-graph/#findComment-1589278 Share on other sites More sharing options...
RohanH Posted August 21, 2021 Author Share Posted August 21, 2021 Just added some clear pictures for the same Link to comment https://forums.phpfreaks.com/topic/313584-assign-values-from-the-range-n-to-the-vertices-of-the-graph/#findComment-1589279 Share on other sites More sharing options...
Barand Posted August 21, 2021 Share Posted August 21, 2021 vertices values are 3,5,2,4,1 Is there rule for what values are applied to the vertices? I haven't spotted the pattern yet. Link to comment https://forums.phpfreaks.com/topic/313584-assign-values-from-the-range-n-to-the-vertices-of-the-graph/#findComment-1589280 Share on other sites More sharing options...
Barand Posted August 21, 2021 Share Posted August 21, 2021 Try this function... Link to comment https://forums.phpfreaks.com/topic/313584-assign-values-from-the-range-n-to-the-vertices-of-the-graph/#findComment-1589282 Share on other sites More sharing options...
RohanH Posted August 23, 2021 Author Share Posted August 23, 2021 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 https://forums.phpfreaks.com/topic/313584-assign-values-from-the-range-n-to-the-vertices-of-the-graph/#findComment-1589308 Share on other sites More sharing options...
requinix Posted August 23, 2021 Share Posted August 23, 2021 OP has requested that this thread be locked due to school policies regarding assignments. Link to comment https://forums.phpfreaks.com/topic/313584-assign-values-from-the-range-n-to-the-vertices-of-the-graph/#findComment-1589310 Share on other sites More sharing options...
Recommended Posts