Question a suppose that you are given an instance of the, Ask an Expert

Engineering

Question :

(a) Suppose that you are given an instance of the MST problem on a graph G, with edge weights that are all positive and distinct. Let T be the minimum spanning tree for G returned by Kruskal's algorithm. Now suppose we replace each edge weight w_e by its square w2_e, thereby creating a new instance of the problem with the same graph but different edge weights. Is it true that T is still a minimum spanning tree for this new instance. If you think it is true, give an explanation; otherwise, give a counterexample.

(b) Let G = (V, E) e a directed graph in which every edge has unit length (i.e., length = 1). Design an algorithm that given any two vertices s and t of G, find a shortest path from s to t using O(|E|) time.

View complete question

Engineering Mathematics, Engineering

Category:- Engineering Mathematics
Reference No.:- M93128704

Have any Question?Write your Review or question?

Related Questions in Engineering Mathematics

All these questions should be answered in matlab 1 generate

All these questions should be answered in MATLAB !!! 1. Generate a set of 3 random patterns of dimension 12 where each value is +1 or -1.(3 random 12*12 matrix) 2. Create a 12-unit Hopfield network (a 12x12 matrix) from ...

Clculus assignment -q1 find the total differential of w

CALCULUS ASSIGNMENT - Q1. Find the total differential of w = x 3 yz + xy + z + 3 at (x, y, z) = (1, 2, 3). Q2. Find the value of the double integral ∫∫ R (6x + 2y 2 )dA where R = {(x, y)| - 2 ≤ y ≤ 1, y 2 ≤ x ≤ 2 - y. Q3 ...

Question 1 - many spas many componentsconsider 4 types of

Question 1 - Many spas, many components Consider 4 types of spa tub: Aqua-Spa (or FirstSpa, or P1), Hydro-Lux (or SecondSpa, or P2), ThirdSpa (or P3) and FourthSpa (or P4), with the production of products P1, ..., P4 in ...

Math assignment -q1 let fx -x3-cosx and p0 1 use newtons

Math Assignment - Q1. Let f(x) = -x 3 -cos(x), and p 0 = 1. Use Newton's method to find p 2 . Could p0=0 be used? Q2. Perform two iterations by Newton's method and the secant method to each of the following: a. e x + 2 - ...

Question suppose that g is a directed graph in class we

Question : Suppose that G is a directed graph. In class we discussed an algorithm that will determine whether a given vertex can reach every other vertex in the graph (this is the 1-to-many reachability problem). Conside ...

Question suppose g is an undirected connected weighted

Question : Suppose G is an undirected, connected, weighted graph such that the edges in G have distinct edge weights. Show that the minimum spanning tree for G is unique.

Numerical analysis assignment -q1 define the following

Numerical Analysis Assignment - Q1. Define the following terms: (i) Truncation error (ii) Round-off error Q2. Show that if f(x) = logx, then the condition number, c(x) = |1/logx|. Hence show that log x is ill-conditioned ...

1 this problem concerns of the proof of the np-completeness

(1) This problem concerns of the proof of the NP-completeness of 300L a) Convert the formula F into a 300L graph b) Find a solution for the 300L instance of F and verify that it is a solution for F F = (Z 1 V Z 2 ) ^ (z ...

Assignment - lp problemsthe data for all the problems in

Assignment - LP problems The data for all the problems in this HW are included in the LP_problems_xlsx spreadsheet Problem 1: Cash Planning A startup investment project needs money to cover its cash flow needs. At the en ...