Wksh 2 and 3 – some solutions

http://www.alastairfarrugia.net/GT-worksheet-2-and-3.pdf

Linear Algebra – Jan 2006 – qn. 6 – partial solution

lin-alg.pdf

Sheet 3, no. 1

Sheet 3, no. 1
a) Show that if G is Eulerian, then its line-graph L(G) is Hamiltonian.

a) If G is Eulerian then it has an Eulerian tour, i.e. a sequence of vertices

v_1, v_2, …, v_r = v_1, such that:
for each i, v_i v_{i+1} is an edge of G;
and each edge of G appears once and only once.

Thus v_1 v_2, v_2 v_3, …, v_{r-1} v_r is a listing of the edges of G such that:
each edge has a vertex in common with the next one (and the last edge has a vertex in common with the first edge)
each each edge appears once and only once.
This is thus a Hamiltonian cycle of L(G).
b) Show that if G is Hamiltonian, then its line-graph L(G) is Hamiltonian.

b) If G is Hamiltonian, then it has a Hamiltonian cycle, i.e. a sequence of vertices

v_1, v_2, …, v_n such that:
each vertex appears once and only once
each vertex is adjacent to the next one (and the last is adjacent to the first).

Now we can visit all the edges of G in the following sequence:

Step 1. all edges of the form v_1 v_j (n > j > 2)
Step 1′. v_1 v_2
Step 2. all edges of the form v_2 v_j (j > 3)
Step 2′. v_2 v_3
Step 3. all edges of the form v_3 v_j (j > 4)
Step 3′. v_3 v_4
…
Step n_1′. v_{n-1} v_n
Step n’. v_n v_1

Note that every edge is of the form v_i v_j, for some i < j.

This edge will be be visited in step i (if j > i+1) or step i’ (if i = i+1). So every edge is visited
exactly once.

Also, all the edges in step i or i’ are adjacent because they have vertex i in common;
the edge in step i’ has vertex i+1 in common with the edges in steps i+1 and i+1′;
and the edge in step n’ has vertex 1 in common with the edges in steps 1 and 1′.

So each edge is adjacent to the next edge, thus giving us a Hamiltonian cycle in L(G).

Give examples to show that the converse of a) is false, and the converse of b) is false.

One example is actually enough.

Consider the star K_1,3 (i.e. vertices v,a,b,c and edges va,vb,vc).

This graph has no cycles, so it is not Eulerian or Hamiltonian.

However its line-graph is K_3, which is both Eulerian and Hamiltonian.
This shows that the converse of a) and b) is false.

Sheet 2, no. 6

Sheet 2, no. 6:
Let G be connected.

How many components are left when we remove a lambda set of separating edges?

How many components are left when we remove a kappa-set of separating vertices? 

Removing a minimum separating set of edges will result in 2 components (seeproof below).

For separating sets of vertices, consider the star K_1,r (one vertex v connected to r other vertices). Removing v will leave r isolated vertices (so we have r components), and r can be as large as we want, so there is no bound on the number of components.

Now let’s give an actual proof that removing a minimum separating set of edges will result in just 2 components.
First consider the case lambda = 1, i.e. the graph has some cut-edge uv.
Now G – uv is disconnected, but by adding just one edge (between u and v) we must get the connected graph G. A single edge uv can only join two components together (the component that contains u and the component that contains v). So G-uv cannot have more than 2 components.

For lambda > 1, let A be a separating set of lambda edges, let e be one of the edges of A, and define A’ := A \ {e}. (So A = A’ union {e}).
Note that A’ is too small to be a separating set (since |A’| = lambda – 1), so G-A’ is still connected. But now, removing edge e will disconnect the graph, since (G-A’)-{e} = G-A.
So the edge e is a cut-edge in G-A’, and as we saw above, (G-A’)-{e} must have only 2 components; that is, G-A has only 2 components.

Sheet 2, no. 4

Sheet 2, no. 4:
Let G be a connected graph with n >= 3 (n is the number of vertices of G).
Show that if G has a cutedge, then it has a cutvertex.

Let xy be a cutedge. So G – xy has 2 components (see qn. 6 for the proof that there are exactly 2 components).
Let A be the component that contains vertex x, and B the component that contains vertex y.
Since G (and thus, G-xy) has at least 3 vertices, A and B cannot both contain just one vertex. Without loss of enerality, A must contain at least 2 vertices, i.e. x nd at least one other vertex v.

Now note that removing the vertex x also removes the edge xy, so in G-x, the vertices v and y must be in different components. Thus G-x is disconnected, that is, x is a cut-vertex.

Show by an example that the converse is false.

For the converse, consider two triangles with a common vertex v (i.e. the graph has vertices a,b,v,x,y and edges ab,bv,va and xy,yv,vx).

Then v is a cut-vertex, but there is no cutedge (i.e. removing any edge leaves a connected graph).

Lin. Algebra – Feb. 2007 – 1a) and 1c)

MAT 3105 -Feb. 2007

1. a) Show that the min. poly. m_T(x) of a lin. trans. T is unique and divides any polynomial annihilated by T.

m_T(x) is defined as a polynomial
a_s x^s + … + a_1 x + a_0
such that m_T(T) = 0, a_s = 1, and s is minimum.

Suppose that p(T) = 0, and p has degree d.
We can scale so that p has leading co-efficient 1.
Then, by definition of m_T, s <= d.
The division algorithm for polynomials tells us that there are polynomials q and r such that:
p = mq + r, and 0 <= deg(r) < s.

