Create the new instance of problem with graph

Assignment Help Basic Computer Science

Reference no: EM1372108

For each of the following two statements, decide whether it is true or false. If true, give a short explanation. If false provide a counterexample.

a) Suppose we are given an instance of the Minimum Spanning Tree Problem on a graph G, with edge costs that are all positive and distinct. Let T be a minimum spanning tree for this instance. Now, suppose we replace each edge cost Ce by its square, Ce^2, thereby creating a new instance of the problem with the same graph but different costs.

True or false? T must still be a minimum spanning tree for this new instance.

b) Suppose we are given an instance of the Shortest s-t Path problem on a directed graph G. We assume that all edge costs are positive and distinct. Let P be a minimum cost s-t path for this instance. Now suppose we replace each edge cost Ce with its square, Ce^2, thereby creating a new instance of the problem with the same graph but different costs.

True or false? P must still be a minimum cost s-t path for this new instance. "

Reference no: EM1372108

Questions Cloud

Create a matrix of 5x6 : Prepare a matrix of 5x6. with identical columns and rows ranging from 200 to 1000 in equal increments

Explain security model of class using cnss model : suppose that the security model is required for protection of your class. Using CNSS model, examine each of the cells and write a short statement.

Increase demand of labor : Discuss and explain two factors that would increase demand for labor. Suppose if the market price of the good or service that a firm produces increases, what happen to the demand of labor

Groupthink in american history : Write down the some examples of groupthink in American history? Have you ever found yourself seeking to conform in the group situation which resulted in the narrow view of some issue?

Create the new instance of problem with graph : Assume we replace each edge cost Ce by its square, Ce^2, thereby creating the new instance of problem with same graph but different costs.

Find profit-maximizing output and price : A company under monopolistic competition faces the demand curve: P = 500 - 12.5Q. The company's marginal cost is MC = 200 + 5Q.

Erikson stages of development : Explain Erikson's stages of development as each applies to your own personality formation. How did success at one stage make you for meeting the next challenge.

Concept of bureaucracy : Making direct reference to your reading assignments, discuss what is meant by the machine metaphor of modern organizations. How does this machine metaphor of organizations apply to Weber's concept of bureaucracy?

Determine average streaming media data rate : Assume we can accurately forecast set of WAPs that the taxi will visit. Determine average streaming media data rate that we can sustain by downloading prefetched data from WAPs?

User Account

All Pages