Fundamentals of Computer Science

Exercises on Graphs and Regular Languages

March 2017

Graphs
Exercise 1 (Dijkstra’s algorithm). If you forgot how Dijkstra’s algorithm (for finding a shortest path in a
graph with only positive weigths) works, please look it up.
Describe an algorithm to carry out the following tasks:

1. Find the shortest path to all nodes from a given source node given the graph only contains positive
weights.
2. The shortest path for a graph in which edges can have negative weights. If the graph contains a cycle
with strictly negative weight, the algorithm must detect that. (look up Bellman-Ford)

3. Find the longest simple path for a given graph with only positive weights.
Prove that your algorithm is correct.
Hint. A modification of Dijkstra’s algorithm might be sufficient. 

Answer. First we will briefly sketch the working principle of Dijkstra’s algorithm. Dijkstra’s algorithm labels
vertices considers a priority queue. Initially all vertices are labeled with h+∞, falsei except the source vertex
s which is labeled with h0, falsei. The label contains the shortest path to the corresponding vertex up to
that point of the algorithm. Dijkstra’s algorithm schedules the source vertex s in the priority.

As long as there are items in the priority queue, the first item is selected. If the node is already visited (the
second element of the label of the vertex), we ignore the vertex. Otherwise we first set the second element
of the label to true, the first element of the label is called the weight of the vertex wv . Next we iterate over
all outgoing edges hv, ui ∈ E (v) of v, we calculate the target weight wu as wu = wv + we with w the weight
of the edge. If the target weight is lower than the weight of the vertex u at that moment, we modify the
weight and schedule u in the priority queue. Otherwise, we leave u unmodified. The algorithm stops when
the destination vertex d is scheduled first in the priority queue.
Proof. Dijkstra’s algorithm works correct because it guarantees progression if the weights of all edges are
positive: each time a node is expanded, the weight of that node is the weight shortest path between the
source and that vertex. This is true, because the priority queue is dequeued by increasing weight. Given
there is shorter path hv1 , v2 , . . . , vn i to vertex that is expanded, the the weight of vertex vn−1 has a weight
lower than the weight of the vertex. But in that case vn−1 would have been expanded earlier and thus further
have minimized the weight for vn .

1. We modify the stop criterion of Dijkstra’s algorithm so that it stops when the priority queue is empty.

1
 Proof. This algorithm is correct because eventually all vertices connected with the given source index
will be scheduled: if the vertex v is connected with the source s, there is a path hs, v1 , v2 , . . . , vi between
the the source vertex and that vertex. Since we definitely expand s, v1 is placed on the priority queue,
and each vertex vi is scheduled because at least the previous vertex vi−1 is scheduled. So at least all
vertices will eventually get scheduled. Since Dijkstra’s algorithm only expands a node if there is no
shorter path between the source and that node, all connected nodes are expanded and marked with
the weight of the shortest path.

2. This is the well known Bellman-Ford algorithm. Dijkstra’s algorithm works on a node-by-node basis
where each node is placed in a queue and processed. Since Dijkstra’s algorithm guarantees - based on
the fact that all edges have positive weights - progression, we know for sure that the node expanded is
optimal. This is no longer possible if the graph can contain negative edges. Bellman-Ford’s algorithm
still labels the vertices but only with the weights. All vertices are thus labeled with ∞ except the
source node which is labeled with 0. The the following step is repeated n times with n − 1 the number
of vertices or until the weights of the vertices no longer change if that occurs earlier.
Iterate over all edges e = hu, vi ∈ E. If u has a weight wu and e weight we , if wu + we ≤ wv ,
then set wv0 = wu + we .

Now we perform the operation a final time. If the weights still change, we have obtained a negative
cycle so there is no shortest path, if not we can reconstruct the path by backwards reasoning as we do
for Dijkstra’s algorithm.

