Exam May 2016, answers PDF

Preview

Summary

ECM3722 Summer Exam 2016 Solutions Barrie Cooper February 19, 2016 Section A 1. This section is entirely bookwork, consisting of results from lecture notes or exercise sheets. (a) Let G be a finite graph and let i and j be vertices of G. Let A be an adjacency matrix for G. i. What does it mean to sa...

Description

ECM3722 Summer Exam 2016 Solutions Barrie Cooper February 19, 2016

Section A 1. This section is entirely bookwork, consisting of results from lecture notes or exercise sheets. (a) Let G be a finite graph and let i and j be vertices of G. Let A be an adjacency matrix for G. i. What does it mean to say that vertices i and j are adjacent? ii. What does it mean to say that G is connected? iii. Let n ∈ N. Prove that the (i, j)th entry of An is equal to the number of paths of length n from vertex i to vertex j . iv. Hence prove that G is connected if and only if the matrix I + A + A2 + · · · + Ak−1 contains only positive entries, where k is the number of vertices in G.

(15)

SOLUTION i. Vertices i and j are adjacent iff there is an edge with endpoints i and j. (1) ii. A graph G is connected iff there is a path between every pair of distinct vertices. (1) iii. We proceed by induction on n. By definition the adjacency matrix A = A1 lists the number of paths of combinatorial length 1 (edges) from vertex i to vertex j as its (i, j)th entry. Suppose that the result is true for paths up to length k. Now, a path of length k + 1 from vertex i to vertex j can be thought of as a path of length k from vertex i to some intermediate vertex p followed by a path of length 1 (edge) from vertex p to vertex j. Summing over p gives the number of paths of length k + 1 from vertex i to vertex j : X (Ak )ip Apj = (Ak+1 )ij , p

(b)

by the definition of matrix multiplication. iv. Suppose that the matrix I + A + A2 + · · · + Ak−1 has strictly positive entries. Let i 6= j be two vertices. We must show that there is a path between i and j. Now, the (i, j)th entry of the above sum is positive and since each of the component matrices in the sum is non-negative, we know that there must be some 1 ≤ n ≤ k − 1 for which the (i, j)th entry of An is positive. But this means there are Ani,j paths of combinatorial length n between i and j. Hence G is connected.

(4)

Conversely, suppose that G is connected. Fix vertices i and j. Since G has k vertices, at worst you must travel through every vertex to get from i to j, which gives a path of combinatorial length at most k − 1. Now, each matrix An for 0 ≤ n ≤ k − 1 counts the number of paths of combinatorial length n between each pair of vertices and hence each entry is non-negative. We consider the (i, j)th entry of the sum I + A + A2 + · · · + Ak−1 . Now, we know that since G is connected, there exists a path of combinatorial length n from i to j, for some 0 ≤ n ≤ k − 1. Hence the (i, j)th entry of An is positive and hence the (i, j)th entry in the sum is positive also, as required.

(4)

i. What does it mean to say that a graph is planar? 1

(5)

ii. State and prove Euler’s formula for finite connected planar graphs. iii. Hence prove that K3,3 is not planar. iv. How should Euler’s formula be modified if the graph is finite and planar, but not necessarily connected? v. How should Euler’s formula be modified if the graph is finite and connected, but not necessarily planar?

(15)

SOLUTION i. A graph is planar if it can be drawn in the plane in such a way that its vertices are distinct points and its edges do not meet except at their endpoints (or more colloquially, if it can be drawn in the plane without its edges crossing). ii. Euler’s formula states that for a finite planar connected graph, v − e + f = 2, where v is the number of vertices, e is the number of edges and f is the number of faces. We proceed by induction on the number of vertices and edges. The simplest case is that of a graph with 1 vertex, 0 edges and 1 face. This certainly satisfies

(2)

