Oliver Braun
CSE 101 (Summer Session 2021)
Homework 5: Graphs and Graph Algorithms
Instructions
Homework questions will be similar to your future exam questions. The homework will not be graded,
however, you are highly recommended to practice using these questions for better preparations of the
exams.
Key Concepts Graphs and their representation, Trees, Euler and Hamilton Tours, Minimum Spanning
Trees, Topological Sorting, Single-Source Shortest Paths (SSSP), All-Pairs Shortest Paths (APSP), Trav-
elling Salesperson Problem (TSP), MST-Heuristic for the TSP, Capacitated Vehicle Routing Planning
(CVRP), Savings-Heuristic for CVRP, Modeling problems with graphs.
A wide range of problems can be expressed with clarity and precision in the concise pictorial language
of graphs [DPV08], p. 80. Graphs are very simple to define: we just take a collection of things and
join some of them by edges. But at this level of abstraction, it’s hard to appreciate the typical kinds of
situations in which they arise. Thus, we propose the following list of specific contexts in which graphs
serve as important models (see here and in the following [KT14], p.74–75).
� Transportation networks: The map of routes served by an airline carrier naturally forms a graph:
the nodes are airports, and there is an edge from u to v if there is a nonstop flight that departs
from u and arrives at v. Described this way, the graph is directed; but in practice when there is an
edge (u, v), there is almost always an edge (v, u), so we would not lose much by treating the airline
route map as an undirected graph with edges joining pairs of airports that have nonstop flights
each way. Looking at such a graph (you can generally find them depicted in the backs of inflight
airline magazines), we’d quickly notice a few things: there are often a small number of hubs with
a very large number of incident edges; and it’s possible to get between any two nodes in the graph
via a very small number of intermediate stops. Other transportation networks can be modeled
in a similar way. For example, we could take a rail network and have a node for each terminal,
and an edge joining u and v if there’s a section of railway track that goes between them without
stopping at any intermediate terminal. The standard depiction of the subway map in a major city
is a drawing of such a graph.
� Communication networks: A collection of computers connected via a communication network can
be naturally modeled as a graph in a few different ways. First, we could have a node for each
computer and an edge joining u and v if there is a direct physical link connecting them. Alter-
natively, for studying the large-scale structure of the Internet, people often define a node to be
the set of all machines controlled by a single Internet service provider, with an edge joining u
and v if there is a direct peering relationship between them—roughly, an agreement to exchange
data under the standard BGP protocol that governs global Internet routing. Note that this latter
network is more ”virtual” than the former, since the links indicate a formal agreement in addition
to a physical connection. In studying wireless networks, one typically defines a graph where the
nodes are computing devices situated at locations in physical space, and there is an edge from u
to v if v is close enough to u to receive a signal from it. Note that it’s often useful to view such a
graph as directed, since it may be the case that v can hear u’s signal but u cannot hear v’s signal
(if, for example, u has a stronger transmitter). These graphs are also interesting from a geometric
perspective, since they roughly correspond to putting down points in the plane and then joining
pairs that are close together.
� Information networks: The World Wide Web can be naturally viewed as a directed graph, in which
nodes correspond to Web pages and there is an edge from u to v if u has a hyperlink to v. The
directedness of the graph is crucial here; many pages, for example, link to popular news sites, but
these sites clearly do not reciprocate all these links. The structure of all these hyperlinks can be
1
used by algorithms to try inferring the most important pages on the Web, a technique employed
by most current search engines. The hypertextual structure of the Web is anticipated by a number
of information networks that predate the Internet by many decades. These include the network
of cross-references among articles in an encyclopedia or other reference work, and the network of
bibliographic citations among scientific papers.
� Social networks. Given any collection of people who interact (the employees of a company, the
students in a high school, or the residents of a small town), we can define a network whose nodes
are people, with an edge joining u and v if they are friends with one another. We could have the
edges mean a number of different things instead of friendship: the undirected edge (u, v) could
mean that u and v have had a romantic relationship or a financial relationship; the directed edge
(u, v) could mean that u seeks advice from v, or that u lists v in his or her e-mail address book.
One can also imagine bipartite social networks based on a notion of affiliation: given a set X of
people and a set Y of organizations, we could define an edge between u ∈ X and v ∈ Y if person u
belongs to organization v. Networks such as this are used extensively by sociologists to study the
dynamics of interaction among people. They can be used to identify the most ”influential” people
in a company or organization, to model trust relationships in a financial or political setting, and
to track the spread of fads, rumors, jokes, diseases, and e-mail viruses.
� Dependency networks. It is natural to define directed graphs that capture the interdependencies
among a collection of objects. For example, given the list of courses offered by a college or university,
we could have a node for each course and an edge from u to v if u is a prerequisite for v. Given a
list of functions or modules in a large software system, we could have a node for each function and
an edge from u to v if u invokes v by a function call. Or given a set of species in an ecosystem,
we could define a graph – a food web – in which the nodes are the different species and there is an
edge from u to v if u consumes v.
This is far from a complete list, too far to even begin tabulating its omissions. It is meant simply
to suggest some examples that are useful to keep in mind when we start thinking about graphs in an
algorithmic context.
We start with some basics and structural properties of graphs, proceed then with problem instances for
graph algorithms, and finish finally with problems where you have to design your own algorithm – based
on known graph algorithms.
References
[DPV08] Dasgupta, S., Papadimitriou, C., Vazirani, U., Algorithms, McGrawHill, 2008.
[KT14] Kleinberg, J., Tardos, E., Algorithm Design, Pearson, 2014.
2
Problem 1. Graphs and their representation. The first question refers to the following directed graph:
–
A
–
B
–
C
–
E
–
D
(a) Give the degrees of the vertices A,B, and E.
(b) What are the direct neighbors of vertex B?
(c) Are there any loops in the graph?
(d) Is this graph a simple directed graph? Explain why or why not.
(e) Does this graph have a source and/or a sink? Explain why or why not.
(f) Is this graph (strongly or weakly) connected or disconnected? Explain your answer.
(g) Give the adjacency matrix representation of the graph.
(h) Give the adjacency list representation of the graph.
Solution:
(a) deg(A) = 4, deg(B) = 6, deg(E) = 5 (loops are double-counted; definition 3, page 652)
(b) A, C, D, E
(c) Yes, loops are (C,C) and (E,E).
(d) No. A simple directed graph has no loops and no parallel edges.
(e) No to both. Sinks have no outgoing edges and sources have no incoming edges. There are no
vertices that satisfy either of those definitions in this graph.
(f) Strongly connected. A strongly connected graph has a path from u to v and v to u for any
vertices u and v in the graph. The entire graph is one giant cycle so clearly you can get from
any vertex to another and back.
(g) 0 1 0 1 0
1 0 1 1 1
0 1 1 0 0
1 0 0 0 1
0 0 1 0 1
(h) A : B,D
B : A,C,D,E
C : B,C
D : A,E
E : C,E
3
Problem 2. Graphs and their representation. The second question refers to the following undirected graph:
–
A
–
B
–
C
–
F
–
D
–
E
(a) Give the degrees of the vertices A,B, and E.
(b) What are the direct neighbors of vertex B?
(c) Are there any cycles in the graph?
(d) Find a path from vertex A to vertex E that is not a simple path.
(e) Is this graph a simple undirected graph? Explain why or why not.
(f) Does this graph have a source and/or a sink? Explain why or why not.
(g) Is this graph (strongly or weakly) connected or disconnected? Explain your answer.
(h) Give the adjacency matrix representation of the graph.
(i) Give the adjacency list representation of the graph.
Solution:
(a) deg(A) = 2, deg(B) = 2, deg(E) = 2
(b) A and C
(c) Yes: A-B-C-A is one cycle. D-E-F-F is another cycle. Note that A-B-C-A-B-C-A would be a
circuit (bot not a cycle as it repeats the vertices B and C (besides the start vertex A). A path
x0, x1, . . . , xn from u = x0 to v = xn of length n > 1 is a sequence of n edges. Length of the
path = number of edges. A path is a circuit if it begins and ends at the same vertex u and has
length greater or equal to 1. A path is a cycle if it is a circuit that does not repeat vertices
(besides u). A path is simple if it does not contain the same edge more than once (sometimes
the term trails is used for simple paths).
One example for a cycle that is not simple would be just two vertices u and v and one edge
{u, v} between them. In that case u− v − u would be a cycle (it begins and ends at the same
vertex u and has length greater or equal to 1, but doesn’t repeat vertices besides vertex u).
But as this cycle would contain the same edge {u, v} more than once it would not be a simple
path.
(d) A path is simple if it does not contain the same edge more than once. This path contains e.g.
the edge {A,B} more than once: A→ B → CA→ B → C → F → E
(e) Yes: Simple Graph = undirected graph with no loops and no parallel edges.
(f) No and no. Impossible for an undirected connected graph to have either a source or as sink.
(g) Strongly connected. An undirected connected graph is always strongly connected, because if
there is a path from a to b, then there is always as well a path from b to a.
(h) 0 1 1 0 0 0
1 0 1 0 0 0
1 1 0 0 0 1
0 0 0 0 1 1
0 0 0 1 0 1
0 0 1 1 1 0
(i) A : B,C
B : A,C
C : A,B, F
D : E,F
E : D,F
F : C,D,E
4
Problem 3. Graph properties. Prove the following claims.
(a) Let G = (V,E) be an undirected graph with |E| edges. Then
∑
v∈V deg(v) = 2|E|.
(b) An undirected graph has an even number of vertices of odd degree.
(c) Let G = (V,E) be a directed graph with |E| edges. Then
∑
v∈V deg
−(v) =
∑
v∈V deg
+(v) =
|E|.
Solution:
(a) Note that every edge counts towards degrees twice: once for the vertex it leaves and one for
the vertex it enters. Therefore, the sum of degrees is exactly the twice the sum of edges.
(b) The previous part tells us that the sum of the degrees is even. Then, the sum of the degrees
for the graph can be broken into the sum of vertices with odd degrees and the sum of even
degrees. However, a sum of even numbers is always even, so that the sum of the odd degrees
must also be even. This only happens if there is an even number of vertices with odd degree.
(c) Every directed edge has exactly one vertex from which it leaves and exactly one vertex to which
it enters. The sum of the in-degrees across all vertices must be exactly the sum of out-degrees
across all vertices.
5
Problem 4. Trees. Draw a Binary Tree of height 3 with a maximum number of leaf nodes. Number the nodes
alphabetically starting with A in the root and then level for level from the left to the right in
increasing order.
(a) What is the parent of node L?
(b) What are the children of node C?
(c) Is the tree balanced? Explain your answer.
(d) Name the leaves of level 3 of the binary tree. How many leaves does this tree have? Can you
generalize your answer?
(e) How many internal vertices does the tree have? Can you generalize your answer?
Solution:
(a) F
(b) F and G
(c) Yes. Every leaf node is at depth of h or h− 1.
(d) Leaves: H, I, J,K,L,M,N,O. This tree has 8 leaves. Number of leaves in a binary tree with
maximum number of leaves is 2h.
(e) This tree has 7 internal nodes. Number of internal nodes in a binary tree with maximum
number of leaf nodes is 2h − 1.
6
Problem 5. Modelling problems with graphs. Say that two actors are co-stars if they have been in the same
movie. Show that in any group of six actors, we can either find a group of three such that all pairs
in the group are co-stars, or a group of three so that no two in the group are co-stars.
Solution:
We want to show that in any group of six actors, at least one of these situations occurs:
(a) There is a group of three actors such that all pairs in the group are co-stars.
(b) There is a a group of three actors so that no two in the group are co-stars.
Choose one particular actor, who we will call actor A. Exactly one of these two things is true:
(i) Actor A has 3 or more co-stars among the group of 6.
(ii) Actor A has less than 3 co-stars among the group of 6.
In Case (i), consider the co-stars of actor A. If no two of them have been co-stars of one another,
then since there are at least three of them, this forms a group of three such that no two in the group
are co-stars, situation (b). If some two of them have been co-stars of one another, then those two
together with actor A form a group of three such that all pairs in the group are co-stars, situation
(a).
In Case (ii), if A has less than 3 costars among the group of 6, that means there are at least three
people with whom he is not a co-star. Consider these non-co-stars of actor A. If all of them have
been co-stars of one another, then since there are at least three of them, this forms a group of three
such that all pairs in the group are co-stars, situation (a). If some two of them are not co-stars,
then those two together with actor A form a group of three in which no two in the group are
co-stars, situation (b).
Thus, in all cases, we can always find situation (a) or (b), which is what we were trying to prove.
Note: We can formulate our answer as a problem of graph theory by constructing an undirected
graph as follows. Let the vertex set V be the set of six actors. Connect two actors with an edge if
they are co-stars. We must show that one of the following two situations occurs:
(a) The graph contains a triangle, i.e. three vertices which are all connected.
(b) The graph contains an anti-triangle, i.e. three vertices, none of which are connected.
Choose one particular vertex, let’s say v, and then the cases become:
(i) degree(v)≥ 3
(ii) degree(v)< 3
The argument is exactly the same, but viewing it as a problem about graphs might help you
to visualize what is going on, and it also frames the question in terms of abstract objects and
relationships, not just the special case of actors with a co-star relationship that we have addressed
here.
7
Problem 6. Directed Acyclic Graphs. A daily flight schedule is a list of all the flights taking place that day. In
a daily flight schedule, each flight Fi has an origin city OCi, a destination city DCi, a departure
time di and an arrival time ai > di. This is an example of a daily flight schedule for August 21,
2016, listing flights as Fi = (OCi, DCi, di, ai):
(a) F1 = (Portland, Los Angeles, 7:00am, 9:00am)
(b) F2 = (Portland, Seattle, 8:00am, 9:00am)
(c) F3 = (Los Angeles, San Francisco, 8:00am, 9:30am)
(d) F4 = (Seattle, Los Angeles, 9:30am, 11:30am)
(e) F5 = (Los Angeles, San Francisco, 12:00pm, 1:00pm)
(f) F6 = (San Francisco, Portland, 1:30pm, 3:00pm)
(a) Describe how to construct a Directed Acyclic Graph (DAG) so that paths in the DAG represent
possible sequences of connecting flights a person could take. What are the vertices, and when
are two vertices connected with an edge?
(b) Why is your graph always a DAG?
(c) Draw the DAG you described for the given example of August 21, 2016.
(d) Use your DAG to help you determine the maximum number of connecting flights a person
could take on August 21, 2016.
Solution:
(a) The vertices are the flights in the daily flight schedule. Draw a directed edge from flight Fi to
flight Fj if
� DCi = OCj (flight Fj leaves from where flight Fi lands), and
� ai < dj (flight Fj leaves after flight Fi lands).
(b) Our graph is always a DAG because it would be impossible to take the same flight more than
once on the exactly same day. This is clear because once you have taken a flight, some time
has elapsed, and you cannot go back in time to take the same flight again.
(c) The following is our DAG:
F1 F2
F3
F4F5
F6
(d) Since paths in the DAG represent possible sequences of connecting flights, the maximum num-
ber of connecting flights a person could take is determined by the longest path in the graph.
Using the graph shown above, we see that the longest path includes four flights (F2, F4, F5, F6),
so the maximum number of connecting flights a person could take on a specific day of the year
is four.
8
Problem 7. Euler and Hamilton.
(a) Describe briefly what the problem of the 7 Bridges of Königsberg is.
(b) What is an Euler Tour? What is an Euler Circuit? What is a Hamilton Tour? What is a
Hamilton Cycle? Is it (from a computationally point of view) harder to compute Hamilton
Tours than to compute Euler Tours? Explain why or why not.
(c) True or false? If a graph G has 3 or more even vertices ↔ G has no Euler tour.
Solution:
(a) The 7 Bridges of Königsberg problem asks whether or not it is possible to start at a certain
place in the town of Königsberg, cross all 7 bridges exactly once each, and return to the same
place in town.
(b) An Euler Tour is a traversal of the graph starting at some vertex v and traversing every edge
exactly once.
An Euler Circuit additionally has the condition of ending at v (and even vertices besides the
start and end vertex might repeat).
A Hamiltonian Tour is a traversal of a graph starting at some vertex v and hitting every single
vertex exactly once.
A Hamiltonian Cycle additionally has the condition of returning to v.
Computationally, Hamiltonian Cycles are significantly more difficult than Euler Circuits.
Euler Circuits (if they exist) can be computed in polynomial time whereas Hamiltonian Cycles
take exponential time.
(c) False. Euler Tour requires that at most 2 vertexes can have odd degrees. A counterexample
would thus simply be a graph with 3 vertexes with even degrees and 3 vertexes with odd
degrees.
9
Problem 8. Hamilton Tours. A ballet recital consists of some number of different acts, each containing several
dancers. Suppose you are given a list of all the acts in the recital, with the names of the dancers
that will appear in each act. Some dancers may be in more than one act, but each act requires a
different costume. To allow the dancers time to change costumes, the recital should be set up so
that no dancer is in two consecutive acts. Our goal is to find an ordering of the acts for the recital
so that no dancer is in back-to-back acts.
(a) Describe how to model this situation using a graph. Carefully describe what the vertices of
your graph represent, and when two vertices are connected with an edge.
(b) Now that you’ve modeled the situation with a graph, which problem from graph theory are
you trying to solve on this graph?
(c) Is it always possible to achieve the goal? Explain.
Solution:
(a) The vertices are the acts of the show. Connect two vertices (acts) with an undirected edge if
they do not share any dancers.
(b) We want to find a path that uses every vertex exactly once, or a Hamilton tour.
(c) No. If the show has only two acts and there is somebody in both acts, we cannot achieve the
goal. In other words, not every graph has a Hamilton tour.
10
Problem 9. Prim’s algorithm for Minimum Spanning Trees.
procedure Prim(G: undirected, weighted connected graph)
T := a minimum weight edge
for i := 1 to n− 2
e := (u, v) an edge of minimum weight incident to a vertex in T and does not form a loop in T
T := T ∪ {e}
return T
(a) Prove the correctness of Prim’s algorithm.
(b) Prove the time complexity of Prim’s algorithm.
Solution:
(a) The loop invariant is that after the k-th loop iteration, T has the first k + 1 edges and k + 2
nodes of the minimum spanning tree. We prove this by induction on the iterations of the loop.
Base Case: Before entering the loop, k = 0, and we have the lowest weight edge with its
attached vertices.
Induction Hypothesis: Assume that after k − 1 iterations, we have the the first k edges in
a minimum spanning tree and the first k + 1 nodes.
Induction Step: Here, we add a minimal edge that does not loop with T . By the IH, T has
the first k edges and k+1 nodes of a minimal spanning tree before we add this edge. Therefore,
T ∪ {e} is the first k + 1 edges and k + 2 vertices of a minimum spanning tree.
(b) Since we delete all edges, this takes time O(m). We find a new edge n times. This results in a
total time complexity of O(n log n + m).
11
Problem 10. Topological Sorting. Imagine you would have to perform in a project jobs A,B,C,D,E, F with the
following time dependencies:
� B must be finished before you can start with D,E, F .
� C must be finished before you can start with B,E.
� D must be finished before you can start with A,E.
� E must be finished before you can start with A.
� F must be finished before you can start with D.
The underlying graph is depicted here:
B
C
E
D
A
F
When you want to answer if all of the time dependencies can be fulfilled: what graph theoretic
problem do you have to solve? Apply the corresponding algorithm to that problem. In what order
will you have to perform the jobs?
indeg
A
B
C
D
E
F
9
Solution:
Your goal is to find an order in which the jobs can be performed such that all prerequisites are
fulfilled. This is a topological sort. The only possible order is C → B → F → D → E → A.
indeg {C} {B} {F} {D} {E} {A}
A 2 2 2 2 1 0 -
B 1 0 - - - - -
C 0 - - - - - -
D 2 2 1 0 - - -
E 3 2 1 1 0 - -
F 1 1 0 - - - -
9 7 4 3 1 0 -
12
Problem 11. Topological Sorting.
(a) Determine the topological sort of the graph. Hint: The sum of the in-degrees is 12.
B E G
C
D
A F H
2
5
3
3
9
3
2
1 27 4
6
indeg
A
B
C
D
E
F
G
H
12
(b) Explain in your own words why Bellman’s algorithm always finds an optimal solution for the
SSSP-problem, if the network is acyclic.
(c) Find a SSSP-solution using Bellman’s algorithm with starting vertex A for the following graph.
B E G
CA F H
2
5
3
3
9
3 1 27 4
Solution:
(a) The topological order provided by the graph is {A,D} → {C} → {B} → {E} → {F,G} →
{H}.
indeg {A,D} {C} {B} {E} {F,G} {H}
A 0 - - - - - -
B 2 1 0 - - - -
C 2 0 - - - - -
D 0 - - - - - -
E 1 1 1 0 - - -
F 4 3 2 1 0 - -
G 1 1 1 1 0 - -
H 2 2 2 2 2 0 -
12 8 6 4 2 0 -
13
(b) When we utilize Bellman’s Algorithm, our relaxation follows the order of vertices provided by
the topological sort, which we previously figured out with the correct dependence relations.
As we relax each vertices according to the topological order, we are making sure that we are
moving down a one-way path, such that after each vertices are relaxed, there is no way back
(acyclic assumed). Also, when we relax each vertices, we are making sure that all paths from
that vertex are considered, ensuring the algorithm to include all possible paths. Within the
procedures, we only keep the shortest paths. Thus, we then can conclude that we are always
finding the optimal solution for SSSP-problems.
(c) Topological Sort: {A} → {C} → {B} → {E} → {F,G} → {H}
indeg {A} {C} {B} {E} {F,G} {H}
A 0 - - - - - -
B 2 1 0 - - - -
C 2 0 - - - - -
E 1 1 1 0 - - -
F 3 3 2 1 0 - -
G 1 1 1 1 0 - -
H 2 2 2 2 2 0 -
10 8 6 4 2 0 -
(A,B) (A,C) (B,E) (B,F) (C,B) (C,F) (E,F) (E,G) (F,H) (G,H)
Relax 7 2 5 4 3 3 1 3 9 2
Bellman Solution Tree:
A 0
B 7 C 2
B 5 F 5
E 10 F 9 H 14
F 11 G 13
H 15
7 2
3 3
5 4 9
1 3
2
1.
2.
3.
4.
5.
6.
7.
u A B C E F G H
dist(A, u) 0 5 2 10 5 13 14
14
Phase Notations: (Note nothing changes when we relax G and H.)
A B C E F G H
Initializtion 0 ∞ ∞ ∞ ∞ ∞ ∞
(1) Relax A edges 7 2
(2) Relax C edges 5 5
(3) Relax B edges 10
(4) Relax E edges 13
(5) Relax F edges 14
(6) Relax G edges
(7) Relax H edges
Result 0 5 2 10 5 13 14
15
Problem 12. Single-source shortest paths. Find a Single Source Shortest Paths solutions. Use starting node A.
A C E
B D F
10
20
50
10
20
23
20
2
2
(a) Use the Bellman algorithm. Begin with a topological sort.
(b) Use the Dijkstra algorithm.
Solution:
(a) The topological order provided by the graph is {A} → {B,C} → {D} → {E} → {F}.
indeg {A} {B,C} {D} {E} {F}
A 0 - - - - -
B 1 0 - - - -
C 1 0 - - - -
D 2 2 0 - - -
E 3 3 1 0 - -
F 2 2 2 1 0 -
9 7 3 1 0 -
(A,B) (A,C) (B,D) (B,E) (C,D) (C,E) (D,E) (D,F) (E,F)
Relax 10 20 50 10 20 23 20 2 2
A 0
B 10 C 20
D 60 E 20 D 40 E 43
F 22 E 60 F 42
10 20
50
10 20
23
2
20 2
1.
2. 3.
4.5.
6.
u A B C D E F
dist(A, u) 0 10 20 40 20 22
Phase notation: (Note nothing changed when we relaxed E)
A B C D E F
Initialization 0 ∞ ∞ ∞ ∞ ∞
(1) Relax A edges 10 20
(2) Relax B edges 60 20
(3) Relax C edges 40 (43)
(4) Relax D edges (60) 42
(5) Relax E edges 22
(6) Relax F edges
Result 0 10 20 40 20 22
16
(b) Dijkstra:
(A,B) (A,C) (B,D) (B,E) (C,D) (C,E) (D,E) (D,F) (E,F)
Relax 10 20 50 10 20 23 20 2 2
Graphic Solution Tree:
A 0
B 10 C 20
D 60 E 20 D 40 E 43
F 22 F 42E 60
10 20
50
10 20
23
2 20 2
1.
2. 3.
4.
5.
6.
u A B C D E F
dist(A, u) 0 10 20 40 20 22
Phase notation: (Note nothing changes in Phase 5 and 6)
A B C D E F
Init 0 ∞ ∞ ∞ ∞ ∞
(1) Relax A edges 10 20
(2) Relax B edges 60 20
(3) Relax C edges 40 (43)
(4) Relax E edges 22
(5) Relax F edges
(6) Relax D edges (60) (42)
Result 0 10 20 40 20 22
17
Problem 13. Properties of SSSP-algorithms.
(a) What do Bellman-Ford, Bellman’s, and Dijkstra’s algorithm have in common? Where do they
differ?
(b) Prove the correctness of Bellman/Ford’s algorithm, and perform a time analysis.
(c) Prove the correctness of Bellman’s algorithm, and perform a time analysis.
(d) Prove the correctness of Dijkstra’s algorithm, and perform a time analysis.
Solution:
All of these algorithms find the shortest distance from one vertex to all of the vertices. All of them
use the initialize function where the distance from the single source s is set to 0 and the distances
from s to all other vertices is set to inf. All three algorithms use the relax function: If the current
shortest path from s to v is greater than the current shortest path from s to u plus c(u, v), then
the shortest path from s to v is updated to pass through u.
Bellman/Ford relaxes every edge in each of the n − 1 iterations. Therefore it executes the relax
function (n− 1) ·m times.
Dijkstra’s algorithm only works on non-negative networks, i.e. c(u, v) ≥ 0 for all edges (u, v).
Bellman’s algorithm only works on acyclic networks and uses the topological sort of the network.
Both algorithms relax only these edges in one iteration that start with a certain vertex u: Dijkstra:
Select u that has minimum distance to the source. Bellman: Select u that comes next in the
topological sort.
Let us now consider the situation when we close up a vertex u: In both algorithms, we have saved
the shortest detected path from s to u at this timepoint of the algorithm.
Dijkstra works because there might be another path to u, but only for higher cost (u has minimal
distance to the source). Bellman works because there is simply no other path to u, because u is
the next vertex in the topological sort.
Runtime Dijkstra: Dijkstra relaxes every edge exactly once. In order to always select that vertex
that has minimal distance to the source, we have to build and maintain a priority queue data struc-
ture that supports the following operations: initialize (costs O(n)), n times deletemin (costs
O(n2) if we use an array and O(n log n) if we use a Fibonacci Heap), and m times decreasekey
(costs O(m)). In total we come so to O(n2 + m) if we use an array and O(n log n + m) if we use a
Fibonacci Heap.
Runtime Bellman: The topological sort costs O(n) and Bellman relaxes every edge exactly once.
Therefore the total cost is O(n + m) - the asymptotically best of the three algorithms.
18
Problem 14. Floyd/Warshall’s algorithm for the All-Pairs-Shortest-Paths problem.
A B C
D E F
3 5
73
5 -2 93
Vertex A
A B C D E F
A
B
C
D
E
F
Vertex B
A B C D E F
A
B
C
D
E
F
Vertex C
A B C D E F
A
B
C
D
E
F
Vertex D
A B C D E F
A
B
C
D
E
F
Vertex E
A B C D E F
A
B
C
D
E
F
Vertex F
A B C D E F
A
B
C
D
E
F
Solution:
Vertex A
A B C D E F
A 0 3 5
B 0 -2
C 5 0 3
D 0
E 3 0 7
F 9 0
Vertex B
A B C D E F
A 0 3 5 1
B 0 -2
C 5 0 3
D 0
E 0 7
F 9 0
Vertex C
A B C D E F
A 0 3 5 1
B 0 -2
C 5 0 3
D 0
E 3 0 7
F 14 9 12 0
Vertex D
A B C D E F
A 0 3 5 1
B 0 -2
C 5 0 3
D 0
E 3 0 7
F 14 9 12 0
19
Vertex E
A B C D E F
A 0 3 4 1 8
B 0 1 -2 5
C 5 0 6 3 10
D 0
E 3 0 7
F 14 9 15 12 0
Vertex F
A B C D E F
A 0 3 17 4 1 8
B 0 14 1 -2 5
C 5 0 6 3 10
D 0
E 21 16 3 0 7
F 14 9 15 12 0
20
Problem 15. MST-heuristic for the Travelling Salesperson Problem.
(a) Determine the Minimum Spanning Tree (MST) using the algorithm of Prim, Starting point is
node O.
A B
E
O
F
C
D
HG
4
6
5
1
58
7 6
2 3
4
2
4
9
2
5 1
(b) Determine a round trip that starts and ends in node O and is generated with the MST-heuristic
is generated. Hint: Construct an Euler tour first and then take shortcuts.
A B
E
O
F
C
D
HG
Solution:
Please see the lecture video.
21
Problem 16. MST-heuristic for the Travelling Salesperson Problem.
(a) Determine the Minimum Spanning Tree (MST) using the algorithm of Prim, Starting point is
node O.
O A B C
D E F
2 5 6
8 2
3 2 56 4
(b) Determine a round trip that starts and ends in node O and is generated with the MST-heuristic
is generated. Hint: Construct an Euler tour first and then take shortcuts.
O A B C
D E F
(c) Prove: The MST-heuristic is a 2-approximation for the Travelling Salesperson Problem.
(d) Establish a lower bound for the length of an optimal TSP-tour.
Solution:
(a) Minimum Spanning Tree:
O A B C
D E F
2 5
2
3 2 4
(b) Length of the Euler-tour: 36, Shortcuts: 33.
(c) Doubling the edges of a MST gives me a feasible roundtrip that has total length 2·MST-length,
this gives us an upper bound for the optimal tour length: l(TSP )∗ ≤ 2 · l(MST ).
(d) The MST-length is a lower bound for the optimal length of a roundtrip: l(TSP )∗ ≥ l(MST ) .
22
Problem 17. Savings heuristic for Capacitated Vehicle Routing Planning. Consider the following graph. The
depot is marked with O. The time required to get from one place to another on the respective route
is shown at each edge.
O A B C
D E F
2 5 6
8 2
3 2 56 4
There are Q = 10 units per truck available. The demand of each customer are in the following
table.
A B C D E F
3 4 2 5 6 3
The distances of the shortest paths can be found in the following table.
O A B C D E F
O 0 2 7 12 5 8 10
A 0 5 10 3 6 8
B 0 6 8 2 4
C 0 12 4 5
D 0 8 10
E 0 2
F 0
(a) Calculate the total length of the tour planning if only round trips are used.
(b) Calculate the Savings values and enter the Savings values in the table:
O A B C D E F
O - - - - - - -
A - -
B - - -
C - - - -
D - - - - -
E - - - - -
F - - - - - - -
(c) Apply the Savings heuristic for Capacitated Vehicle Routing Planning. Which tours are gen-
erated in this way? How big is the saving compared to the round trips?
Solution:
(a) Round Trips: 88 miles.
(b) Savings values:
O A B C D E F
O - - - - - - -
A - - 4 4 4 4 4
B - - - 13 4 13 13
C - - - - 5 16 17
D - - - - - 5 5
E - - - - - - 16
F - - - - - - -
(c) sC,F = 17
O → C → F → O (5)
sC,E = 16
C and E are immediate neighbors from O (C in the tour O → C → F → O and E in the tour
23
O → E → O).
But the remaining Capacity (5 left) is not sufficient to combine C and E in one tour O → E →
C → F → O (we would need 11 total).
sE,F = 16
E and F are immediate neighbors from O, but Capacity no sufficient.
sB,C = 13
Immediate neighbors: yes.
Capacity: yes.
New tour: Combine O → C → F → O and O → B → O to O → B → C → F → O (9)
Close up this tour as there is only 1 unit left. The minimum capacity of the remaining customers
is 3.
Delete all Savings values that include customers of this closed tour, i.e. B,C, F .
The only remaining Savings values are: sD,E = 5, sA,D = 4, sA,E = 4.
sD,E = 5
Capacity not sufficient.
sA,D = 4
Immediate neighbors: yes.
Capacity: yes.
New tour: Combine O → A→ O and O → D → O to O → A→ D → O (8)
Close up this tour as there is only 2 units left. The minimum capacity of the remaining
customer is 6.
Delete all Savings values that include customers of this closed tour, i.e. A,D.
No Savings values left and the algorithm terminates.
Result:
Tour 1: O → B → C → F → O (9 and 28 miles)
Tour 2: O → A→ D → O (8 and 10 miles)
Tour 3: O → E → O (6 and 16 miles)
Total tour length: 28 + 10 + 16 = 54 miles.
Total Savings: 88 miles (roundtrips) - 54 miles (Savings heuristic) = 34 miles.
24
25
Problem 18. Savings heuristic for Capacitated Vehicle Routing Planning. Consider the following graph. The
depot is marked with O. The time required to get from one place to another on the respective route
is shown at each edge.
O
A
C
B
D
9
4
3
7
2 4
There are Q = 10 units per truck available. The demand of each customer are in the following
table.
A B C D
2 5 4 4
The distances of the shortest paths can be found in the following table.
O A B C D
O 0 5 9 3 10
A 0 4 2 8
B 0 6 4
C 0 7
D 0
(a) Calculate the total length of the tour planning if only round trips are used. Note: Not
necessarily the direct route (e.g. O-A 9 hours travel time) is the fastest route (faster is O-C-A
with a total duration of 5 hours).
(b) Calculate the Savings values and enter the Savings values in the table:
O A B C D
O - - - - -
A - -
B - - -
C - - - -
D - - - - -
(c) Apply the Savings heuristic for Capacitated Vehicle Routing Planning. Which tours are gen-
erated in this way? How big is the saving compared to the round trips?
Solution:
(a) Round Trips Only: 27 · 2 = 54 miles
(b) Savings values:
O A B C D
O - - - - -
A - - 10 6 7
B - - - 6 15
C - - - - 6
D - - - - -
(c) sB,D = 15
O → B → D → O (9)
Close up this tour as there is only 1 unit left. The minimum capacity of the remaining customers
is 2.
Delete all Savings values that include customers of this closed tour, i.e. B,D.
sA,C = 6
Immediate neighbors: yes.
Capacity: yes.
New tour: Combine O → A→ O and O → C → O to O → A→ C → O (6)
26
No Savings values left and the algorithm terminates.
Result:
Tour 1: O → B → D → O (9 load and 15 miles savings)
Tour 2: O → A→ C → O (6 load and 6 miles savings)
new tours have a total length of 54 miles (roundtrips) - 21 miles (Savings heuristic) = 33 miles.
27
Problem 19. There are n cities on a plane with coordinates (x1, y1), (x2, y2), . . . , (xn, yn). All cities are distinct
and located at different points on the plane. The city 1 has access to electricity. You need to
connect cities with wires, such that all cities will have access to electricity. A city has access to
electricity if it is city 1 or if it is connected with a wire to another city, that has access to electricity.
The length of the wire that connects the two cities equals the euclidean distance between these
cities. Your task is to connect the cities with wires, such that the total length of all wires is
minimized.
(a) Develop an algorithm that solves this problem.
(b) Prove its correctness.
(c) Find its time complexity.
Solution:
(a) Let matrix d[i][j] be equal to the euclidean distance between cities i and j, i.e. d[i][j] =√
(xi − xj)2 + (yi − yj)2. As a result, we have a full graph G = (V,E) with nodes as cities
and the weight on edges as euclidean distances between the cities. In order to find the answer,
we will find the minimum spanning tree of this graph. This tree will be the answer to our
problem.
(b) Let G′ = (V ′, E′) be a graph that connects all nodes in G and the sum of weights in this graph
is as small as possible. Let’s find the minimum spanning tree of G′. The sum of weights in the
minimum spanning tree of G′ will be less than or equal to the sum of weights of graph G’, thus
it will be optimal. But as G′ is a subgraph of G, then the total sum of weights of the spanning
tree of G is less than or equal to the sum of all weights in the spanning tree of G′. Thus, it is
also optimal.
(c) The time complexity of this solution equals the time complexity of finding the minimum span-
ning tree in a full graph. If we apply Prim’s algorithm to this purpose, then the time complexity
is O(n2).
28
Problem 20. There is a set of n courses. Each course has its prerequisites (from the same set). So course i is
assigned a set of courses that are required to be completed before course i starts. You are given a
set of n courses, and each course is provided with a list of prerequisites. Find a schedule (a list) of
courses, if such exists, such that all n courses are in this list and they all can be completed. If there
is no such a schedule, just output −1. As an example, we have 5 courses and a list (A,D,C,B,E).
We go from left to right and try to complete a current course. If all prerequisites for the current
course are completed, then the current course can also be completed.
(a) Develop an algorithm that solves this problem.
(b) Prove its correctness.
(c) Find its time complexity.
Solution:
(a) Let’s construct a graph G = (V,E), |V | = n, |E| = m, such that each node represents some
course. There is a directed edge from node u to node v if the course for node u is a prerequisite
for the course for node v. Now, we have a directed graph. Let’s find topological sorting of this
graph. If there is such, then the list will be courses given in a topological sorted order of their
corresponding nodes.
(b) Let’s say v1, v2, . . . , vn is a topological order of nodes in graph G. Then, from the properties
of the topological sort we know, that there is no edge from vi to vk, when i > k, i.e. all
corresponding courses can be completed. This list also includes all nodes, which makes it a
valid schedule. Now, let’s say u1, u2, . . . , un is a list of nodes, which correspond to courses from
the answer to this problem. Then, this list will also be the one of the topological orders of
graph G. Indeed, as this is a valid schedule, all courses can be completed, i.e. there can only
be edges (vi, vk), such that i < k.
(c) The time complexity is to construct a graph and to find its topological order, i.e. O(n + m).
29
Problem 21. You are given a rooted tree G = (V,E), |V | = n, |E| = m. You have q online queries (u, v). For
each query (u, v) you need to answer whether u is an ancestor of v in the tree G.
(a) Develop an algorithm that solves this problem.
(b) Prove its correctness.
(c) Find its time complexity.
Solution:
(a) Let’s use DFS to solve this problem. We launch DFS from the root. We will need two
additional values for each node v: in[v] and out[v]. in[v] is a time when DFS visits node v.
out[v] is a time when DFS leaves node v. The time starts with zero and increases by one each
time we enter or quit some node in DFS. Then, if in[a] < in[b] and out[b] < out[a], a is an
ancestor of b.
(b) If in[a] < in[b], this means that we have visited a sometime before we have visited b. If
out[b] < out[a], this means that by the time we have left b, we are still in the subtree, in which
a is a root.
Now, if a is an ancestor of b, then we will visit a first, then we will visit b, then we will quit b
and, finally, we will quit a. This leads to our inequality.
(c) We need O(n + m) for DFS and O(q) for all queries. Each query takes O(1) time to answer.
The overall complexity will be O(n + m + q).
30
Problem 22. You are given an undirected unweighted graph G = (V,E), |V | = n, |E| = m. Determine, whether
this graph contains a circuit or not.
(a) Develop an algorithm that solves this problem.
(b) Prove its correctness.
(c) Find its time complexity.
Solution:
(a) We will use a DFS algorithm to solve this problem. Let’s color each node to two colors: red
and blue. If the node hasn’t been visited yet by DFS, then the color of the node is red.
Otherwise, the color of the node is blue. If at some step DFS tries to visit the node with the
blue color, then there exists a circuit.
(b) If the DFS algorithm is trying to enter a node v with the blue color from node u, this means
that we have visited v before. If we take the path from v to u (which was constructed by a
DFS tree) and add to this path edge (u, v), which exists as we are trying to visit node v from
u, then we will get a circuit. If there exists a circuit in the graph, then, at some point, DFS
will visit one of its nodes. Let that node be v. As node v is part of a circuit, it has at least
two edges (v, a) and (v, b), such that there is a path from a to b that doesn’t go through v.
This path will be processed sooner or later by DFS and we will get to node b from a. Then,
we will try to visit v, which is going to have the blue color.
(c) The complexity of the solution equals the complexity of DFS, i.e. O(n + m)
31
Problem 23. There are n cities on a plane with coordinates (x1, y1), (x2, y2), . . . , (xn, yn). All cities are distinct
and located at different points on the plane. The city 1 has access to electricity. You need to
connect cities with wires, such that all cities will have access to electricity. A city has access to
electricity if it is city 1 or if it is connected with a wire to another city, that has access to electricity.
The length of the wire that connects the two cities equals the euclidean distance between these
cities. Your task is to connect the cities with wires, such that the total length of all wires is
minimized.
(a) Develop an algorithm that solves this problem.
(b) Prove its correctness.
(c) Find its time complexity.
Solution:
(a) Let matrix d[i][j] be equal to the euclidean distance between cities i and j, i.e. d[i][j] =√
(xi − xj)2 + (yi − yj)2. As a result, we have a full graph G = (V,E) with nodes as cities
and the weight on edges as euclidean distances between the cities. In order to find the answer,
we will find the minimum spanning tree of this graph. This tree will be the answer to our
problem.
(b) Let G′ = (V ′, E′) be a graph that connects all nodes in G and the sum of weights in this
graph is as small as possible. Let’s find the minimum spanning tree of G′. The sum of weights
in the minimum spanning tree of G′ will be less than or equal to the sum of weights of graph
G′, thus it will be optimal. But as G′ is a subgraph of G, then the total sum of weights of
the spanning tree of G is less than or equal to the sum of all weights in the spanning tree of
G′. Thus, it is also optimal.
(c) The time complexity of this solution equals the time complexity of finding the minimum
spanning tree in a full graph. If we apply Prim’s algorithm to this purpose, then the time
complexity is O(n2).
32
Problem 24. You have a chess board n × m. There is a knight on cell (xs, ys). The knight can make moves
from cell (x, y) to cells (x + 1, y + 2), (x − 1, y + 2), (x + 1, y − 2), (x − 1, y − 2), (x + 2, y − 1),
(x− 2, y− 1), (x + 2, y + 1) and (x− 2, y + 1) (all cells must be on the board). Find the minimum
number of steps the knight needs to make to get from cell (xs, ys) to cell (xf , yf ).
(a) Develop an algorithm that solves this problem.
(b) Prove its correctness.
(c) Find its time complexity.
Solution:
(a) If we assume that each cell of the board is a node, then we can connect a node that corresponds
to cell (x, y) with nodes that correspond to cells (x + 1, y + 2), (x − 1, y + 2), (x + 1, y − 2),
(x− 1, y− 2), (x+ 2, y− 1), (x− 2, y− 1), (x+ 2, y + 1) and (x− 2, y + 1) (all cells must be on
the board) with undirected edges. As a result, we will have an undirected unweighted graph.
We then launch BFS from the node which corresponds to cell (xs, ys) and find the distance
to the node which corresponds to cell (xf , yf ).
(b) Let’s assume that we have an optimal sequence of steps from cell (xs, ys) to (xf , yf ). As we
can see, this sequence will correspond to some path in the constructed graph from the node
that corresponds to cell (xs, ys) to the node that corresponds to cell (xf , yf ). But as BFS
always finds the minimum distance from the node from which it starts to all other nodes, then
the path found in BFS will also be optimal.
(c) The time complexity equals the time complexity of BFS. There are nm nodes in the con-
structed graph and less than 4nm edges. The overall time complexity is O(nm).
33
Problem 25. You are given an undirected connected weighted graph G = (V,E), |V | = n, |E| = m. The weights
of all edges are positive integer numbers. Your task is to delete edges in this graph so that the
resulting graph will be connected and the product of all weights of all edges in this graph will be
as small as possible.
(a) Develop an algorithm that solves this problem.
(b) Prove its correctness.
(c) Find its time complexity.
Solution:
(a) Let’s construct another graph G′ = (V ′, E′), such that V ′ = V , E = E′ and w(e′) = log(w(e))
for all e′ ∈ E′ and e ∈ E. Then, we will find the minimum spanning tree in G′ with Prim’s
algorithm. We will take the same tree G (the same nodes and edges). This tree in G will be
the graph that we are looking for.
(b) When we are looking for the minimum spanning tree in G′, we are minimizing the following
function log(w(e′1))+ log(w(e
′
2))+ . . .+log(w(e
′
k)) = log(w(e
′
1)w(e
′
2) . . . w(e
′
k)), where k is the
number of edges in the resulting graph. But minimizing log(x) for x > 0 means minimizing
x. Thus, we are minimizing function w(e′1)w(e
′
2) . . . w(e
′
k), when we search for the minimum
spanning tree.
(c) The time complexity equals the number of operations required to get a new graph plus the
time complexity of Prim’s algorithm, i.e. O(n + m) + O(n log n + m) = O(n log n + m).
34
Problem 26. There is a set of n courses. Each course has its prerequisites (from the same set). So course i is
assigned a set of courses that are required to be completed before course i starts. You are given a
set of n courses, and each course is provided with a list of prerequisites. Find a schedule (a list)
of courses, if such exists, such that all n courses are in this list and they all can be completed. If
there is no such a schedule, just output −1.
For example, let’s say we have 5 courses and a list (A,D,C,B,E). We go from left to right and
try to complete a current course. If all prerequisites for the current course are completed, then the
current course can also be completed.
(a) Develop an algorithm that solves this problem.
(b) Prove its correctness.
(c) Find its time complexity.
Solution:
(a) Let’s construct a graph G = (V,E), |V | = n, |E| = m, such that each node represents some
course. There is a directed edge from node u to node v if the course for node u is a prerequisite
for the course for node v. Now, we have a directed graph. Let’s find topological sorting of
this graph. If there is such, then the list will be courses given in a topological sorted order of
their corresponding nodes.
(b) Let’s say v1, v2, . . . , vn is a topological order of nodes in graph G. Then, from the properties
of the topological sort we know, that there is no edge from vi to vk, when i > k, i.e. all
corresponding courses can be completed. This list also includes all nodes, which makes it a
valid schedule. Now, let’s say u1, u2, . . . , un is a list of nodes, which correspond to courses
from the answer to this problem. Then, this list will also be the one of the topological orders
of graph G. Indeed, as this is a valid schedule, all courses can be completed, i.e. there can
only be edges (vi, vk), such that i < k.
(c) The time complexity is to construct a graph and to find its topological order, i.e. O(n + m).
35
Problem 27. You are given a weighted directed graph G = (V,E), |V | = n, |E| = m with positive weights. You
are also given a node s in this graph. Find such node v, such that there is a path from v to s and
that among all possible such nodes, the shortest path from v to s is as large as possible.
(a) Develop an algorithm that solves this problem.
(b) Prove its correctness.
(c) Find its time complexity.
Solution:
(a) Let’s construct graph G′ = (V ′, E′) such that G′ is a copy of G, but all edges are directed in
an opposite direction. Let’s find shortest paths from node s to all other nodes in G′. We can
do this with Dijkstra’s algorithm. Then, among all these paths, we choose the one with the
maximum value. The node, to which this path leads is the answer to our problem.
(b) Any path from s to v in G is a path from v to s in G′ and vice versa. This means that
the shortest path from v to s in G is the shortest path from s to v in G′. This proves the
correctness of our solution.
(c) The time complexity equals the time complexity of building graph G′ and using Dijkstra’s
algorithm on it, i.e. O(n + m) + O(n log n + m) = O(n log n + m).
36