Now 0 = p(T) = m(T)q(T) + r(T) = 0 q(T) + r(T) = r(T)
So r(T) = 0, and since s is the lowest positive degree of any polynomial such that r(T) = 0, we must have deg(r) = 0.
Thus m divides p exactly.

Moreover, if p is also a min. poly. for T, then:
deg(p) = deg(m) ===> deg(q) = 0, so q is just some constant k.

p and m both have leading co-efficient 1, so k = 1.
Thus p = m, that is, the definition gives us a unique m.

If u is an eigenvalue of T, show that u is a root of m_T(x) = 0.

For the last part, “u is an eigenvector of T” means that Tv = uv, for some non-0 vector v.

Then T^2 v = T(Tv) = T(uv) = u (Tv) = U^2 v, and in general, for all natural numbers n, T^n v = u^n v.

Then m(T)v = a_s T^s v + … + a_1 Tv + a_0 v
= a_s u^s v + … + a_1 u v + a_0 v
= (a_s u^s + … + a_1 u + a_0) v
= m(s) v.

Now m(T) = 0 means that m(T) v = 0,
so m(s) v = 0
and since v is non-0 we have m(s) = 0.

1. c)
If A = (5 -2 // 3 -2) determine the matrix P that

diagonalises A under a similarity operation.

[I use // to denote a newline.]

We want a P such that P’AP is diagonal, where P’ is the inverse of P.
P is the matrix of eigenvectors of A.
Now to find the eigenvectors:
(i) find the eigenvalues using |A – kI| = 0
(ii) solve Av = kv, where k is an eigenvalue

(i) The determinant |A-kI| is:

|5-k -2|
!3 -2-k|

= (5-k)(-2-k) – (-6)
= -[(5-k)(2+k) - 6]
= -[10 +3k - k^2 -6]
= -[k^2 -3k -4]
= -(k-4)(k+1)

So the eigenvalues are k = 4 and k=-1.

(ii) We want to solve Av = kv. Let v = (x // y).

We get:

5x – 2y = kx
3x – 2y = ky

(5-k)x – 2y = 0
3x – (2+k)y = 0

(5-k)x = 2y
3x = (2+k)y

When k=4, we have:
x = 2y
3x = 6y, i.e. x = 2y

so v_4 = (2 // 1)

When k=-1, we have:
6x = 2y, i.e. 3x = y
3x = y

so v_{-1} = (1 // 3)

Thus, one possible P is
(2 1)
(1 3)

with inverse
P’ = 1/5 (3 -1)
(-1 2)

and we can check that P’AP = (4 0)
(0 -1)

[Note: There are at least two ways of getting different matrices P (which will of course mean that P' will be different too).
First, if v is an eigenvector with eigenvalue k, then so is rv, where r is a non-zero scalar. So we could multiply a column of P by any non-0 r.
Second, we could change the order of the columns of P, which in this case will lead to the following diagonal matrix:
(-1 0)
(0 4)
]

Solve A(x_n // y_n) = (x_{n+1} // y_{n+1}) for
(x_0 // y_0) = (3 // -1).

We are given the equation:
A w_n = w_{n+1}, where w_0 is (3 // -1)

To solve the equation, we note that the eigenvectors v_4

and v_{-1} form a basis of R^2.
So we can write w_0 = a v_4 + b v_{-1}
or equivalently w_0 = P (a // b)
so that P’ w_0 = (a // b)

Now P’ w_0 = (2 // -1),
so a = 2 and b = -1, that is:
w_0 = 2 v_4 + (-1) v_{-1}.

Now the equation defines w_n as follows:
w_n = A^n w_0
so w_n = A^n (2 v_4 + (-1) v_{-1})
= 2 A^n v_4 + (-1) A^n v_{-1}
= 2 4^n v_4 + (-1) (-1)^n v_{-1}
= 2 4^n (2 // 1) + (-1)^{n+1} (1 // 3)
= (x_n // y_n)

where x_n = 4^{n+1} + (-1)^{n+1}
and y_n = 2 4^n + 3 (-1)^{n+1}.

4 questions from sheets 2 and 3

gt-solutions.pdf

Networks exam

Dr. Peter Borg told me that, for the exam, you are not required to know the proof that Kruskal’s algorithm (and the greedy algorithm) are correct. You are only required to know statements of theorems.
There was a question about scheduling problems that involved probability (MAT 2402, June 2003, question 2 – part b).
Dr. Borg told me that there will not be questions like that on the exam – of course there may be scheduling problems, but not with probabilities.

Graph theory – solutions to three questions

components.pdf

colour-classes.pdf

subgraphs-edges.pdf

2005 – question 2c – using matroids for scheduling

In the scheduling problem of qn. 2c (2005 past paper), the greedy algorithm does not explicitly give a schedule – it only tells us which jobs to do early (i.e. before their deadline).

The matroid is (S,I), where S is the set of tasks, and a set A of tasks is independent if there is *some* way of scheduling them so that they all meet their deadline. This schedule need not do the maximum-penalty task first.

In 2c, there is *some* way of scheduling tasks 1,2,3,4 so that they all meet their deadline (e.g. doing 2,4,1,3, in that order). So the greedy algorithm will choose all of 1,2,3,4.
We cannot add task 5 now, because there is no way of scheduling 1,2,3,4,5 so that they all meet their deadline.
Similarly, we cannot add task 6, because there is no way of scheduling 1,2,3,4,6 so that they all meet their deadline.
However, we can add task 7, because we can schedule 1,2,3,4,7 so that they all meet their deadline, e.g. do 2,4,1,3,7 in that order. Tasks 5 and 6 will be late, so the total penalty is 40 + 30 = 70.