v−e+f =1−0+1=2. Now, all finite connected planar graphs can be constructed by introducing new edges between existing vertices and introduce new vertices that are attached to existing vertices. Suppose therefore that the formula holds true for finite connected planar graphs with V vertices, E edges and F faces. Adding an edge produces a graph with V vertices, E + 1 edges, but F + 1 faces because the edge must partition an existing face into two. Hence our new graph satisfies V − (E + 1) + (F + 1) = V − E + F = 2 . Adding a vertex instead, requires us to add an edge in order that the resulting graph remain connected and there is no change in the number of faces, hence, (V + 1) − (E + 1) + F = V − E + F = 2 . Both procedures preserve the formula, hence we can conclude by induction that Euler’s formula holds for all finite connected planar graphs. iii. Let κ denote the number of connected components of G, and let v, e and f denote the number of vertices, edges and faces respectively. Then

(7)

v−e+f =1+κ. (3) iv. (Note that if the graph isn’t planar, you have to have more information to determine what constitutes a face — we did this by defining ribbon graphs to be graphs with a cyclic ordering of half-edges at each vertex, thereby uniquely defining faces and a canonical embedding into a surface of minimal genus g.) Let g denote the genus of the graph and let v, e and f denote the number of vertices, edges and faces respectively. Then, v − e + f = 2 − 2g . (3)

(c)

i. ii. iii. iv. v. vi.

State the definition of the complexity classes P and N P . State the definition of a vertex colouring of a graph. State the definition of the chromatic number of a graph. State the greedy colouring algorithm for finding a vertex colouring of a finite graph. Derive an upper bound for the complexity of the greedy colouring algorithm. Does the greedy colouring algorithm demonstrate that the problem of computing the chromatic number of a finite graph is in complexity class P ? SOLUTION 2

(20)

i. The complexity class P consists of all the problems that can be solved by a polynomial-time algorithm on a deterministic Turing machine. The complexity class N P consists of all the problems that can be solved by a polynomial-time algorithm on a non-deterministic Turing machine. (4) ii. A vertex colouring is the assignment of a colour to each vertex of the graph in such a way that adjacent vertices possess different colours. (2) iii. The chromatic number is the smallest number of colours needed for a vertex colouring of the graph to exist. (1) iv. The greedy colouring algorithm can be stated as follows: A. Given a non-empty loop-free graph G = (V, E, ε); initialise a set T = ∅ of coloured vertices, a function f : T → N representing the colouring, and a set C = ∅ giving the colours of the neighbours for the vertex under consideration. B. If T = V then stop and return the function f . Otherwise, choose v ∈ V \ T . C. Replace C by {f (u) : u ∼ v and u ∈ T }. D. Replace T by T ∪ {v} and define f (v) = min N \ C . E. Go to Step B. (6) v. The complexity of the greedy colouring algorithm is O(|V |2 ). The complexity is certainly at least O(|V |) since I take each vertex one at a time. But now, for each chosen vertex v I have a subroutine that computes the new value of C and the new value of f (v). Each of these tasks has complexity O(|V |). These two computations are not nested so the complexity of the whole subroutine is still O(|V |), whence the result. (4) vi. No. The greedy colouring algorithm is a heuristic not an exact algorithm. In particular, it does not guarantee to find an optimal solution to the vertex colouring problem. (3)

[50]

Section B 2. Let f : {finite graphs} → S be a function that takes a finite graph as an input and produces an output in some set S. We say that f is an invariant if f (G) = f (G′ ) whenever graphs G and G′ are isomorphic. (a) Which of the following are well-defined invariants? Justify each answer carefully. i. the number of vertices; iii. the chromatic polynomial; v. the Perron-Frobenius eigenvalue.

ii. the adjacency matrix; iv. the dual graph;

SOLUTION This question is unseen, but the students have seen all the terms used as part of the course. i. Yes, isomorphic graphs must have the same number of vertices. In particular, an isomorphism of graphs is a pair of bijections mapping vertices to vertices and edges to edges that respect endpoints. ii. This is not well-defined. In general, the adjacency matrix of a graph is not unique as it depends on the ordering of the vertices. iii. Yes, if two graphs G and G′ are isomorphic, then every vertex colouring of G corresponds uniquely to a vertex colouring of G′ and vice versa. iv. This is not well-defined. The dual depends not only on the structure of the graph, but on the embedding also and in particular, choosing a different embedding can give rise to non-isomorphic duals. v. Yes, if G and G′ are isomorphic, then every function on G corresponds uniquely to a function on G′ and vice versa. In particular, the result of applying the adjacency operator to any function depends purely on how the vertices are connected to each other, which is preserved by isomorphism.