Proof. We will only prove the case of iterating the step n − 1 times. One can easily modify the proof
to show that it works if one iterates until the weights no longer modify. Say the optimal path between
the source s and d is hs, v1 , v2 , . . . , vm , di. Since the number of vertices is n there cannot exists a longer
(shortest) path than a path with n − 1 edges. This thus means that m ≤ n − 2. The first time we call
the subroutine, all vertices are labeled ∞ except the source. After applying the first step, all vertices
to which an edge from the source are labeled with a value that is optimal for paths with one edge or
lower (for zero edges, we can only reach the source node which has weight 0).

Given we have iterated over the first i steps - thus obtain the shortest path to each vertex with i
edges or lower - now we iterate over all edges we thus virtually “add” an edge to the optimal paths
with i or less edges. If the constructed path is shorter (less weight), that means that the last vertex of
the end has a weight that was higher. We thus replace is with the weight of the new path. After we
have done this for every edge, the vertices are labeled with the shortest path with i + 1 edges or less.

Since we do this n − 1, times, the vertices are labeled with a path that contain n − 1 or less edges.
This is the largest path with respect to the number of edges possible. If by applying the step again
weights change, this means that for at least one vertex, there exists a path of length n results in a
shorter path than that of n − 1. A path that contains n edges however contains at least one edge twice,
this thus means there is a loop somewhere. In that case it is beneficial to keep looping over the graph,
otherwise one would never have added the edge twice.

Given there is no such loop, we have calculated the weights for all the vertices for paths with at most
n − 1 edges. Since we know there are no cycles, it means we have iterated over all cycle-free paths and
that the destination vertex v will be marked with the shortest path.

3. If the graph does not contain positive edges, one can use the Bellman-Ford algorithm where we replace
the weight of every edge with its negative counterpart. This is however not an assumption we can
make. One can expect that if there is a positive cycle, we simply keep running through that cycle.

2
 The definition of simple path however states that it can contain every edge at most once. If thus enter
a positive cycle, we need to exit the cycle at last before we traverse an edge for the second time. You
cannot incorporate this behavior in Dijkstra’s algorithm because the edges it has already traversed is a
property that scales with the length of the path. There are thus an exponential amount of paths each
with different context. As a result one has to implement a backtracking algorithm that considers all
possible paths. The problem is NP-hard and there is an easy reduction from the Hamiltonian cycle
problem.

Proof. Since the backtracking algorithm iterates over all possible paths up to length n − 1 - thus all
real paths - and evaluates the weight of these paths, evidently the algorithm will come up with the
longest path.


Exercise 2 (adjacency matrix).
1. Construct the adjacency matrix of the graph in Figure 1.

2. Use this matrix to determine whether there is a path between a and d.

3. If so, what is the minimum number of edges in such a path? How can you determine this using the
adjacency matrix?
4. How many matrix-multiplication operations do you need to compute the connectivity between every
two nodes for a given graph G (V, E)? What if the number of edges is very small?

5. Is there a specific property for adjacency matrices of undirected graphs that is not necessary true for
adjacency matrices of directed graphs?

b
c

d
e

Figure 1: Graph for exercise 1.

Answer. 1. See matrix A. The indices of A correspond to the nodes in alphabetical order.
 
0 1 1 0 1
 1 0 0 0 0 
 
A=  1 0 0 1 1   (1)
 0 0 1 0 0 
1 0 1 0 0

3
 2. We can see that there is no direct edge between a and d because Aad = 0, we thus determine whether
there is a path of length 2 between a and d by calculating the square of A:
 
3 0 1 1 1
 0 1 1 0 1 
A2 = 
 
 1 1 3 0 1  (2)

 1 0 0 1 1 
1 1 1 1 2

As we can see A2ad = 1, there exists thus a path of length 2.

