Exam 13 2017, questions PDF

Preview

Summary

Download Exam 13 2017, questions PDF

Description

MATH39001 TWO HOURS

THE UNIVERSITY OF MANCHESTER

Diagram for Question 2 to be provided by the School of Mathematics. COMBINATORICS AND GRAPH THEORY DATE: 26 January, 2017 TIME: 09:45–11:45 Answer THREE of the FOUR questions. If more than THREE questions are attempted, then credit will be given for the best THREE answers.

Electronic calculators may be used, provided that they cannot store text/transmit or receive information/display graphics.

P.T.O. Page 1 of 5

MATH39001 1. (a) Give the definition of a spanning tree of a simple graph G. (b) State without proof the Matrix Tree Theorem. (Either version given in the course is sufficient.) (c) An electrical network is represented by a connected graph G with a resistance Re > 0 assigned to each edge e and with two distinguished vertices, a source s and a sink t. Describe without proof the method of spanning trees used to calculate the currents in the edges of G assuming that the electric potential difference U between s and t is known. (d) The graph below represents an electrical network, where s is the source, t is the sink. The resistances of the edges in appropriate units are as shown on the graph.

It is known that the current in the edge bt flowing from b to t is Ibt = 1. Use the method of spanning trees to calculate the currents Isa and Ibc. (You may use without proof the fact that this graph has 8 spanning trees.) (e) Let δ ≥ 3 and g ≥ 3 be integers and assume that g is odd. Let G be a graph in which every vertex has degree at least δ and which contains no cycle of length less than g. Prove that G has at least 1+

δ((δ − 1)(g−1)/2 − 1) δ−2

vertices. [20 marks] Page 2 of 5

MATH39001 2. (a) Let G = (V, E) be a directed graph with two distinguished vertices, namely a source s and a sink t, and with a capacity c(x, y) > 0 assigned to → xy. each edge − (i) Define the notion of a flow in G and the value of a flow. (ii) Let f be an arbitrary flow in G and let S, T be any cut. Prove that v(f ) ≤ c(S, T ). (c) In the graph below, the numbers in parentheses show the capacities of the edges. Find a maximal flow between s and t in this graph and show that it is indeed maximal by finding a minimal cut. At each step, indicate clearly the current flow, the path along which you are increasing the flow and the amount by which you are increasing the flow and also show how you find the minimal cut. (Use the diagrams distributed on a separate sheet for solving this part of the question and attach it to your answer booklet.)

(d) Let G = (V, E) be a directed graph with a source s and a sink t. Let c1 , c2 : E → R be capacities for the edges of G and let c be the capacity − → defined by c(x, y) = c1 (x, y) + c2 (x, y) for any edge xy. Let M1 , M2 and M be the maximum of the values of the flows in G with capacities c1 , c2 and c, resp. Show that if f1 : E → R is a flow for the capacities c1 and f2 : E → R is a flow for the capacities c2 , then f : E → R defined by f (x, y) = f1 (x, y) + f2 (x, y) is a flow for the capacities c. Deduce that M ≥ M1 + M2 . Explain briefly how it can happen that M > M1 + M2 . [20 marks] Page 3 of 5

MATH39001 3. (a) Give the definition of the ordinary power series generating function of ∞ . a sequence {an }n=0 (b) (i) Let f (x) be the ordinary power series generating function of the sequence {an }∞ n=0 . Show that the ordinary power series generating function of ′ the sequence {nan }∞ n=0 is xf (x). (ii) Calculate the ordinary power series generating function of the sep(x) quence {n2 5n }∞ , where p(x), q(x) are n=0 . Write your answer in the form q(x) polynomials. ∞ ∞ (c) Let the sequences {an }n=0 and {bn }n=0 have ordinary power series generating functions f (x) and g(x), respectively. Show that f (x)g (x) is the n P ∞ ordinary power series generating function of the sequence ak bn−k n=0 . k=0

∞ (d) The sequence {cn }n=0 is defined by c0 = 1, c1 = 5 and the recurrence relation cn+2 = 7cn+1 − 12cn

for n ≥ 0. Let h(x) be the ordinary power series generating function of {c n }∞ n=0 . 1 − 2x (i) Show that h(x) = , and by decomposing h(x) into (1 − 3x)(1 − 4x) partial fractions or otherwise, find an explicit formula for cn in terms of n. n X (ii) Let tn = 2n−k ck for n ≥ 0. Express the ordinary power series k=0

generating function of the sequence {tn }∞ n=0 in terms of h(x). Use generating functions to prove that the identity 2cn − tn = 3n holds for all integers n ≥ 0. [20 marks]

Page 4 of 5

MATH39001 4. (a) Give the definition of the exponential generating function of the sequence {an }∞ n=0 . ∞ is f (x), then (b) Prove that if the exponential generating function of {an }n=0 ′ ∞ f (x) is the exponential generating function of {an+1 }n=0 and xf ′ (x) is the ∞ . exponential generating function of {nan }n=0 ∞ (c) Calculate the exponential generating function of the sequence {n2 4n }n=0 . ∞ is defined by c0 = 3, c1 = 8 and the recurrence (d) The sequence {cn }n=0 relation cn+2 = 5cn+1 − 6cn ∞ . By for n ≥ 0. Let h(x) be the exponential generating function of {cn }n=0 taking the exponential generating function of both sides of the recurrence relation, find an ordinary differential equation satisfied by h(x), solve it and hence prove that cn = 2n + 2 × 3n for every n ≥ 0. ∞ (e) Let {an }∞ n=0 and {bn }n=0 be sequences. Let f (x) be the exponential gen∞ erating function of the sequence {an }∞ n=0 , g(x) that of the sequence {bn }n=0 . Show  n that f (x)g ∞(x) is the exponential generating function of the sequence P n . ak bn−k k k=0

n=0

∞ be a sequence with exponential generating function p(x). Let (f) Let {dn }n=0 n   P n (−1)k dn−k for n ≥ 0 and let q(x) be the exponential generating fn = k k=0

∞ . function of {fn }n=0 (i) Show that q(x) = e−x p(x). n   P n (ii) Prove that dn = f for n ≥ 0. k k k=0

END OF EXAMINATION PAPER.

Page 5 of 5

[20 marks]...