3

(10)

(b) For each of the well-defined invariants f in question 2a, find non-isomorphic graphs G and G′ that satisfy f (G) = f (G′ ). SOLUTION Bookwork — we have seen all these examples, although not strictly in this context. i. The complete graph K4 and the cycle graph C4 both have four vertices, but are not isomorphic. In particular, they don’t have the same number of edges. iii. Every tree with n vertices has chromatic polynomial P (t) = t(t − 1)n−1 , but they are not isomorphic in general e.g. the Dynkin graphs A4 and D4 . v. Every cycle graph has Perron-Frobenius eigenvalue 2 (a corresponding eigenvector consists of a 1 at each vertex), but cycle graphs with a different number of vertices are not isomorphic e.g. C3 and C4 .

(9)

Suppose that G has n vertices and let d 1 ≤ d 2 ≤ · · · ≤ d n be the ordered list containing the degree of each vertex in G. We call the sequence (d i ) the degree sequence of G. (c) Is the degree sequence a well-defined invariant? SOLUTION Unseen — we have not covered this topic this year. Yes, since isomorphisms map vertices to vertices and edges to edges whilst respecting endpoints, they must preserve degree.

(2)

(d) Are there non-isomorphic graphs G and G′ with the same degree sequence? Give a proof or counterexample to justify your answer. SOLUTION Unseen. Yes, a straightforward solution is to consider C4 (the cycle graph with four vertices) and the graph consisting of two copies of C2 . Both have degree sequence (2, 2, 2, 2), but C4 is connected whereas the other graph is not. (If we want to restrict ourselves to simple connected graphs, there are plenty of examples.)

(4)

[25] 3. Let G be a finite connected graph with vertex set V and edge set E. Let RV = {φ : V → R} denote the set of real-valued functions on the vertices of G. Consider the inner product on RV given by X φ(i)ψ(i) . hφ, ψi = i∈V

(a) State the definition of a Schr¨ odinger operator on G. SOLUTION Bookwork. A Schr¨odinger operator on G is a linear map A: RV → RV satisfying: • A is symmetric (for the given inner product on RV ); • if there is no edge in G connecting vertices i and j and i 6= j then aij = 0; • if there is an edge in G connecting vertices i and j then aij < 0.

4

(5)

(b) State the Perron-Frobenius Theorem for Schr¨ odinger operators on a finite connected graph. SOLUTION Bookwork. Let G be a finite connected graph and let A be a Schr¨ odinger operator on G. Then the smallest eigenvalue λ1 of A is simple (that is, it has multiplicity 1) and the eigenspace Eλ1 is generated by an eigenvector that takes strictly positive values everywhere.

(4)

(c) What is meant by the Perron-Frobenius eigenvalue for G? SOLUTION Bookwork. The largest eigenvalue of the adjacency operator for G.

(2)

(d) Suppose that H is a finite connected subgraph of G. Let λ denote the Perron-Frobenius eigenvalue for G and let µ denote the Perron-Frobenius eigenvalue for H . Prove that λ ≥ µ. SOLUTION Unseen. Note that − adj is a Schr¨odinger operator. By the Perron-Frobenius Theorem, the largest eigenvalue of G and of H is simple and is generated by an eigenvector that takes strictly positive values everywhere. We have seen in lectures that the Perron-Frobenius eigenvalue is the maximum value obtained by hadj(φ), φi where kφk = 1. Therefore, if µ is the Perron-Frobenius eigenvalue for H , let φ be a Perron-Frobenius eigenvector for H with kφk = 1. We can extend φ to a function φ on G (if necessary) by declaring the value on vertices not in H to be zero. Now, kφk = 1 also and µ = max{hadjG ψ, ψi : kψk = 1} ≥ hadjG (φ), φi ≥ hadjH (φ), φi = hλφ, φi = λhφ, φi = λ . (10)

(e) What is the analogous result for Schr¨ odinger operators on G and H ? SOLUTION Unseen. Suppose that B is a Schr¨ odinger operator on G extending the Schr¨ odinger operator A on H . Let λ be the Perron-Frobenius eigenvalue of B and let µ be the Perron-Frobenius eigenvalue of A. Then λ ≤ µ.