3. Since A0 = I5 doesn’t contain a path from a to d and neither does A, but A2 does, we know that the
shortest path uses two edges.
4. If we first perform a matrix-addition, B = A + I. The resulting matrix B contains the edges as well
as loops. If we now calculate B 2 we obtain all paths of length 0, 1 and 2. A naive algorithm can now
perform n multiplications, thus calculate B n−1 with n the number of nodes. Since there are n nodes,
it can take at most n − 1 steps to go from one vertex to another one. A smarter approach hover is

2
to reuse the result we obtain by B 2 . Since B 4 = B 2 , we can speed up the process. The algorithm
does not calculate B n−1 using n − 2 matrix multiplications, but log2 (n − 1). If the number of edges is
very small, we can make it even more efficient. The longest path is bounded by the number of edges
e. If e is very small, we can calculate B min(n−1,e) . We can use our efficient algorithm for this.
5. symmetry of the adjacency matrix

Exercise 3 (Euler’s theorem about Eulerian paths/graphs).
1. Generalize Euler’s theorem with respect to directed graphs. Don’t forget to take loops into account.
2. Prove that in a graph containing exactly two vertices u and v of odd degree, there exists a path from
u to v.
Answer. 1. The new theorem states:
Theorem 1 (Euler’s modified theorem). A directed graph G (V, E) contains a Eulerian path if and
only if the graph is connected1 and for all vertices v ∈ V the number of incoming edges equals the
number of outgoing edges.

Proof. Evidently the graph must be a connected graph: a Eulerian cycle contains each vertex so that
means that we need to be able to traverse from every vertex to every vertex by following the Eulerian
cycle.

We construct a cycle P we do this by starting from a vertex v since the graph is connected, we know
that there must be at least one outgoing edge. We now take one of the edges to a vertex w. Since w has
at least one incoming edge, it has at least one outgoing edge as well, so we can repeat this operation
until we reach v again. Now there are two possibilities:
(a) We have visited every edge. In that case we’ve constructed a Eulerian cycle so we’re done; or
(b) We haven’t visited an edge. Optionally this means we haven’t even visited every vertex. Since
the graph is connected however, it means that there is at least one vertex we’ve visited where
there exists an edge we haven’t visited in our original path. Now since our original path always
took one incoming and one outgoing edge per cycle, we know that this vertex must also contain
1 Note that the definition of connected differs a bit in the context of a directed graph.

4
 an unused incoming edge. If we take the outgoing vertex, we’re sure we can find a way to return
to the vertex since the graph is connected. We can thus construct a cycle from that vertex that
we can add to the path.
By keeping to add cycles to the path, we will eventually end up with a Eulerian cycle because we can’t
add a cycle to the path anymore of no edges haven’t been visited anymore.

2. Proof. For each component of the graph, it is true that the number of vertices with odd degree is even,
so the u en v are in the same component, which means that there is a path between them.

Exercise 4 (Maximal flow). Find a maximal flow using the algorithm from the course notes for the flow graph
below. Also indicate the minimal cut corresponding to the maximal flow you found. Use the alphabetical
order of the vertices. (you can give the cut by the partition P, P as in the course notes - drawing is might
be messy) The capacity of each edge equals 1.

e
i

a h z
c
g
b
f

Do other minimal cuts exist?

Answer.
e
i
1
1
d
1
a 1 h z
c
1 1
1
g
1 1
b
f

At the end of 3 rounds of labeling and improving, the flows (different from zero) are as in the picture
above.
One more round of labeling results in:

5
 e (a,1)
i (e,1)
(i,1) 1
1
d
1
a 1 h z
(_,_) c
1 (d,1) 1
1
g
1 1
b
(g,1)
f

A common mistake is to forget to label d from node i. The labeled nodes are {a, b, e, i, d, g} and that
is the P part of the (minimal) cut. Since z had no label, the maximal flow has been reached: 3. The cut
crosses the arcs (i, z), (a.c), (g, z): they are good edges, and they carry a flow equal to 1.

Below is another maximal flow: it has another minimal cut of course.

