MATH2081 | MATH2328: Math for Computing

1
Lecturers: Dr Nguyen Hieu Thao & Dr Jeff Nijsse
Email: [email protected]

Tutorial Exercises: Graph Theory and

Networks
414 Chapter 8 ◆ Graph Theory
(2024C, Week 10)1
8.5 Exercises
1. In a precedence graph, the verticesInmodel
Exercises 1–6,
certain write❦
actions. the
Foradjacency
example, matrix of might
a vertex each graph. 17. Th
or
1.
model a statement in a computer program. There is an edge from vertex
b v to vertex w if wh
the action modeled by v must occur before the action modeled
x by w. Drawxthe precedence 18. W
1 2
graph for
414 the computer
Chapter 8 ◆ program below.
Graph Theory x5 giv
a c
19. Co
x = 1; y = 2; z = x + y; z = z + 1. x 6 x7
8.5 Exercises gr
2. Write the adjacency matrix and the incidence matrix of each
x 3 graph. x4 20. Le
In Exercises 1–6, write the adjacency matrix of each graph. 17. The 7 × 7 matrix whose ij th entry is 1 if i + 1 divides j +W 1
or j + 1 divides i + 1, i ̸ = j; whose ij th entry is 2 if i = j; and
1. b 21. Su
whose ij th entry is 0 otherwise
x1 x2 18.e Write the
x 8 adjacency
d matrices of the components of the graphs
x5 given by the adjacency matrices of Exercises 13–17.
a c 2.
19. aComputec the squares of the adjacency matrices of K5 and the
x6 x7
graphs of Exercises
x 1 and 2.
3 wh
x3 x4 20. Let A be the adjacency matrix for the graph of Exercise 1.
x 1 What is thex 2entry indrow a, column d of A5 ? the
21. Suppose that xa 4graph has an adjacency matrix of the form
22. Re
e x8 d b e ' (
(a) (b) A′ 23. Le
A= ,
2.
a c 3. A ′′ ab
1 x
3. Draw the graph represented by
a below.
x 3 the adjacency matrix (a) b
where all entries of the submatrices A′ and A′′ are 0. What
In must
Exe
x1 x2 d x 11 x
the graph look2 like? dence m
a b xc d e x 5 Exercise
e1 e2 e3 e4 ex5 e6
4 22. Repeat
d x 4 21 with “adjacency”
3  replaced by “incidence.”
a 1 0 c0 0 0 1
 
ab 2 e 0 0 1 0
23. Let A bean adjacency matrix of 24. a
a graph. Why is An symmetric
❦
b 
0 0 1 0 1 g x 7 b 0 x 81 1 0 1 0
x 6 about b
3. the main diagonal for every positive integer n?

(a) xc1 0 1 2 1 1 (b) c  e
a  b 1 0 0 1 0 0 c
 
x 9In Exercises
xd10240 and
1 25,
0 draw
1 0the graphs
0 represented by the inci-

d 1 0 x 21 0 0
x 11
e x 0 1 1 0 0 dence
f matrices.
e 0 0 1 0 1 1 d
d
5 x4 x3 ⎛ ⎞ ⎛ ⎞e
c 4. The graph of Figure
24. 8.2.2
a 1 0 0 0 0 1 25. a 0 1 0 0 1 1
❦
g x6 x7 x8
4. Draw the graph represented
e by the incidence matrix (b)
5. The complete above.b graph
bipartite
⎜0 1 1 0 1 0⎟
⎜ K2,3 ⎟ b ⎜0
⎜ 1 1 0 1 0⎟
26. ⎟W
⎜ ⎟ c ⎜1 0 0 1 0 0⎟ c ⎜0 0 0 0 0 1⎟
x9 x 10 ⎜ ⎟
6. The complete graph on d five
⎝0 vertices
1 0 1 K50 0⎠ d ⎝1 0 0 1 0 0⎠tri
1 Most of the content of thisf document is taken from the book [1].
e 0 0 1 0 1 1 e 1 0 0 1 027.0 Le
4. The graph of Figure 8.2.2 In Exercises 7–12, write the incidence matrix of each graph.
5. The complete bipartite graph K2,3 26. What must a graph look like if some row of its incidence ma-
7. The graph of Exercisetrix 8. only
1 consists Theofgraph
0’s?
of Exercise 2
6. The complete graph on five vertices K5
9. The graph of Exercise
In Exercises 7–12, write the incidence matrix of each graph. 27. Let3 A be 10. The graph
the adjacency of of
matrix Figure
a graph8.2.1 If
G with n vertices. Let
11. The complete bipartite graph K2,3 Y = A + A2 + · · · + An−1 . yo
7. The graph of Exercise 1 8. The graph of Exercise 2
9. The graph of Exercise 3 12. ofThe
10. The graph complete
Figure 8.2.1 graph on five vertices K Exercis
If some off-diagonal5 entry in the matrix Y is zero, what can
11. The complete bipartite graph K2,3 you say about the graph G?
In Exercises 13–17, draw the graph represented by each adjacency 28. Le
12. The complete graph on five vertices K5 matrix. Exercises 28–31 refer to the adjacency matrix A of K5 . ele
13.by each
In Exercises 13–17, draw the graph represented
⎛ a b c
adjacency d e
28. ⎞ 14.
Let n be a positive a b c d e
⎛ integer. Explain why ⎞ f An
all the diagonal
matrix. a 2 0 0 1 0 elements of Anaare equal 0 0and1all the
0 off-diagonal
0 1 elements of
 The capacity of ancity edgeB. is
