Consider the undirected graph shown in Figure .
List the elements of and .
Then, for each vertex do the following:
Compute the in-degree of v.
Compute the out-degree of v.
List the elements of .
List the elements of .
Figure: Sample Graphs
Consider the directed graph shown in Figure .
Show how the graph is represented using an adjacency matrix.
Show how the graph is represented using adjacency lists.
Repeat Exercises and for the
directed graph shown in Figure .
Consider a depth-first traversal
of the undirected graph shown in Figure
starting from vertex a.
List the order in which the nodes are visited
in a preorder traversal.
List the order in which the nodes are visited
in a postorder traversal.
Repeat this exercise for a depth-first traversal
starting from vertex d.
List the order in which the nodes of the undirected graph
shown in Figure are visited
by a breadth-first traversal that starts from vertex a.
Repeat this exercise for a breadth-first traversal
starting from vertex d.
Repeat Exercises and for the
directed graph shown in Figure .
List the order in which the nodes of the directed graph
shown in Figure are visited
by a topological order traversal that starts from vertex a.
Consider an undirected graph .
If we use a adjacency matrix A
to represent the graph,
we end up using twice as much space as we need
because A contains redundant information.
I.e., A is symmetric about the diagonal and
all the diagonal entries are zero.
Show how a one-dimensional array of
length can be used to represent G.
Hint: consider just the part of A above the diagonal.
What is the relationship between the sum of the degrees of
the vertices of a graph and the number of edges in the graph.
A graph with the maximum number of edges
is called a fully connected graph.
Draw fully connected, undirected graphs that contain
2, 3, 4 and 5 vertices.
Prove that an undirected graph with n vertices
contains at most n(n-1)/2 edges.
Every tree is a directed, acyclic graph (DAG),
but there exist DAGs that are not trees.
How can we tell whether a given DAG is a tree?
Devise an algorithm to test whether a given DAG is a tree.
Consider an acyclic, connected, undirected graph G
that has n vertices.
How many edges does G have?
In general, an undirected graph contains one or more
connected components.
A connected component of a graph G is a subgraph of G
that is connected and contains the largest possible
number of vertices.
Each vertex of G is a member of exactly one
connected component of G.
Devise an algorithm to count the number of connected
components in a graph.
Devise an algorithm that labels the vertices of a graph
in such a way that all the vertices in a given connected
component get the same label
and vertices in different connected components
get different labels.
A source in an directed graph is a vertex
with zero in-degree.
Prove that every DAG has at least one source.
What kind of DAG has a unique topological sort?
Under what conditions does a postorder depth-first traversal
of a DAG visit the vertices in reverse topological order.
Consider a pair of vertices, v and w, in a directed graph.
Vertex w is said to be reachable from vertex v
if there exists a path in G from v to w.
Devise an algorithm that takes as input a graph,
,
and a pair of vertices, ,
and determines whether w is reachable from v.
An Eulerian walk
is a path in an undirected graph that starts and ends
at the same vertex and traverses every edge in the graph.
Prove that in order for such a path to exist,
all the nodes must have even degree.
Consider the binary relation defined for
the elements of the set as follows:
How can we determine whether is a total order?
Show how the single-source shortest path problem
can be solved on a DAG using a topological-order traversal.
What is the running time of your algorithm?
Consider the directed graph shown in Figure .
Trace the execution of Dijkstra's algorithm
as it solves the single-source shortest path problem
starting from vertex a.
Give your answer in a form similar to Table .
Figure: Sample Weighted Graphs
Dijkstra's algorithm works as long as there are no negative
edge weights.
Given a graph that contains negative edge weights,
we might be tempted to eliminate the negative weights
by adding a constant weight to all of the edge weights
to make them all positive.
Explain why this does not work.
Dijkstra's algorithm can be modified to deal with negative edge
weights (but not negative cost cycles)
by eliminating the known flag
and by inserting a vertex back into the queue
every time its tentative distance decreases.
Explain why the modified algorithm works correctly.
What is the running time of the modified algorithm?
Consider the directed graph shown in Figure .
Trace the execution of Floyd's algorithm
as it solves the all-pairs shortest path problem.
Prove that if the edge weights on an undirected graph
are distinct,
there is only one minimum-cost spanning tree.
Consider the undirected graph shown in Figure .
Trace the execution of Prim's algorithm
as it finds the minimum-cost spanning tree
starting from vertex a.