(4)

[25] 4. Figures 1 and 2 show portions of two electrical networks.

A γ

β

C α

B Figure 1: A star.

Figure 2: A triangle. 5

(a) Show that if you replace the star in Figure 1 with the triangle in Figure 2 in an electrical network, then the current flowing and the potential differences between the vertices does not change provided the edge labels represent resistance and we define α=

AB + BC + CA , A

β=

AB + BC + CA , B

γ=

AB + BC + CA . C

SOLUTION We have seen the star-triangle transform, but the proof of the result is unseen. Since solutions are unique, it suffices to show that for the same current flowing and the same potential at each vertex, the resistances stated for the triangle satisfy the required set of equations. We draw diagrams representing current and potential.

1

1−f f 1−e f −e

e Figure 3: Current flowing in the star.

Figure 4: Current flowing in the triangle.

Va

Va

Vv Vb

Vb

Vc

Figure 5: Potentials in the star.

Vc

Figure 6: Potentials in the triangle.

Without loss of generality, we can assume Vc = 0. We now use Ohm’s law to write a system of linear equations, one for each edge: Va − Vv = A

Va = (1 − f )β

Vv − Vb = eB Vv = (1 − e)C

Va − Vb = f γ Vb = (f − e)α

We eliminate Vv in the left-hand system of equations, and f in the right-hand system of equations, to get Va = A + (1 − e)C

γVa = (γ − Va + Vb )β

Vb = (1 − e)C − eB

γVb = (Va − Vb − γe)α

We rearrange the right-hand side system to get Va (β + γ) − βVb = βγ Va α − Vb (α + γ) = eαγ Substituting in the expressions for Va and Vb from the left-hand system of equations and writing S = AB + BC + CA yields for the first equation (A + (1 − e)C)(β + γ) − β((1 − e)C − eB) = βγ

⇔ ⇔ ⇔

6

Aβ + Aγ + (1 − e)C γ + βeB = βγ AS AS + (1 − e)S + eS = βγ + C B ACS + ABS + AC S = βγBC = S 2 .

Hence the first equation holds. For the second equation we consider α(A + (1 − e)C) − (α + γ)((1 − e)C − eB) = eαγ

⇔

αA − (1 − e)γC + eBγ + eBα = eαγ eBS eBS + = eαγ S − (1 − e)S + C A eACS + eABS + eBC S = eαγAC = eS 2

⇔ ⇔

Hence the second equation holds also. We have shown therefore that replacing the star with the triangle with the specified resistances, does not change the current flowing or the potential difference between each pair of vertices.

(12)

(b) Prove that the inverse transformation from triangle to star is given by A=

αβ + βγ + γα , α

B=

αβ + βγ + γα , β

C=

αβ + βγ + γα , γ

provided we interpret the edge labels as conductances. SOLUTION The proof is unseen, but the students have seen the triangle-star transformation. By symmetry, it suffices to check the result for a single edge. Note that if I start with an edge with resistance A, this is transformed to an edge with resistance α. This has conductance 1/α, which is transformed to the edge with conductance A′ =

1 αβ

1 + βγ + 1 α

1 γα

=

α+β+γ = βγ

S A

+

S B

βγ

+ CS

=

1 S2 = , ABCβγ A

as required.

(6)

(c) Briefly explain the correspondence between electrical networks and rectangle tilings. SOLUTION Bookwork. Suppose I cut a rectangle from a material with a high resistance and arrange so that there is a potential difference between the top edge and bottom edge. Then a current will flow, say from top to bottom, proportional to the width of the rectangle. This current will not be disturbed if I cut some vertical slits in the material. Moreover, the potential difference between a point of the rectangle and the bottom will be proportional to the height of the point. In particular, all points on a horizontal line have the same potential, so I can short these by inserting horizontal rods of infinite conductance. A rectangle tiling is one such way of cutting vertical slits and horizontal rods in my large rectangle. In such a diagram, the small rectangles are acting as “wires” carrying current between the horizontal rods (“vertices”). Choosing an appropriate scale for measuring the height and width of our rectangles, the height of each rectangle is equal to the potential drop and its width is equal to the current. In particular, the resistance of a rectangle is equal to its height divided by its width.

(7)

[25]

7...