You are given an undirected graph consisting of N vertices, numbered from 1 to N, and...
Fantastic news! We've Found the answer you've been seeking!
Question:
Transcribed Image Text:
You are given an undirected graph consisting of N vertices, numbered from 1 to N, and M edges. The graph is described by two arrays, A and B, both of length M. A pair (A[K], B[K]), for K from 0 to M-1, describes an edge between vertex A[K] and vertex B[K]. Your task is to assign all values from the range [1.N] to the vertices of the graph, giving one number to each of the vertices. Do it in such a way that the sum over all edges of the values at the edges' endpoints is maximal. For example, given N = 5, A = [2, 2, 1, 2], B = [1, 3, 4, 4], the graph has four edges: (2, 1), (2, 3), (1, 4), (2, 4). In order to obtain the maximum sum of weights, you can assign the following values to the vertices: 3, 5, 2, 4, 1 (to vertices 1, 2, 3, 4, 5 respectively). 5, val=1 1, val=3 7 2, val=5 3, val=2 9. 4, val=4 This way we obtain the sum of values at all edges' endpoints equal to 7 + 8 + 7 +9 = 31: This way we obtain the sum of values at all edges' endpoints equal to 7 + 8+7+9 = 31: edge (2, 3): 7 = 5 (vertex 2) + 2 (vertex 3) edge (2, 1): 8 = 5 (vertex 2) + 3 (vertex 1) edge (1, 4): 7 = 3 (vertex 1) + 4 (vertex 4) edge (2, 4): 9 = 5 (vertex 2) + 4 (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. Write a function: You are given an undirected graph consisting of N vertices, numbered from 1 to N, and M edges. The graph is described by two arrays, A and B, both of length M. A pair (A[K], B[K]), for K from 0 to M-1, describes an edge between vertex A[K] and vertex B[K]. Your task is to assign all values from the range [1.N] to the vertices of the graph, giving one number to each of the vertices. Do it in such a way that the sum over all edges of the values at the edges' endpoints is maximal. For example, given N = 5, A = [2, 2, 1, 2], B = [1, 3, 4, 4], the graph has four edges: (2, 1), (2, 3), (1, 4), (2, 4). In order to obtain the maximum sum of weights, you can assign the following values to the vertices: 3, 5, 2, 4, 1 (to vertices 1, 2, 3, 4, 5 respectively). 5, val=1 1, val=3 7 2, val=5 3, val=2 9. 4, val=4 This way we obtain the sum of values at all edges' endpoints equal to 7 + 8 + 7 +9 = 31: This way we obtain the sum of values at all edges' endpoints equal to 7 + 8+7+9 = 31: edge (2, 3): 7 = 5 (vertex 2) + 2 (vertex 3) edge (2, 1): 8 = 5 (vertex 2) + 3 (vertex 1) edge (1, 4): 7 = 3 (vertex 1) + 4 (vertex 4) edge (2, 4): 9 = 5 (vertex 2) + 4 (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. Write a function:
Expert Answer:
Answer rating: 100% (QA)
Java Code public class Main public static void mainS... View the full answer
Related Book For
Introduction to Operations Research
ISBN: 978-1259162985
10th edition
Authors: Frederick S. Hillier, Gerald J. Lieberman
Posted Date:
Students also viewed these programming questions
-
You are given an annual time series with 40 consecutive values and asked to fit a fifth-order autoregressive model. a. How many comparisons are lost in developing the autoregressive model? b. How...
-
You are given an M/M/1 queueing system with mean arrival rate and mean service rate . An arriving customer receives n dollars if n customers are already in the system. Determine the expected cost in...
-
You are given an M/M/2 queueing system with = 4 per hour and = 6 per hour. Determine the probability that an arriving customer will wait more than 30 minutes in the queue, given that at least 2...
-
A 2-in dia. steel bar is subjected to the loading indicated. Locate and estimate the maximum shear stress in the weld throat. F T____ 2 ...... kips 15 kip ·in 6 in in 2-in dia.
-
(a) What can you suggest to Lucia about figuring out her investment philosophy? (b) Would you recommend active or passive investing for her, and why? (c) Should Lucia be a lender or owner? (d)...
-
Review Research In Motions income statement in Appendix A and identify its revenues for the years ended February 27, 2010, February 28, 2009, and March 1, 2008. For the year ended February 27, 2010,...
-
The following financial information is taken from the annual report of Intel Corporation: Using the above data, calculate the companys inventory turnover, inventory-on-hand period, and gross profit...
-
Zimmermans Bank is the only bank in the small town of St. Thomas. On a typical Friday, an average of 10 customers per hour arrives at the bank to transact business. There is one teller at the bank,...
-
several types of intrusion detection and prevention systems (IDPSs), which function like burglar alarms for computer data. Of all the systems described, which one intrigues you the most, and why? If...
-
GloFish, Inc. has genetically engineered a species of fish that glows in normal lighting conditions. The company believes the new fish will be a huge success as a new pet option for children and...
-
Suppose that you are about to open a new pizza restaurant in the Bronx. You want to know how many times people order pizza per month to estimate your sales revenue. You go out and take a random...
-
What are the differences between public sector and private sector auditing?
-
Explain behavior-based quality culture as a concept.
-
List and describe the steps involved in laying the foundation for a quality culture.
-
What are the most important advantages of PBB that have emerged from recent experience?
-
What are the benefits of accrual budgeting?
-
Go to ted.com (also available in YouTube) and watch at least one 18 minute video. Document the video and how the speaker used the nine elements mentioned in the "Understanding Presentation Skills in...
-
In exchange for land, the company received a 12-month note on January 1. The face amount of the note is $1,000, and the stated rate of interest is 13%, compounded annually. The 13% rate is equal to...
-
Reconsider the example of a traveling salesman problem shown in Fig. 14.4. (a) When the sub-tour reversal algorithm was applied to this problem in Sec. 14.1, the first iteration resulted in a tie for...
-
Reconsider Prob. 20.4-6 involving the game of craps. Now the objective is to estimate the probability of winning a play of this game. If the probability is greater than 0.5, you will want to go to...
-
Reconsider Prob. 19.2-6. (a) Formulate a linear programming model for finding an optimal policy.
-
On January 1, 2011, BGA Company had a balance of \(\$ 500,000\) in its Bonds Payable account. During 2011, BGA issued bonds with a \(\$ 150,000\) face value. There was no premium or discount...
-
The following accounts and corresponding balances were drawn from Winston Company's 2012 and 2011 year-end balance sheets. Other information drawn from the accounting records: 1. Winston incurred a...
-
Top Brands, Inc. (TBI), presents its statement of cash flows using the indirect method. The following accounts and corresponding balances were drawn from TBI's 2012 and 2011 year-end balance sheets....
Study smarter with the SolutionInn App