Prove that the minimal spanning tree in graph is unique

Assignment Help Mathematics
Reference no: EM1318401

To prove that the minimal spanning tree in graph is unique.

Suppose you have n video streams that need to be sent, one after another, over a communication link. Stream I consists of a total of bi bits that need to be sent, at a constant rate, over a period of ti seconds. You cannot send two streams at the same time, so you need to determine a schedule for the streams: an order in which to send them. Whichever order you choose, there cannot be any delays between the end of one stream and the start of the next. Suppose you schedule starts at time 0(and therefore ends at time ∑ni=0 ti ,whichever order you chose).we assume that all the values b and ti  are positive integers.

Now, because you are just one user ,the link does not want you taking up too much bandwidth, so it imposes the following constraint ,using a fixed parameter r:

(*) for each natural number t>0,the total number of bits you send over the time interval from 0 to t cannot exceed rt.

Note that this constraint is only imposed for time intervals that start at 0, not for time intervals that start at any other value.

We say that a schedule is valid if it satisfies the constraint (*) imposed by the link.

The problem given a set of n streams, each specified by its number of bits bi and its time duration ti ,as well as the link parameter r, determine whether there exist a valid schedule.

Example: suppose we have n=3 streams, with

(b1, t1)=(2000,1)       (b2, t2)=(6000,2)         (b3, t3)=(2000,1)

and suppose the link's parameter is r=5000.then the schedule that n runs the streams in the order 1,2,3 is valid, since the constant (*) is satisfied:

t=1; the whole first stream has been sent, and 2000<5000

t=2 ; half of the second stream has also been sent and 2000+3000 <5000

Similar calculations hold for t=3 and t=4

consider the following claim :

there exists a valid schedule if and only if each stream I satisfies bi <= rti

Decide whether you think the claim is true or false and give a proof of either the claim or its negation.

Reference no: EM1318401

Questions Cloud

Discretionary right : Emma Employee works as a salesperson. Her company, International Widgets, implements sales incentive program: If any salesperson sells 100 units in July, they will receive a $12,000.00 bonus. International states that the program is discretionary ..
Hypothesis testing with one way anova : Describe appropriate treatment means μ1, μ2 and μ3. After that Test for statistically significant differences between these treatment means. Set α = 0.05.
Collection of the volatile data for investigation : Discuss with others what kinds of the data are considered volatile and the methods through which the investigators should collect and preserve the volatile data. Recognize the consequences of not collecting or preserving the volatile data to the i..
Confidence intervals for your data set : Construct the following confidence intervals for your data set:
Prove that the minimal spanning tree in graph is unique : To prove that the minimal spanning tree in graph is unique and Decide whether you think the claim is true or false and give a proof of either the claim or its negation.
Finding tc with confidence level and sample size : Find the t c for a 90% confidence level with a sample size of 18.
Propose three ways of mentor and new employee : Propose three ways that a mentor and a new employee orientation can assist employees with their career development.
Find the value of x at which the minimum or maximum occurs : Find the value of X at which the minimum or maximum occurs.
Estimating the mean length of time : A physician wanted to estimate the mean length of time  µ  that a patient had to wait to see him after arriving at the office.

Reviews

Write a Review

Mathematics Questions & Answers

  Questions on ferris wheel

Prepare a Flexible Budget Gator Divers is a company that provides diving services such as underwater ship repairs to clients in the Tampa Bay area.

  Logistic map

This assignment has two question related to maths. Questions are related to bifurcation cascade and logistic map.

  Finding the probability of cards

This assignment has questions related to probabiltiy.

  Systems of ode

Find all the xed points, and study their stability and Draw the phase portrait of the system, as well as the graphs of the solutions in all relevant cases.

  Derive the boolean expression

Derive the Boolean Expression and construct the switching circuit for the truth table stated

  System of equations

Evaluate which equations are under-identified, just-identified, and over-identified.

  Linear programming problem

Linear programming problem consisting of only two constraints with one objective function.

  Find the natural domain

Find the natural domain of the given functions.

  Introduction to numerical methods

Compute the coecients of the polynomials using the term recurrence relation.

  Chart of the topological manifold

De?nition of smoothness of functions on a smooth manifold is chart independent and hence geometric.

  Mathematics in computing

Questions related on mathematics in computing.

  Complex problems

Complex problems

Free Assignment Quote

Assured A++ Grade

Get guaranteed satisfaction & time on delivery in every assignment order you paid with us! We ensure premium quality solution document along with free turntin report!

All rights reserved! Copyrights ©2019-2020 ExpertsMind IT Educational Pvt Ltd