MT365 Block 3 Exercises

MT365 Block 3 Exercises

Graphs 3

Question 1

Let G be the following graph.

(a) Using the cycle method, determine whether G is planar, and if so, give a plane drawing of G.

(b) Without explicitly counting faces, find a way to determine the number of faces of G.

(c) Now let H be the graph obtained by deleting the edge ch from G and inserting an edge bf. Give a subgraph of H that has K5 as a contraction, and state which edge needs to be contracted. Is H planar?

Question 2

A wildlife park wishes to have the following species in as few enclosures as possible:

Aardwolf, Eagle, Hyena, Jackal, Meerkat, Oryx and Warthog.

Some species cannot share an enclosure, shown by the crosses in the following table.

A / E / H / J / M / O / W
A / - / x / x / x / x
E / x / - / x / x / x
H / x / - / x / x / x / x
J / x / x / x / - / x / x / x
M / x / x / x / x / -
O / x / x / -
W / x / x / x / -

Draw a suitable subgraph of K7 in order to find the minimum number of enclosures needed, and list a possible assignment of species to enclosures.

Question 3

Consider the following planar graph G.

(a) How many faces does G have?

(b) Is there a face of degree 5?

(d) What is the chromatic number χ(G)?

A dominating set of vertices is a set S with the property that each vertex of G is either in S or adjacent to a vertex in S. The dominating number of G, dom(G), is the number of vertices in a minimum dominating set.

An independent set of vertices is a set of vertices of G, no two of which are adjacent. The independence number of G, ind(G), is the number of vertices in a maximum independent set.

(e) What are the values of dom(G) and ind(G)?

(f) Consider the subgraph H of G containing the vertices G, H, I, J, K, L and M. Draw its dual graph.

Networks 3

Question 4

A rowing coach has to assign eight rowers to an ‘eights’ boat. He has chosen one out of the eight to be the stroke (position 1) and another rower to be at bow (position 8). The coach has assessed the remaining six rowers, A – F, in each of the remaining positions, 2 – 7. He has given them suitability scores, using a lower number to represent greater suitability. The following table gives the suitability scores.

2 / 3 / 4 / 5 / 6 / 7
A / 7 / 6 / 5 / 3 / 6 / 5
B / 8 / 7 / 5 / 4 / 5 / 6
C / 7 / 5 / 7 / 8 / 7 / 6
D / 8 / 8 / 6 / 5 / 7 / 6
E / 8 / 6 / 5 / 5 / 7 / 8
F / 7 / 7 / 4 / 5 / 5 / 6

(a) Use the Hungarian algorithm for the assignment problem to find the first revised cost matrix and the first partial graph.

(b) An initial matching is as follows.

C-2, D-5, E-4, F-6

Use this initial matching and continue to apply the algorithm to find an optimal assignment. Give the lowest suitability score.

(c) Rower A won’t be available to row in the next competition and gets replaced by rower G. The new suitability table is as follows.

2 / 3 / 4 / 5 / 6 / 7
G / 5 / 5 / 6 / 4 / 7 / 5
B / 8 / 7 / 5 / 4 / 5 / 6
C / 7 / 5 / 7 / 8 / 7 / 6
D / 8 / 8 / 6 / 5 / 7 / 6
E / 8 / 6 / 5 / 5 / 7 / 8
F / 7 / 7 / 4 / 5 / 5 / 6

The coach would like to find an assignment with every suitability score less than 6. Use the Marriage Theorem to show that this is not possible.

Design 3

Question 5

Let C be the linear code

{000000, 001101, 010111, 011010, 100011, 101110, 110100, 111001}.

(a) Write down the length, dimension and rate of code C.

(b) Is code C cyclic? Justify your answer briefly.

(d) Find a parity check matrix for code C, and use it to correct the received word 100110.

(e) Find all the codewords of the dual code C*.

(f) Are the codes C and C* equivalent? Justify your answer briefly.

Question 6

How many errors can the following codes detect and correct?

(a) The Hamming code of length 7

(b) The Reed-Muller code R(7)

MT365 Block 3 Solutions

Graphs 3

Solution 1

(a) See HB p23 for the cycle method. We use the Hamiltonian cycle abcdefgha.

The edges not on the Hamiltonian cycle are: ae, af, ag, bd, be, bh, ce, cg, ch and eg. We put the edge ae inside the cycle, in set A. [At this initial stage, make sure to place a SINGLE edge into A.]

The edges bh, ch and cg are not compatible with ae and must go in set B (outside the cycle). We check and find that these edges are compatible with each other.

Next, we check for incompatibilities of the remaining edges with each edge in B. The edges af, ag, bd and be are not compatible with (for example) edge ch and must therefore go in set A. There are no further incompatibilities.

