Graphs-and-Tree
Question 1 |
Let G = (V,E) be a directed, weighted graph with weight function w:E → R. For some function f:V → R, for each edge (u,v) ∈ E, define w'(u,v) as w(u,v) + f(u) - f(v).
Which one of the options completes the following sentence so that it is TRUE?
“The shortest paths in G under w are shortest paths under w’ too, _______”.
if and only if f(u) is the distance from s to u in the graph obtained by adding a new vertex s to G and edges of zero weight from s to every vertex of G | |
if and only if ∀u ∈ V, f(u) is positive
| |
if and only if ∀u ∈ V, f(u) is negative | |
for every f: V→R |
Question 1 Explanation:
Question 2 |
Consider the following statements.
S1:The sequence of procedure calls corresponds to a preorder traversal of the activation tree.
S2:The sequence of procedure returns corresponds to a postorder traversal of the activation tree.
Which one of the following options is correct?
S1:The sequence of procedure calls corresponds to a preorder traversal of the activation tree.
S2:The sequence of procedure returns corresponds to a postorder traversal of the activation tree.
Which one of the following options is correct?
S1is false and S2is false
| |
S1is true and S2is true | |
S1is true and S2is false | |
S1is false and S2is true |
Question 2 Explanation:
The given statements are true, they are well known facts.
- The sequence of procedure calls corresponds to a preorder traversal of the activation tree.
- The sequence of returns corresponds to a postorder traversal of the activation tree.
Question 3 |
Consider the following directed graph:
Which of the following is/are correct about the graph?
Which of the following is/are correct about the graph?
For each pair of vertices u and v, there is a directed path from u to v. | |
The graph does not have a strongly connected component. | |
The graph does not have a topological order. | |
A depth-first traversal staring at vertex S classifies three directed edges as back edges. |
Question 3 Explanation:
Option-1: FALSE: There is no path from top right corner vertex to any other vertex
Option-2: FALSE: A directed graph is called strongly connected if there is a path in each direction between each pair of vertices of the graph. As there is no path from the above vertex then this statement is wrong.
Option-3: TRUE: This graph does have directed cycles, thus topological order can not be possible for according to topological definition.
Question 4 |
Consider the following statements:
(a) Depth first search is used to traverse a rooted tree.
(b) Preorder, Postorder and Inorder are used to list the vertices of an ordered rooted tree.
(c) Huffman’s algorithm is used to find an optimal binary tree with given weights.
(d) Topological sorting provides a labelling such that the parents have larger labels than their children.
Which of the above statements are true?
(a) Depth first search is used to traverse a rooted tree.
(b) Preorder, Postorder and Inorder are used to list the vertices of an ordered rooted tree.
(c) Huffman’s algorithm is used to find an optimal binary tree with given weights.
(d) Topological sorting provides a labelling such that the parents have larger labels than their children.
Which of the above statements are true?
(a) and (b) | |
(c) and (d) | |
(a), (b) and (c) | |
(a), (b), (c) and (d) |
Question 4 Explanation:
→ Preorder, Postorder and Inorder are traversing techniques where all the nodes of the tree will be traversed from the root node.
→ Depth-first search (DFS) is an algorithm for traversing or searching tree or graph data structures. The algorithm starts at the root node (selecting some arbitrary node as the root node in the case of a graph) and explores as far as possible along each branch before backtracking.
→ The optimal binary tree, which has minimum weighted path length when the characters of the alphabet are stored at its n terminal nodes.An optimal binary tree generates what is called a Huffman code
→ A topological sort or topological ordering 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. For instance, the vertices of the graph may represent tasks to be performed, and the edges may represent constraints that one task must be performed before another; in this application, a topological ordering is just a valid sequence for the tasks.
A topological ordering is possible if and only if the graph has no directed cycles, that is, if it is a directed acyclic graph (DAG). Any DAG has at least one topological ordering, and algorithms are known for constructing a topological ordering of any DAG in linear time.
→ Depth-first search (DFS) is an algorithm for traversing or searching tree or graph data structures. The algorithm starts at the root node (selecting some arbitrary node as the root node in the case of a graph) and explores as far as possible along each branch before backtracking.
→ The optimal binary tree, which has minimum weighted path length when the characters of the alphabet are stored at its n terminal nodes.An optimal binary tree generates what is called a Huffman code
→ A topological sort or topological ordering 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. For instance, the vertices of the graph may represent tasks to be performed, and the edges may represent constraints that one task must be performed before another; in this application, a topological ordering is just a valid sequence for the tasks.
A topological ordering is possible if and only if the graph has no directed cycles, that is, if it is a directed acyclic graph (DAG). Any DAG has at least one topological ordering, and algorithms are known for constructing a topological ordering of any DAG in linear time.
Question 5 |
Level order Traversal of a rooted Tree can be done by starting from root and performing:
Breadth First Search | |
Depth First Search | |
Root Search | |
Deep Search |
Question 5 Explanation:
Breadth first search:
It is an algorithm for traversing (or) searching tree (or) graph data structures. It starts at the root and explores all of the neighbour nodes at the present depth prior to moving on to the nodes at the next depth level.
It is an algorithm for traversing (or) searching tree (or) graph data structures. It starts at the root and explores all of the neighbour nodes at the present depth prior to moving on to the nodes at the next depth level.
Question 6 |
Weighted graph :
Is a bi-directional graph | |
Is directed graph | |
Is graph in which number associated with arc | |
Eliminates table method |
Question 6 Explanation:
→ Weighted graph is a graph in which number associated with arc. A weighted graph is a graph in which each branch is given a numerical weight.
→ A weighted graph is therefore a special type of labeled graph in which the labels are numbers.
→ A weighted graph is therefore a special type of labeled graph in which the labels are numbers.
Question 7 |
Consider the graph, which of the following is a valid topological sorting ?
ABCD | |
BACD | |
BADC | |
ABDC |
Question 7 Explanation:
Finding valid topological sorting we have two methods.
1. Using DFS method
2. Using indegree elimination method
The simplest method is indegree elimination method.
Indegrees:
A →0
B →1
D →2
C → 1 (Final)
We can assume that indegree value of A is ‘0’. So, it is starting point.
Step-1: Remove ‘A’ from graph, then indegrees are
B →0
D →1
C →1
Sequence:
Step-2: Remove ‘B’ from graph, then indegrees are
D →0
C →1
Sequence:
Step-3: Remove ‘C’ from graph then indegrees are
C →0
Sequence:
1. Using DFS method
2. Using indegree elimination method
The simplest method is indegree elimination method.
Indegrees:
A →0
B →1
D →2
C → 1 (Final)
We can assume that indegree value of A is ‘0’. So, it is starting point.
Step-1: Remove ‘A’ from graph, then indegrees are
B →0
D →1
C →1
Sequence:
Step-2: Remove ‘B’ from graph, then indegrees are
D →0
C →1
Sequence:
Step-3: Remove ‘C’ from graph then indegrees are
C →0
Sequence:
There are 7 questions to complete.