Test: Graphs & Hashing- 2 - Computer Science Engineering (CSE) MCQ

If the (1, 3) entry in M³ is 2, it means there are 2 paths of length 3, connecting nodes 1 and 3. If you see the graph in option (a), there are 2 paths connecting 1 and 3,(1 → 2 → 3 → 3 and 1 → 3 → 3 → 3).

In Breadth first traversal the nodes are searched level by level. Starting with vertex A, the only next choice is B. Then C, then 1 and lastly 2. Comparing with ABCDE.

Strong component of a given graph is the maximal set of vertices such that for any two vertices i, j in the set, there is a path connecting i to j.
Obviously vertex ‘d' can’t be in the maximal set (as no vertex can be reached starting from vertex d).

Using the Kruskal’s algorithm:


∴ Minimum cost is 20.

Number of binary tree with 3 nodes with post order A, B, C

So there are 5 binary tree possible.

As we observe that the graph is disconnected
n > 3 (number of vertices)
e = 2 (number of edges)
For example : n = 4
for this only 2 colors are sufficient.

Breadth first search can be used to find connected components of a graph.

In a regular graph, all the vertices will be of the same degree. Total degrees of all the vertices is nd. Each edge will be increasing the total degree by 2. So, totally nd/2 edges.

Number of elements in set = n
Number of possible binary relations = n²
Number of possible binary relations of the set = 2ⁿ².

Matrix of 10 rows and 10 columns can have m axim um 1 0 x 1 0 = 100 entries. S ince only 15 non-zero entries are present, so number of real link will be 15 only.
Assuming undirected graph.