e
1
i

1 1
d
1 1
a 1 h z
c 1
1 1
g
b
f


Exercise 5 (Graph properties).
1. Do simple graph exist with n > 1 vertices such that every vertex has a distinct degree?
2. Show that for every n, Kn,n has a subgraph isomorphic to Ck - a cycle of length k - for every k ∈
{4, 6, . . . , 2 · n}.
3. Show that for every n ≥ 2, Kn,n is a Hamiltonian graph.
Answer. 1. No. In a simple graph with n vertices, the maximal degree of a vertex is (n − 1) so if all
degrees are distinct, the degree sequence of that graph equals [n − 1, n − 2, ..., 0]. This means that the
vertex with highest degree is connected to every other vertex, contradicting the fact that there is a
vertex with degree equal to 0.
For general graphs, one transform a given graph to one with all distinct degrees, by adding enough
loops to every vertex.
2. Given a graph Kn,n we will label the vertices of the first set with ai ∈ A and the vertices of the second
set with bj ∈ B. By definition there only exist edges between every ai ∈ A and every bj ∈ B. Now for
a given k in {4, 6, . . . , 2 · n}, we can define a cycle graph Ck as a1 → b1 → a2 → b2 → . . . → ak/2 →
bk/2 → a1 . It is clear that all the edges in the path are edges from Kn,n since we alternate between ai
and bj . Furthermore we never use an edge twice since each time an edge starts from a vertex in A, the
index has incremented.

6
 3. If we take the previously described path and set k = 2 · n a1 → b1 → a2 → b2 → . . . → an → bn → a1 ,
we’ve visited every vertex exactly once and didn’t visit an edge more than once. This works for every
n ≥ 2. For n = 1, there exists no cycle since there is only one edge between a1 and b1 and we would
need to traverse it twice in order to generate a cycle.


Exercise 6 (Eulerian and Hamiltonian paths).

For the definitions of Eulerian and Hamiltonian path, see 2.2.12 and 2.2.13 in the course notes.

1. Can a graph contain both a Eulerian and Hamiltonian path? If so, draw such graph.
2. Can a graph contain a path that is both Eulerian and Hamiltonian? If so, what can you say about the
shape of such graphs? Prove this.
3. An n-cube can be defined inductively as follows:

Definition 1 (n-cube). A 1-cube is a graph that contains exactly one vertex and no edges.
An n-cube consists of two n − 1 cubes such that the corresponding vertices of the two cubes
are connected.
For which values for n does an n-cube contain a Hamiltonian path? Prove your answer. Show paths
for the 3- and 4-cube.

Answer.

c b

d a

e f

Figure 2: A graph that contains both a Hamiltonian and Eulerian path.

c b

d a

e f

Figure 3: A graph that contains a path that is both Hamiltonian and Eulerian.

1. Yes. See Figure 2. The Hamiltonian path is a → b → c → d → e → f . The Eulerian is a → b → e →

b → c → d → e → f.

2. Yes. See Figure 3. There are only two possible graphs-families that contain such path, a cycle graph
Cn and a path graph Pn 2 .
2A path graph is graph that consists out of n vertices such that vi is connected to vi−1 and vi+1 , there is no wrap-around.

7
 Proof. A path that is both Eulerian and Hamiltonian visits all vertices and edges exactly once. Given
the path v1 → v2 , if v1 = v2 , then we speak of a cycle. This means the graph contains an loop for
v1 . If v1 6= v2 , then the only possible graph is a graph with two vertices v1 and v2 with one edge in
between. Now we add a vertex in between the path. If the path is v1 → v3 → v2 , since every vertex
is visited exactly once, we know for sure that v1 6= v3 6= v2 . Again in the case v1 = v2 , we speak of a
cycle. Since the we visit every vertex exactly once, the graph consists in that case out of 2 vertices v1
and v3 and there are two edges: one from v1 to v3 and vice versa. If v1 6= v2 we can only construct a
path graph. By induction where we each time add a vertex in between, we can proof that we can only
generate graphs that belong to the Cn or Pn graph family.