We check and find that all the edges in A are compatible.

The two remaining edges are: ce and eg.

We check each new edge in A in turn and find that the edges ce and eg are not compatible with bd and af, respectively. So ce and eg must go in B.

We check and find that all the edges in B are compatible, and deduce that G is planar.

To obtain a plane drawing of G, note that we have set A = {ae, af, ag, bd, be}, giving the edges inside the cycle, and set B = {bh, ch, cg, ce, eg}, giving the edges outside the cycle.

(b) Use Euler’s formula for planar graphs (HB p22), which is n – m + f = 2, where n is the number of vertices, m is the number of edges and f is the number of faces.

Graph G has 8 vertices and 18 edges. We can therefore deduce that it must have the following number of faces: f = 2 – n + m = 2 – 8 + 18 = 12.

(c) Take the subgraph of H containing the vertices a, b, e, f, g and h. Contract the edge gh to get K5. By Theorem 1.4 (Handbook p22), because H contains a subgraph that has K5 as a contraction, H cannot be planar.

Solution 2

The subgraph of K7 is as follows.

The edges show which species cannot be put into the same enclosure. So the minimum number of enclosures is given by the chromatic number χ(G) (the smallest k such that G is k-colourable).

Looking at vertices A, E, J and M, we see that G contains K4 as a subgraph, and will therefore need to be coloured with at least four colours. If we can find a 4-colouring, then we know that χ (G) = 4.

We assign four colours, 1 – 4, to the vertices A, E, J and M. Vertex H can only be the same colour as E. Vertices O and W can only be the same colour as either vertex A or vertex M. Hence χ (G) = 4 and we will need four enclosures to separate the animals:

Aardwolf, with any of Oryx and Warthog

Eagle, Hyena

Jackal

Meerkat, with any of Oryx and Warthog

Solution 3

(a) G has 10 faces. (Don’t forget to count the infinite face.)

(b) Yes, the face with vertices G, L, I, J and M has face degree 5.

(c) The smallest face degree is 3, for the face with vertices C, D and E. The largest face degree is 6, for the infinite face.

(d) We will need at least 3 colours, as G contains cycles of odd length. In fact, χ(G) = 3, because the following is a valid 3-colouring.

(e) dom(G) = 3. Choose for example vertices E, G and H.

ind(G) = 6. Choose for example vertices A, D, H, K, L and M.

(f) As H has four faces, H* will have four vertices. As H has 9 edges, H* will have 9 edges, too. Draw H* by first drawing H and then placing a vertex on each of the four faces of H. Now add edges between these four new vertices by drawing them to cross the edges of H. You should get the following dual graph H*.

Networks 3

Solution 4

(a) See HB p28. First we assign a weight to each rower, namely the lowest cost in the respective row. Then we deduct this weight from each of the costs in that row.

Next, we do the same for the columns.

This results in the following first revised cost matrix.

2
2 / 0
3 / 0
4 / 0
5 / 1
6 / 1
7
3 A / 2 / 3 / 2 / 0 / 2 / 1
4 B / 2 / 3 / 1 / 0 / 0 / 1
5 C / 0 / 0 / 2 / 3 / 1 / 0
5 D / 1 / 3 / 1 / 0 / 1 / 0
5 E / 1 / 1 / 0 / 0 / 1 / 2
4 F / 1 / 3 / 0 / 1 / 0 / 1

We construct the first partial graph using only those edges whose current cost is zero.

(b) Part A of the algorithm (HB p 28): Label with * each rower not incident with an edge in the current matching M = C-2, D-5, E-4, F-6, i.e. A and B.

Take each newly labelled rower in turn and label with that rower any unlabelled position in the boat that is joined to the rower by an edge NOT IN M.
Take each newly labelled position in turn and label any unlabelled rower that is joined to the position by an edge IN M.
Repeat until a position not incident with an edge in M is labelled, called a breakthrough, or until no more labelling is possible.

We reach breakthrough as follows:

Part B of the algorithm: Trace back through the labels to find an alternating path, either A5D7 or B5D7. First improved matching: replace D5 by A5 and D7 to get the new matching A5, C2, D7, E4 and F6.

Next, we return to Part A of the algorithm, to see whether the new matching can be further improved. We get the following labelling.

No more labelling is possible and no breakthrough was achieved, and so we check the alternative improved matching, B5, C2, D7, E4 and F6. Similarly to the above, you should get to a stage where there’s no more labelling possible and no breakthrough has been achieved.

Next, we go to Part C of the algorithm. The original bipartite graph is the complete bipartite graph because any rower can fill any position. In the above bipartite graph, the labelled rowers are A, B, E and F and the labelled positions are 4, 5 and 6. We use the first revised cost matrix from above and I have shaded the costs that have edges that start at a labelled rower and end at an unlabelled position to help us determine the lowest cost, δ.

