Algorithms and Data Structures (INF1, Autumn'05)
Exercise Set 12
Exercise 1:
Let G=(V,E) be a digraph where n is the number of nodes and m is the number
of edges.
- What is the maximal number of edges a digraph with 1 node can have?
- What is the maximal number of edges a digraph with 2 nodes can have?
- What is the maximal number of edges a digraph with 3 nodes can have?
- What is the maximal number of edges a digraph with 5 nodes can have?
- What is the maximal number of edges a digraph with n nodes can have?
Let us now consider the space complexity of adjacency matrix and adjacency
list implementation of digraphs. Fill in the following table
when certain relationships between the number of nodes and edges are know
(use big-O notation).
| Adjacency Matrix | Adjacency List |
|---|
| nothing is known about n and m | | |
| m = O(n) | | |
| m = Ω(n2) | | |
| n = Ω(m2) | | |
| m = O(n*log n) | | |
Which representation is more space efficient? Which cases above
demonstrate this? Can you characterize them in words? In which
cases adjacency matrix and adjacency list requite approximately the
same space?
Exercise 2:
-
Provide one sequence of topologically ordered nodes of
the DAG G=(V,E) where V={A,B,C,D,E} and E={ (A,B), (C,B),
(C,D), (B,E), (E,D) }. (Hint: draw a picture).
-
Draw a DAG with 5 nodes (names of nodes A, B, C, D, E)
such that there is exactly one topologically ordered
sequence of nodes. Is it true that there have to be exactly
4 edges in the DAG? If yes, prove it. If no, draw a
DAG with a different number of edges (still having only 5 nodes)
such that it has exactly one topologically ordered sequence of
nodes.
-
Draw a DAG with 5 nodes (names of nodes A, B, C, D, E)
such that there are exactly 4 different topologically ordered
sequences of nodes.
-
Draw a DAG with 5 nodes (names of nodes A, B, C, D, E)
such that it has the maximum possible number of
topologically ordered sequences of nodes. What is this number?
-
What is the maximum number of topological orders
for a DAG with n nodes?
Exercise 3:
Using the operations of the ADT DIGRAPH construct g:DIGRAPH
representing the following directed graph
G=(V,E) where
V= {A, B, C, D} and E= {(A,B), (B,B), (C,D)} such that the names
of the edges are 1, 3 and 7 (in this order).