Acho que entendi uma situação específica, conforme descrito abaixo, mas não tenho o conhecimento teórico para realizar uma prova e não consegui encontrar nenhuma fonte que a mencione. Se meu entendimento estiver correto, posso economizar metade do espaço na minha matriz de adjacência; se não for, é provável que tenha bugs muito estranhos. Por isso, gostaria de ter certeza e agradeceria se alguém com um histórico mais sólido pudesse revisar meu raciocínio.

Digo que eu represento um DAG de n vértices em uma matriz de adjacência n * n, de modo que a entradai,j é1 se houver uma aresta do vérticei ao vérticej, 0 de outra forma. Como o gráfico é direcionado e acíclico, segue-se que, sei,j = 1, entãoj,i = 0. Se agora eu classificar os nós na matriz de modo que o nível topológico do nó em in é igual ou superior ao nó em i n-1, parece-me que metade da matriz de adjacência sempre conterá0s, como é o caso no exemplo a seguir:

      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

Talvez eu esteja certo, mas existe uma maneira formal de verificar isso?