-
What is a minimal spanning tree for the following graph, given in
edge-based form (each edge is a list of three elements, the two nodes
and the cost of the edge):
(A B 4) (A C 10) (B C 3) (B D 4) (B E 9) (C E 16) (C F 2) (D F 5) (E F 3)
-
What is the shortest elementary chain from A for the same graph?
-
For the same graph:
a) What is the degree of node B?
b) Is there a Hamiltonian Cycle?
c) Is there a Eulerian Tour?
- The distance from node x to node y in a graph is the cheapest path
between those nodes. The diameter of a connected graph is the longest
such distance between any two nodes in the graph. What is the diameter
of the graph in (1)?
- Disregarding the costs on edges, is the graph in (1) isomorphic to
the following graph presented in vertex-based form?
A: B C
B: A C D E
C: A B E F
D: B F
E: B C F
F: C E
- [1] p. 58, #4: Given a graph G, prove that G is a free tree if we
know that whenever we delete one edge from G, then G is no longer
connected.
- [1] p. 58, #8: Prove that a free tree G with N nodes has N-1 edges.
- Give a topological sort for the following set of relations:
1<3, 1<5, 3<5, 3<6, 3<4, 5<4, 5<2, 6<2, 4<2
- [1] p. 15 #9: Give an algorithm to delete an arbitrary item with
value v from a doubly linked list.
- [1] p. 19, #4: Given n items and m predecessor-successor relations,
prove that the topological sort algorithm takes O(n+m) time and
requires O(n+m) space when a queue is used to keep track of the nodes
whose COUNT field has become zero.