I have a complete weighted directed graph G=(V,A,W) and I want to reduce the density of the graph by deleting arcs as follows: given i,j,k \in V if w(i,j) w(j,k) <= w(i,k), then we delete arc (i,k). The code is given below, where ad is initially the adjacency matrix of G

        for (int i = 0; i < |V|;   i)
        {
            for (int j = 0; j < |V|;   j)
            {
                if(j!=i)
                  {
                     for (int k = 0; k < |V|;   k)
                         {
                               if(k!=i && k!=j){
                                     if(ad[i][j]==1 && ad[j][k]==1 && w(i,j) w(j,k) <= w(i,k))
                                           ad[i][k]=0;
                                }
                         } 
                  }
            }
       }

My question is: can this procedure make the resulting graph not connected?

CodePudding user response：

Assuming no machine arithmetic shenanigans and that w(i, j) is positive whenever i ≠ j, no, you can't disconnect the graph.

For every (i, j) pair, consider a longest (by arc count) walk from i to j whose weight is at most w(i, j). This walk is well defined because i → j has weight at most w(i, j), and the assumptions of positive weights and a finite graph imply that the set of possible walks is finite, hence has a maximum. The algorithm cannot remove any of the arcs on this walk, or else there would be a longer walk. Hence the residual graph is strongly connected.