Finally, we introduce
the capacity a supersource
of the route. Edges ofand supersink.
infinite capacity connect
A, t1 ,1.toWhat
A, t2 is
, and B, t to B,
a planar graph?
1 t2 to indicate that any number of cars
8.7 can
4000 5. wait
Whatatis city
Exercises A orreduction?
a series
city B. Finally, we introduce a supersourceA,and 6:00supersink. C, 6:30
2. What is a face? 6. Define
3000 In Exercises homeomorphic
1–3, show graphs.
that each graph is planar by redrawing it 5.
4000
3. State Euler’s equation for a connected, planar graph. C,B,
A, 6:00 so
6:30 that no edges cross.
7. State Kuratowski’s theorem. (a) A designated
` ` 6:15
4. What are series edges?
3000 1. 2000 ` (b) A designated
` a` ` 6:15
B,A,
` 4000 ` b z
6:15
` C, 6:45 (c) The weightg C
2000
2 8.7 Exercises
` ` 4000
3000
` a ` c
negative num
a A, 6:15 ` ` 6:45
C,B, 6:30 z
3000is planar by redrawing it
In Exercises 1–3, show that each graph 5.2000 Example
b 10.1.2 The graph of Figure
5. Show that
so thateach graph
no edges cross. is planar by redrawing it so`that no edges cross.
` ` a
is vertex z. The capa
6:30
B,A, e d
❦
1. 6:30 C, 7:00
2000 c is 2.
In Exercises 6–8, dete
b 4000
2. graph is planar, redraw
A, 6:30
Figure 10.1.5 A network that 7:00
C,represents g bcity
the flow of traffic from
a c Throughout
subgraph homeomorphth
4000the period 6:00 P.M. to 7:00 P.M.
A to city C during
a c d sink6.by z.
Figure 10.1.5 A network that represents the flow of traffic from city A flow in a net
Variants
A to city C during of the6:00
the period network flow
P.M. to problem
7:00 P.M. have been used in the design of f efficient com-
puter networks (see [Jones; Kleinrock]). In a model of a computer d network, a vertexef is a capacity of that edg
e neither the source fno
(a)of the eor switching center,
d
(b)
❦ ❦
Variants message
network flow problem haveanbeen edgeused
represents a channel
in the design of on which
efficient data can be transmit-
com-
In Exercises 6–8, determine whether each graph is planar.these
If the
2. ted between vertices, a flow is the average
puter networks (see [Jones; Kleinrock]). In a model of a computer number of
3. network,bits per is a it so that no edges cross; otherwise, find a ideas precise.
second
graph isaplanar,
vertexredraw being transmitted
on a channel, and the capacity of an edge is the capacity of the corresponding channel.
❦ ❦
message or switching center, an edge b represents a channel on which data can behomeomorphic
transmit-
6. Consider a planar
ted between vertices, graph
a with 5number
G average
a flow is the
c vertices a, b, c, d, e. In this order cof thed vertices, the
subgraph
of bits per second being a transmitted
to either K 5 or K 3,3 .
Definition 10.1
6. b a b
10.1 Review on aExercises
channel, and the capacity of an edge is the capacity of the corresponding channel.
❦ ❦
adjacency matrix of G is below: of the directed edge
7.
e f g h number Fij such that
10.1 Review1. Exercises
What is a network? d
(a) How many edges does G
e have? Explain your answer.
f 8. What is a flow out of a vertex?
a b c dc e
2. What is a source in a network? 9. What is conservation of flow? f (a) Fij ≤ Cij . e
1. What is a network? 3. 8. What is a flow out of a vertex?
 
