1. The time
complexities of some standard graph algorithms are given. Match each algorithm
with its time complexity? (n and m are no. of nodes and edges respectively)
[Paper III December 2012]
a. Bellman Ford algorithm 1. O (m log n)
b. Kruskals algorithm 2. O (n3)
c. Floyd Warshall algorithm 3. O(mn)
d. Topological sorting 4. O(n + m)
Codes:
a b c d
(A) 3 1 2 4
(B) 2 4 3 1
(C) 3 4 1 2
(D) 2 1 3 4
2. Two graphs A and
B are shown below: Which one of the following statement is true?
[Paper III December
2012]
(A) Both A and B are planar.
(B) Neither A nor B is planar.
(C) A is planar and B is not.
(D) B is planar and A is not.
3. Maximum number of edges in a n Node undirected
graph without self loop is:
[Paper II
December 2011]
(A) n2 (B)
n(n – 1)
(C) n(n + 1) (D)
n(n – 1)/2
4. Consider a weighted
undirected graph with positive edge weights and let (u, v) be an edge in the
graph. It is known that the shortest path from source vertex s to u has weight
53 and shortest path from s to v has weight 65. Which statement is always true? [Paper III June 2012]
(A) Weight (u, v)
12 (B) Weight (u, v) = 12
(C) Weight (u, v) ≥ 12 (D) Weight (u, v) > 12
5. G1 and G2 are two graphs
as shown: [Paper
III June 2012]
(A) Both G1 and G2
are planar graphs.
(B) Both G1 and G2 are not planar graphs.
(C) G1 is planar and G2 is not planar graph.
(D) G1 is not planar and G2 is planar graph.
6.
The number of colours required to properly colour the vertices of
every planer graph is [Paper II
June 2012]
(A) 2 (B) 3
(C) 4 (D) 5
SOLUTIONS
1. A
- The Bellman–Ford algorithm is an algorithm that computes shortest paths from a single source vertex to all of the other vertices in a weighted digraph. Bellman–Ford runs in O(|V|·|E|) time, where |V| and |E| are the number of vertices and edges respectively.
- Kruskal's algorithm is a greedy algorithm in graph theory that finds a minimum spanning tree for a connected weighted graph. This means it finds a subset of the edges that forms a tree that includes every vertex, where the total weight of all the edges in the tree is minimized. Where E is the number of edges in the graph and V is the number of vertices, Kruskal's algorithm can be shown to run in O(E log E) time, or equivalently, O(E log V) time.
- Floyd–Warshall algorithm (also known as Floyd's algorithm, Roy–Warshall algorithm, Roy–Floyd algorithm, or the WFI algorithm) is a graph analysis algorithm for finding shortest paths in a weighted graph with positive or negative edge weights (but with no negative cycles, see below) and also for finding transitive closure of a relation R. the complexity of the algorithm is O(n3).
- A topological sort of a directed graph is a linear ordering of its vertices such that for every directed edge uv from vertex u to vertex v, u comes before v in the ordering. The usual algorithms for topological sorting have running time linear in the number of nodes plus the number of edges O(|V| + |E|).
2. A
A planar graph is a graph that can be embedded in the plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints. In other words, it can be drawn in such a way that no edges cross each other. The given graphs can be redrawn as shown below:
3. D
If you have n nodes, and each node has an edge with n-1 other nodes. However, n(n-1) is double-counting because if two nodes are each connected with the other then that needs to be counted as a single edge. So maximum number of edges is n(n-1)/2.
4. C
The difference in weights to u and v from source is 12. The shortest path to v may or may not include the edge (u, v). Suppose it is included, then the weight(u,v) = 12. And if it is not included, that means there is a path of less weight from u to v, i.e weight(u,v) > 12
5. B
6. C
The Four Color Theorem asserts that every planar graph - and therefore every "map" on the plane or sphere - no matter how large or complex, is 4-colorable
The Four Color Theorem asserts that every planar graph - and therefore every "map" on the plane or sphere - no matter how large or complex, is 4-colorable
No comments:
Post a Comment