7T
King’s College London
UNIVERSITY OF LONDON
This paper is part of an examination of the College counting towards the award of a degree. Examinations are governed by the College Regulations under the authority of the Academic Board.
MSc EXAMINATION
7CCSMNTH Network Theory
Period 2 (May/June 2014)
TIME ALLOWED: THREE HOURS
ANSWER QUESTION ONE AND THREE OTHER QUESTIONS
ANSWER EACH QUESTION IN A SEPARATE ANSWER BOOK
AND WRITE ITS NUMBER ON THE COVER.
CALCULATORS MAY BE USED. THE FOLLOWING MODELS ARE PERMITTED:
Casio fx83
Casio fx85.
DO NOT REMOVE THIS PAPER FROM THE EXAMINATION ROOM
TURN OVER WHEN INSTRUCTED 2014 © King’s College London
1.
a)
7CCSMNTH
Question one
Find a minimal spanning tree, using the prim’s algorithm for the below graph (Figure 1). Show all the steps you take.
6
2
6
3
5
3 2
5 7
147
8
3
4
34
6
b)
c)
d)
e)
Let G be a simple graph with k components, with each component a tree (i.e., G is a forest). Prove that n = m+k, where n=|V(G)| and m=|E(G)|.
Hint: You may assume that the statement holds for k =1.
[4 marks] Assume we have m traffic streams of equal length packets arriving
according to a Poisson process with rate λ/m each. The m traffic streams are time-division multiplexed in a scheme whereby the time axis is divided in m-slot frames with one slot dedicated to each traffic stream. Each slot is one time unit long and can carry a single packet. What is the average queueing delay per packet in this system?
In the Erdos-Renyi graph Gnp, calculate the followings:
i) Degree distribution of P(k)
ii) Average degree of a random node v
Consider problem (P) to be, (P): Minimise f(x)
[5 marks]
[2 marks] [2 marks]
Subject to gi(x) ≤ 0 for i = 1, …, m hi(x) = 0 for i = 1, …, n
Let x* be a feasible solution that solves (P) locally. i) Write the Lagrangian dual problem of (P).
1
Figure 1: Graph for question 1(a)
[6 marks]
[3 marks] ii) Reformulate (P) to an unconstrained problem using Logarithmic
barrier method.
[3 marks]
[Total 25 marks]
2
2.
a)
See Next Page
7CCSMNTH
Question two
An Eulerian tour in an undirected graph is a cycle that is allowed to pass through each vertex multiple times, but must use each edge exactly once. This simple concept was used by Euler in 1736 to solve the famous Konigsberg bridge problem. Euler formulated the relevant information as a graph with four nodes (denoting land masses) and seven edges (denoting bridges), as shown in Figure 2.
Figure 2: Graph of question 2(a)
i) Show that an undirected graph has an Eulerian tour if and only if all its vertices have even degree.
[5 marks]
ii) Show that there is no Eulerian tour of the Konigsberg bridges (of Figure 2). [4 marks]
iii) Can you give a similar if-and-only-if characterisation of which directed graphs have Eulerian paths?
[5 marks]
Suppose that whether or not a web server is in a fully operational mode
at a specific day N depends on previous conditions of the server through the last three days only, i.e., days N-1, N-2 and N-3. Show how the performance of this web server can be analysed using a Markov chain. How many states are needed for the Markov chain?
[6 marks] What does Pollaczek- Khinchin (P-K) formula explain in an M/G/1 system? Write the P-K formula and use it to calculate the average number of customers in the M/G/1 queuing system (including
b)
c)
customers in the queue and in service).
3
[5 marks]
[Total 25 marks] See Next Page
3.
a)
7CCSMNTH
Question three
Find the maximum flow from node s to node t through the network in Figure 2 using the Ford Fulkerson’s Algorithm. In each step show the residual graph. Assume links’ weights are the capacity of the links in units of flow.
Figure 3: Network topology
[10 marks]
An edge of a network is called a bottleneck edge if increasing its capacity results in an increase in the maximum flow. List all bottleneck edges in the network of Figure 3.
[5 marks]
Consider the following generalisation of the max flow problem.
You are given a directed network G = (V, E) with edge capacities {ce}. Instead of a single (s, t) pair, you are given multiple pairs (s1, t1), (s2, t2)… (sk, tk), where the si are sources of G and the ti are destinations of G. You are also given k demands d1, …, dk. The goal is to find k flows f(1), …, f(k) with the following properties:
b)
c)
– – – – –
i) ii)
f(i) is a valid flow from si to ti
For each edge e, the total flow fe(1) + fe(2) + … + fe(k)
Doesn’t exceed the capacity ce.
The size of each flow f(i) is at least the demand di.
The size of the total flow (the sum of the flows) is as large as possible.
Explain whether you can reduce this problem to a simple max
flow problem.
How would you solve this problem?
[4 marks] [6 marks]
[Total 25 marks]
See Next Page
7CCSMNTH
4
4. Question four
a) Consider a two-node Markovian queueing network (of the more general
type considered by Jackson) for which N=2, m1 = m2=1 (single server queues), μki = μi (constant service rate), and which has transition probabilities (rij) as described in the following matrix:
rij =
Table I: transition probabilities
Where 0 < α < 1 and node 0 and N+1 are the “source” and “”sink nodes, respectively. We also have (for some integer K)
And assume the system initially contains K customers.
i) Find ei (i=1,2).
The corresponding equation is
[6 marks]
ii) Since N=2, let us denote p(k1, k2) = p(k1, K-k1) by pk1. Find the balance
i ↓ j→
0
1
2
3
0
0
1
0
0
1
0
0
1-α
α
2
0
1
0
0
equations for pk1.
iii) Solve these equations for pk1 explicitly.
[8 marks]
[5 marks] b) Calculate the clustering coefficient of each node (Ci) in the graph in Figure
3, and the average clustering coefficient of the graph.
[6 marks]
a
A
be d
c
Figure 3.
5
f
[Total 25 marks]
See Next Page
7CCSMNTH
5. Question five
a) Consider a general optimisation problem in the form of problem
(GP).
(GP): minimise f(x) subject to
i) Explain the Newton’s algorithm by showing its steps.
[4 marks]
ii) Consider the function
This function has its optimal solution at x* =(x*1, x*2) = (1, 1) and
f (1, 1) = 10. Run the k-th iterates of the Newton’s algorithm, and compute dk (the descending direction).
[4 marks]
b) Resource Allocation problem:
Assume wireless channel that can transmit up to 40 Mbps and will be divided between any numbers of admitted users. There are 5 users in total with the data rate as vector R =[ri] (R = [5, 15, 3, 21, 7]). The profit of service provider depends on the number of admitted users as well as the allocated data rate to that user, i.e. profit for giving service to user i, pi = 3 ri + 10. Service provider’s objective is to maximise their profit.
i) Model this problem as a Knapsack problem; use greedy approximation and find out which users will be given service.
[7 marks]
ii) Model the problem with the genetic algorithm, starting with the
population of five chromosomes, and continue for five
iterations.
- Use five bits binary for representing the chromosomes
- Assume cross-over probability is 0.5 and mutation probability is 1.
- Define your cross-over and mutation operators yourself (use the
same operation for all the five iterations).
- Write all steps of computing the five sets of populations. Based on
the fifth population, which users will be allocated service?
- If you make any further assumptions, explain them.
[10 marks]
[Total 25 marks]
6
.
6.
a)
See Next Page
7CCSMNTH
Question six Supposethatsomeresearchersstudyingeducationalinstitutionsdecideto collect data to address the following two questions.
- As a function of k, what fraction of classes in King’s College have k students enrolled?
- As a function of k, what fraction of 3rd-grade elementary school classrooms in the city of London have k students?
Which one of these would you expect to more closely follow a power- law distribution as a function of k? Give a brief explanation for your answer.
[5 marks] Consider an M/M/1 system with parameters λ and μ in which exactly r
customers arrive at each arrival instant.
i) Draw the state-transition-rate diagram
[4 marks]
ii) By inspection, write down the equilibrium equations for pk
(k=0, 1, 2 ...).
[4 marks]
Draw a simple, connected graph with degree sequences of
(5;4;3;3;2;2;1) and (7;6;5;4;3;3;2).
[2 marks] Consider the network of Figure 2 and assume the links’ weights represent cost of transmitting one unit of flow over that link, denoted by cij. Assume source node s has 10 units of flow to transmit to the destination node t, and all the links have the capacity of one unit of flow. Formulate the problem that minimise the transmission cost from s
b)
c) d)
e)
to t in this network (the Minimum Cost Flow problem). Consider problem (P2)
[5 marks]
(P2): Minimise (x1 − 12)2 +(x2 +6)2
Subjectto x 2+3x1 +x 2 −4.5x2 ≤6.5 122
(x1 − 9) +x2 ≤ 64
Determine whether or not the point an optimal solution to this problem.
7
= (2, 1) is a candidate to be [5 marks] [Total 25 marks]
8
Final Page