Creo que he entendido una situación particular como se describe a continuación, pero me falta el conocimiento teórico para realizar una prueba y no pude encontrar ninguna fuente que lo mencione. Si mi comprensión es correcta, puedo ahorrar la mitad del espacio en mi matriz de adyacencia, de lo contrario, es probable que tenga errores bastante extraños. Por lo tanto, me gustaría estar seguro, y agradecería si alguien con una formación más sólida pudiera revisar mi razonamiento.

Digo que represento un DAG de n vértices en una matriz de adyacencia n * n tal que la entradai,j es1 si hay un borde desde el vérticei al vérticej, 0 de lo contrario. Debido a que el gráfico es dirigido y acíclico, se sigue que sii,j = 1, luegoj,i = 0. Si ahora clasifico los nodos en la matriz de modo que el nivel topológico del nodo en in es igual o mayor que el nodo en i n-1, entonces me parece que la mitad de la matriz de adyacencia siempre contendrá0s, como es el caso en el siguiente ejemplo:

      V 1           V 2     from V    1 2 3 4 5 6 7 8
      / \           / \ 
     /   \         /   \      to V 1  0 0 0 0 0 0 0 0
    /     \       /     \          2  0 0 0 0 0 0 0 0
 e1/     e2\   e3/     e4\         3  1 0 0 0 0 0 0 0
  /         \   /         \        4  1 1 0 0 0 0 0 0
V 3          V 4          V 5      5  0 1 0 0 0 0 0 0
             /|\          /        6  0 0 0 1 0 0 0 0
            / | \        /         7  0 0 0 1 0 0 0 0
           /  |  \      /          8  0 0 0 1 1 0 0 0
        e5/ e6| e7\  e8/
         /    |    \  /
       V 6   V 7   V 8

Quizás tenga razón, pero ¿hay alguna forma formal de verificar esto?