Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

MATH 367 NETWORKS IN THEORY AND PRACTICE

1. Euler's formula V-E+ F=2 relates the number of faces F, edges E and vertices V of a connected planar graph.

(i) State the definition of a complete bipartite graph. [3 marks]

(ii) Draw the complete bipartite graph K33. [3 marks]

iii) Show that the graph that arises by omitting any edge from K3.3 is planar and check that Euler's formula holds for such a resulting graph. [4 marks]

(iv) Proof Euler's formula. [6 marks]

(v) Prove that K3.3 is not planar. (You can assume that every cycle in a bipartite qraph is of even length). [6 marks]

2. A flow through aflow network with source s, sinkt and intermediate verticesa. b. c and d is given by the following diagram:

The numbers ilj at each arc denote the capacity (i) and the fow through (j) of each arc. Use the met hod of Ford Fulkerson to find a maximal flow and a minimal capacity cut for this flow network. Draw the resulting flow network. [8 marks]

3. (a) A project involving 4 tasks is to be undertaken by a project team containing 4 people. Each task must be assigned to a single member of the team and no team member might be assigned more than one task.The time in which team member i is expected to complete task j is tij.The time estimates for all team members and tasks are comprised in the matrix T =tii given below:

(i)Use the Hungarian met hod (Met hod of Lines) to determine the assignment of team members to tasks for which the total time taken to complete the four tasks is minimised. [8 marks]

(ii) What is the tot al time taken to complete all tasks? [2 marks]

(b) A company has to assign 6 jobs J1, J2, ...& to 4 workers Wi, ... W4.Each job has to be assigned to 1 worker. The "cost" of worker Wi on job J; is given by the matrix C=Gi. The job J; takes a time b=bi to perform (by any worker). The cost matrix and time vector are given below:

All jobs must be complet ed wit hin an 8-hour working day. Find a feasible assignment of minimal tot al cost. [10 marks]