3. From n ≥ 2 one can generate such Hamiltonian path.

Proof. We proof this by induction.

Base case Given a 2-cube with two vertices v1 and v2 a trivial Hamiltonian path is v1 → v2 . Since
a 2-cube contains two vertices with exactly one edge in between, evidently this is a Hamiltonian path.

Induction Given two n-cubes, the n + 1-cube that consists out of the two cubes contains a Hamilto-
nian path as well. Since the n-cubes have the same shape, evidently they have the same Hamiltonian
path(s). We will denote this path for the first n-cube as v1 → v2 → . . . → v2n−1 . The equivalent path
for the second cube is denoted by v10 → v20 → . . . → v20 n−1 . Since the edges are not directed, we can
reverse the path, and the resulting path is still a Hamiltonian path: v20 n−1 → v20 n−1 −1 → . . . → v10 .
Since vi has an edge to vi0 we can connect v2n−1 with v20 n−1 . The resulting path is v1 → v2 → . . . →
v2n−1 → v20 n−1 → v20 n−1 −1 → . . . → v10 . Since the first two paths visited every vertex once, and we
simply concatenated the paths, the resulting path visits every vertex in both cubes. So the resulting
path is Hamiltonian as well.

Regular Languages
Exercise 7. For a given string w = w1 w2 . . . wn (wi ∈ Σ) we
 denote the reversed string as
wR = wn . . . w2 w1 . For a given language L we write LR = wR | w ∈ L . Given L is regular, is LR regular
as well?
Answer. Yes. we can prove this using two different strategies: (1) providing a construction that for every
regular expression e constructs a regular expression eR such that the language described by eR is the reverse
of the the original language; (2) provide a construction that generates for a given DFA D an NFA DR that
decides the reverse language.

1. Regular expression that describes the reverse language: we can do this inductively on the structure of
a regular expression:

R =  (3)
φR = φ (4)
R
∀a ∈ Σ : a = a (5)
R
E2R E1R


(E1 E2 ) = (6)
R
E1R |E2
R


(E1 |E2 ) = (7)
R
?
(E1? ) = E1R (8)

8
 2. Automaton that decides the reverse language:
Construction 1. Given a DFA D = hQ, Σ, δ, qs , F i. We consider an additional state q 0 ∈
/ Q. We
consider a new transition function δ 0 such that:

∀qi ∈ Q, σ ∈ Σ : δ 0 (qi , σ) = {qj ∈ Q | qi = δ (qj , σ)} (9)

0 0
δ (q , ) = F (10)

De constructed NFA is defined as: DR = hQ ∪ {q 0 } , Σ, δ 0 , q 0 , {qs }i


Exercise 8. Give for every language below over the alphabet Σ = {0, 1} a regular expression that determines
the language. Construct an NFA that decides the language.
1. {w | every odd position of w is a 1}
2. {w | w contains at least two 0s and at most one 1}
3. The complement language of {11, 111}

4. {w | the numbers of occurrences of 01 and 10 in w are the same}

Answer.
?
1. (1 (0|1)) (1|)
2. 0? (00|001|010|100) 0?
? ? ? ?
3. () | (1) | (0 (0|1) ) | (10 (0|1) ) | (110 (0|1) ) | (111 (0|1) (0|1) )
? ?
4. 0? | 1? | 0 (0|1) 0 | 1 (0|1) 1
For NFAs: see Figure 4. 

Exercise 9. Prove that for every n ≥ 1 there exists an NFA that decides the following languages.

1. Ln = ak | k is a multiple of n over the alphabet Σ = {a}.
2. Ln = {x | x is the binary representation of a natural number that is a multiple of n}
Answer.

