Let G = (V, E) be a directed graph with n vertices. A path from v_i to v_j in G is sequence of vertices (v_i, v_i+1, ……., v_j) such that (v_k, v_k+1) ∈ E for all k in i through j – 1. A simple path is a path in which no vertex appears more than once. Let A be an n x n array initialized as follow
$$$A[j,k] = \left\{ {\matrix{ {1\,if\,(j,\,k)} \cr {1\,otherwise} \cr } } \right.$$$ Consider the following algorithm.

for i = 1 to n
   for j = 1 to n
      for k = 1 to n
         A [j , k] = max (A[j, k] (A[j, i] + A [i, k]); 

Which of the following statements is necessarily true for all j and k after terminal of the above algorithm ?

What is the weight of a minimum spanning tree of the following graph?

Let G be an undirected connected graph with distinct edge weight. Let emax be the edge with maximum weight and emin the edge with minimum weight. Which of the following statements is false?

Complexity of Kruskal’s algorithm for finding the minimum spanning tree of an undirected graph containing n vertices and m edges if the edges are sorted is _______.