i a kbetween
0 1 the
3. What is a sink(b)in aDraw
network?the planar graph G. 10. Given a flow in a network, what is the j relation l 1 1 2 (b) For each vert
2. What is a source in a network? 9. What is conservationflow of flow?
out of the source and the flow into the bsink? 1 0 1 1 1
4. What is a capacity in a network? a c d
In Exercises 4 and 5, show that each egraph is not
b K1 or 1K d. 2planar by finding

3. What is a sink in a network? 10. Given a flow in11. a network, what is the relation between the c 0 0
(c) Is a simple graph? Explain your answer.
What is a supersource?
a subgraphDrawhomeomorphic to either
h What is a❦
G
5. What is a flow in a network? flow out of the source and the flow into the7.sink?
 5 3,3 
8.
4. What is a capacity in a network? 12. 4.
supersink? d a1 1 0 2b 1
[In a sum ❦
e f g
5. What is a flow in a network?
the largest simple 11.
6. What is a flow in an edge?
subgraph of G.
What is a supersource? a b
e 2 1 0 1 0 such
h as (1
Johnsonbaugh-50623 e book February 3, 2017 15:56
7. What is a flow into a vertex? 12. What is a supersink? over all vertices i. Al
6. What is a flow in an edge? i We call Fij the
10.1 7. Fill in the missing edgej flows so
Exercises
k
thatl the result is a flow in the f given network. c Determine
7. What is a flow into a vertex? g
In Exercises 4 and 5, show that each graph is not planar by finding
the value
In Exercises 1–3, fill in the of
a subgraph each
missing edge flow.
homeomorphic
flows so thattothe
either K5isor K3,32.
result .
d c
10.1 Exercises b 8. 4, 0 c e a d
4. (a)
a flow in the given network. Determine the values of the flows. (b) (c)
b
In Exercises 1–3, fill 1.
in the missing edge flows so that the result is a
2. b 3. the flow into j and
8. Thw
3, 2 h 6,2 c
b
a flow in the given network. Determine the values of6,the flows.c b 4, 0 c b 4, 3 c thr
a 5, 2, z ing
1. f 5, 3, 2c 6,2 5, 5,
b 6, 5, 3 c 4,
6,
❦the
2, g 4,1, d d
a e z flow out of j.
a 6, z a 5, 2, z
5, 3 5, 4, 2
e d 2,
d 4, 5, 3 e
4, 5, 3 2, 4, 2f 3,e 1 4,
a 6, z The property e
d e d 5, 3 e f 5, 2 oil-pumping exampl
g
4, 5, 3,
3 2
4.
used nor supplied Th
The following graph represents a pumping network in which
at
oil for three refineries, A, B, and C, is delivered from three
d
8. Find a maximal flow in each network starting with the edgewells,
3, 2 e
flows given.
❦
w1 , w 2 , and Example
w3 . The capacities
10.1.4 of the The
intermediate
assignments,
systems are shown on the edges. Vertices b, c, d, e, and f rep-

❦
resent intermediate
b 2, pumping
2 c stations. Model this system as a
(a) The network in Exercise 7(a). network.
3, 2 4, 3
3 b 4 c 4
❦
2, 1
(b) The network in Exercise 7(b). w 1a z A
define a flow for 7:0
the
Re
3 8
(c) The network beside. 5, 3 4, 2 Fad = 3, is the same
9. In
2 d 6 at
w2 d 2, 2 e B
twe
In Figure 10.1 2
5 3 + dir
Figure 10.1.2
9. Let G denote the set of simple graphs G = (V, E), where V = 1, 2, · · · , n4 for some n ∈ Z . of Example 10.1.4. A
Flow in a
network. Edges are labeled
w 3x, y to indicate capacity x C is y. This notation w
Define a function f from G to Z+0 by the rule G 7→ f (G) = |E|. Is5 f one-to-one?
e 2 Isf f 6onto?
and flow y.
❦
5. Model the system of Exercise 4 as a network assuming that
Explain your answers. well w1 can pump at most 2 units, well w2 at most 4 units, and a
well w3 at most 7 units.
6. Model the system of Exercise 5 as a network assuming, in
References addition to the limitations on the wells, that city A requires 4
units, city B requires 3 units, and city C requires 4 units.
10. Giv
1. Johnsonbaugh, R.: Discrete Mathematics - Eighth Edition. Pearson
7. Model Education,
the system New
of Exercise 6 as York
a network assuming, in ad-
wh
dition to the limitations on the wells and the requirements by
(2018). the cities, that the intermediate pumping station d can pump 11. Wh
at most 6 units. wo

10.2 A Maximal Flow A

If G is a transport network, a ma
general, there will be several flows
give an algorithm for finding a max
initial flow and iteratively increase
possible. The resulting flow will th
We can take the initial flow
To increase the value of a given fl
and increase the flow along this pa
It is helpful at this point to in
G denotes a network with source a