1. One can construct a DFA that decides a language Ln for a given n as follows:
Construction 2. One considers n states: q0 , q1 , . . . , qn−1 . q0 is the initial state and the only accepting
state (F = {q0 }). The transition function δ is defined as follows:

∀qi ∈ Q, j ∈ {0, 1} : δ (qi , a) = q(i+1) mod n (11)

The NFA is defined as h{q0 , q1 , . . . , qn } , {a} , δ, q0 , {q0 }i.

2. We assume the binary representation uses little endian: the least significant bits occur at the end of
the string. The endianness is of no vital importance: the first exercise already shows that if a language
is regular, it’s reverse is regular as well, we can thus construct the reverse language for the big endian
variant. One can construct a DFA that decides the language as follows:

9
 0 q1
0 q3
0
1 0
0, 1 q0 q4
1 q6
start 0 0
0, 1
q0 q1 q2 q2 0
start 0
1
1 q5
0
(a) (b)

0, 1

q1
0, 1 0 0

0 0, 1
0 q4 start q0 q3
0
0, 1
0, 1
1 1
q0
1 q1
1 q2
1 q3
start q2

(c) (d)

Figure 4: NFAs for the given languages.

.

Construction 3. One considers n states: q0 , q1 , . . . , qn−1 . q0 is the initial state and the only accepting
state. The transition function δ is defined as follows:

∀qi ∈ Q, j ∈ {0, 1} : δ2 (qi , j) = qk where k = 2 · i + j mod n (12)

The NFA is defined as h{q0 , q1 , . . . , qn−1 } , {0, 1} , δ2 , q0 , {q0 }i.


Exercise 10. An all-paths-NFA hQ, Σ, δ, q0 , F i differs from an NFA because it accepts a string w only if
• for every possible subdivision w = y1 y2 . . . ym , yi ∈ Σε and every state sequence r0 , r1 , . . . , rm such
that r0 = q0 and ri+1 ∈ δ(ri , yi+1 ), it holds that rm ∈ F ;
• there is at least one subdivision w = y1 y2 . . . ym , yi ∈ Σε such that there is a state sequence r0 , . . . , rm
with r0 = q0 and ri+1 ∈ δ(ri , yi+1 ).
Show that L is regular, if and only if there exists an all-paths-NFA that decides L.
Answer. We prove this in both directions:
1. Given L is a regular language, the language is recognized by an all-path NFA.
Proof. Given L is a regular language, then there exists a DFA D = hQ, Σ, δ, qs , F i that
decides L. A DFA is an NFA with a determinstic transition function. This implies that for
a given string s, there is exactly once path of states. We can transform D into an equivalent
NFA N = hQ, Σ, δ 0 , qs , F i:

∀q ∈ Q, σ ∈ Σ : δ 0 (q, σ) = {δ (q, σ)} (13)

10
 Given N is always in one state at the time, and equivalent to D, for every string s there
exists one path of states as well. When the path of states for s is leading to an accepting
state, D, The all-path NFA N will accept as well since there is one such path of states and
it is accepting: all paths thus accepted and vice versa.
2. Given L is recognized by an all-paths-NFA, L is regular.

Proof. We prove this by using a construction that converts an all-path-NFA into a DFA
that recognizes the same language.
Construction 4. Given an all-paths-NFA hQ, Σ, δ, q0 , F i we construct a DFA hQ, Σ, δ 0 , q00 , Fi
that decides the same language:

Q = P (Q) (14)
F = P (F ) \ {∅} (15)
q00 = eb (q0 ) (16)
0 0 0 0
∀Q ∈ Q, σ ∈ Σ : δ (Q , σ) = δd (Q , σ) (17)

With eb and δd defined as in the course text.

We approximately perform the same transition as from a normal NFA to a DFA. In every
state of the DFA, the “heads” of the paths are stored. We modify F such that a state in the
DFA is accepting if and only if all stored heads are accepting, and there is at least one such
head.


11