Q1(a) How many spanning trees are there for the graph G in figure below (3pt) Two trees are edge disjoint if they have no edges in common Q1(b) For G e , the graph G with vertex e deleted, draw two spanning trees that are edge disjoint (4pt) Q1(c) For G e with edge ( a , d ) deleted, prove that there cannot be two edge disjoint spanning trees (4pt) Q2(a) Prove every tree with n 2 vertices has at least 2 leaves (4pt) Q2(b) Let T be a tree Prove if all vertices have degree either 1 or at least 4, then T has at least 2( n 1) 3 leaves (5 pt) Q3 Determine whether each of the following graphs has a Hamilton circuit If it does, identify the Hamilton circuit in the graph, making sure to clearly label the vertices If it does not, give an argument to show why no Hamilton circuit exists (3 pt each) Q4 Suppose an n vertex bipartite graph G has exactly k connected components, each of which has two or more vertices How many ways are there to color G using a given set of two colors (7 pt) Q5 In the game of dominoes we have a collection of domino tiles, which are rectangular tiles with two numbers on them, one on each end An arrangement of the dominoes in a line is valid if adjacent numbers are equal For example, given dominos (0, 1), (0, 3), (0, 4), (1, 3), we can arrange them in a valid line (0, 1)(1, 3)(3, 0)(0, 4) (a) A ( i , j ) domino is a domino tile with numbers i and j on it Given a set of 100 dominoes with numbers i and j , where 1 i 10 and 11 j 20 , show that it is possible to arrange all 100 dominoes in a valid line (2 pt) (b)Suppose that one of these 100 dominos is missing Show that it is still possible to arrange all of the remaining dominos in a valid line (3 pt) (c) What if two dominos are missing Can we still arrange the rest in a valid line Prove your answer (5 pt) Q6 Suppose an investor wants to invest a certain amount of his assets, worth $ dollars, into a particular stock After enough statistical analysis of the history of the stock, the investor believes that a good model for how the stock will behave for the next few days or weeks is that, for every second, the probability that the stock fluctuations yield an increase of one in the value he currently has invested is u and the probability that it decreases by one is d (where u d 1) The investor sets up an automatic trader software that will automatically sell all of his stock as soon as the value he has invested in this stock reaches a limit value L Our goal is to compute the probability that the stock achieves the limit valuation To that end, let V t be a random variable giving the valuation of the investor's stocks after t seconds have passed We can define the time it takes for the investor either to go broke or to have his stocks sold by the autotrader as T min t V t 0 or V t L It turns out that T is finite this means that it is never the case that the stock will fluctuate between 0 and L of valuation forever (namely, the event that it fluctuates forever with never going broke or reaching the limit value has 0 probability i e , P ( T ) 1) Now we want to compute the following p $ P ( V t L V 0 $), namely, the probability that, given that the investor starts with $ value in assets invested in this stock, they end up with the limiting value (a) What are the values of p 0 and p L (3 pt) (b) Write recurrence for p $ (3 pt) (c) Solve the recurrence (for simplicity, assume that u d ) Your final solution should give p $ depending only on u (or d ), $, and L Hint Is it a linear homogenous equation (7 pt)

The Answer is in the image, click to view ...

Answered step by step

Verified Expert Solution

Link Copied!

Question

1 Approved Answer

Posted on Oct 12, 2024

Q1(a). How many spanning trees are there for the graph G in figure below? (3pt) Two trees are edge-disjoint if they have no edges in

Q1(a). How many spanning trees are there for the graphGin figure below? (3pt)

Two trees areedge-disjointif they have no edges in common.

Q1(b). ForGe, the graphGwith vertexedeleted, draw two spanning trees that are edge-disjoint. (4pt)

Q1(c). For G ewith edge (a,d) deleted, prove that there cannot be two edge-disjoint spanning trees. (4pt)

Q2(a). Prove: every tree withn 2 vertices has at least 2 leaves. (4pt)

Q2(b). LetTbe a tree. Prove: if all vertices have degree either 1 or at least 4, thenThas at least 2(n+ 1)/3 leaves. (5 pt)

Q3. Determine whether each of the following graphs has a Hamilton circuit. If it does, identify the Hamilton circuit in the graph, making sure to clearly label the vertices. If it does not, give an argument to show why no Hamilton circuit exists. (3 pt each)

Q4. Suppose ann-vertex bipartite graphGhas exactlykconnected components, each of which has two or more vertices. How many ways are there to colorGusing a given set of two colors? (7 pt)

Q5. In the game of dominoes we have a collection of domino tiles, which are rectangular tiles with two numbers on them, one on each end. An arrangement of the dominoes in a line isvalidif adjacent numbers are equal. For example, given dominos (0, 1), (0, 3), (0, 4), (1, 3), we can arrange them in a valid line (0, 1)(1, 3)(3, 0)(0, 4).

(a) A (i,j) domino is a domino tile with numbersiandjon it. Given a set of 100 dominoes with numbersiandj, where1 i 10and11 j 20, show that it is possible to arrange all 100 dominoes in a valid line. (2 pt)

(b)Suppose that one of these 100 dominos is missing. Show that it is still possible to arrange all of the remaining dominos in a valid line. (3 pt)

Q6. Suppose an investor wants to invest a certain amount of his assets, worth $ dollars, into a particular stock. After enough statistical analysis of the history of the stock, the investor believes that a good model for how the stock will behave for the next few days or weeks is that, for every second, the probability that the stock fluctuations yield an increase of one in the value he currently has invested isuand the probability that it decreases by one isd(whereu+d= 1). The investor sets up an automatic trader software that will automatically sell all of his stock as soon as the value he has invested in this stock reaches a limit valueL.

Our goal is to compute the probability that the stock achieves the limit valuation. To that end, letV_tbe a random variable giving the valuation of the investor's stocks aftertseconds have passed. We can define the time it takes for the investor either to go broke or to have his stocks sold by the autotrader asT= min {t:V_t= 0 orV_t=L}. It turns out thatTis finite; this means that it is never the case that the stock will fluctuate between 0 andLof valuation forever (namely, the event that it fluctuates forever with never going broke or reaching the limit value has 0 probability; i.e.,P(T< ) = 1). Now we want to compute the following:p_$=P(V_t=L|V₀= $), namely, the probability that, given that the investor starts with $ value in assets invested in this stock, they end up with the limiting value.

(a) What are the values ofp₀andp_L? (3 pt)

(b) Write recurrence forp_$. (3 pt)

(c) Solve the recurrence (for simplicity, assume thatud). Your final solution should givep_$depending only onu(ord), $, andL. Hint: Is it a linear homogenous equation? (7 pt)