Suppose $G = (V, A)$ is the acyclic weakly connected digraph with$ V $consisting of vertices $v_{i}$ $(i = 1, 2, ..., 8)$ in which the seven arcs are $(v 1 , v 2 ), (v 3 , v 2 ), (v 4 , v 3 ),(v 7 , v 2 ),( v 3 , v 6 ), (v 5 , v 6 )$ and $(v 8 , v 7 )$. Relabel the vertices and arcs such that when the last row of the incidence matrix is deleted, the truncated matrix is upper triangular and non-singular.
Aunt Google does not tell me what is relabel and why we need relabel. Could any one use this example to explain why we need relabel and how to relabel?
To relabel (at least in this case) means to permute the labels. The vertices are currently labeled $1$ through $8$; the arcs strictly speaking haven't been labeled but could be regarded to be implicitly labeled $1$ through $7$ in the order in which they're listed. If you write down the incidence matrix with the rows and columns ordered according to these labels (i.e. with the entry for vertex $v_1$ in the first row and so on and the entry for arc $(v_1,v_2)$ in the first column and so on) and delete the last row, the resulting matrix is not upper triangular (since it has an entry $1$ in the second row and first column, for example). The exercise is asking you to find a different ordering of the vertices and arcs such that if you write down the incidence matrix with the rows and columns ordered accordingly, deleting the last row leads to a matrix that's upper-triangular and non-singular.