Note: The Networks3 eTutorial contains a slightly different method for identifying which cells should be updated, called HUNS. You cross out the horizontal, unlabelled supplies (unlabelled rows) and the vertical, labelled demand (labelled columns).

δ is the (non-zero) minimum cost among the shaded cells, and so δ = 1.

Next, we increase the weight on each labelled rower by δ = 1 and decrease the weight on each labelled position by δ = 1. Furthermore, for each edge of the original bipartite graph that joins a labelled rower to an unlabelled position, decrease the current cost by δ = 1; for each edge that joins an unlabelled rower to a labelled position, increase the current cost by δ = 1. The revised cost matrix should now be as follows (I’ve shaded the costs that have changed – note that we will need to remove edge D5).

2
2 / 0
3 / -1
4 / -1
5 / 0
6 / 1
7
4 A / 1 / 2 / 2 / 0 / 2 / 0
5 B / 1 / 2 / 1 / 0 / 0 / 0
5 C / 0 / 0 / 3 / 4 / 2 / 0
5 D / 1 / 3 / 2 / 1 / 2 / 0
6 E / 0 / 0 / 0 / 0 / 1 / 1
5 F / 0 / 2 / 0 / 1 / 0 / 0

Decreasing some of the costs by δ will have created at least one more edge. Incorporate all such edges with zero cost in to the first partial graph, delete all the labels and return to Part A of the algorithm.

The revised partial graph now is as follows.

The graph after labelling should look as follows.

Tracing back, we find two alternating paths: B6F2C3 and B6F4E3. We choose the first to obtain the improved matching A5, B6, C3, D7, E4 and F2. This is clearly a maximum matching. The positions should therefore be filled as follows:

2 / 3 / 4 / 5 / 6 / 7
F / C / E / A / B / D

The total suitability score is: 7 + 5 + 5 + 3 + 5 + 6 = 31. (You can check that the other alternating path will lead to the same suitability score.)

2 / 3 / 4 / 5 / 6 / 7
G / 5 / 5 / 4 / 5
B / 5 / 4 / 5
C / 5
D / 5
E / 5 / 5
F / 4 / 5 / 5

By the Marriage Theorem (HB, p25), an assignment consisting entirely out of suitability scores that are less than 6 will exist if and only if for each subset of m rowers, the m rowers collectively can fill at least m positions, with scores less than 6, for 1 ≤ m ≤ 6.

Now consider the four rowers B, D, E and F. Collectively, they can only fill positions 4, 5 and 6, and hence, by the marriage condition, no assignment consisting entirely out of suitability scores that are less than 6 is possible.

Design 3

Solution 5

(a) See Handbook p32. The length of code C is n=6 (as each code word comprises of 6 bits), its dimension is k=3 (since there are eight code words and 23 = 8). The rate of the code is r = k/n = 3/6 = 1/2.

(b) Code C is not cyclic: for example, 111001 is in C, but 111001 cycles to 111100, which is not in C.

Use Theorem 1.1 on p32 of the Handbook to deduce that, as δ is odd, code C can detect and correct up to (δ-1)/2 = 1 error.

(d) See Handbook p33. Since n=6 and k=3, a parity check matrix H is a (n-k)xn=3x6 matrix, such that HxT= 0T, for all code words x. For each x containing bits x1, x2, x3, x4 , x5 and x6 in that order, we have

x1 + x2 + x5 = 0

x1 + x2 + x3 + x6 = 0

x1 + x4 + x6 = 0

So one parity check matrix is as follows.

Alternatively, if we can find a generator matrix in standard form, G = [I | B], then H = [BT | I].

We can use G as shown below,

to get the following parity check matrix.

The error syndrome for the received word r is HrT, and using H in standard form we get

The error syndrome is the same as the third column of H, and so the third bit is in error. The corrected word is 101110.

(e) See Handbook p33. The code words of C* are generated by the parity check matrix of code C; i.e. they are linear combinations of the rows of H.

r1: 011100 r2: 110010 r3: 111001 r1+r1: 000000 r1+r2: 101110 r1+r3: 100101

r2+r3: 001011 r1+ r2+r3: 010111

(f) See Handbook p33. The two codes C and C* are equivalent. Swapping bits 4 and 5 gives the relevant rearrangement.

Solution 6

See Handbook pp 32-34 and Theorem 1.1 on p 32.

(a) All Hamming codes have minimum distance 3. So this code will detect and correct up to 1 error.

(b) The minimum distance of R (m) is 2m-1. So δ = 64. This code will detect up to 32 errors and correct up to 31 errors.