Я думаю, что я понял конкретную ситуацию, как описано ниже, но мне не хватает теоретических знаний, чтобы провести доказательство, и я не смог найти источник, который упоминает это. Если мое понимание правильное, я могу сэкономить половину пространства в моей матрице смежности, если это не так, у меня могут быть довольно странные ошибки. Так что я хотел бы быть уверен, и я был бы признателен, если бы кто-то с более солидным опытом мог пересмотреть мои аргументы

Скажем, я представляю DAG из n вершин в n * n матрице смежности, так что записьi,j является1 если есть ребро от вершиныi к вершинеj, 0 в противном случае. Поскольку граф является направленным и ациклическим, из этого следует, что еслиi,j = 1, тогдаj,i = 0, Если я теперь сортирую узлы в матрице так, чтобы топологический уровень узла в In равно или больше, чем узел в Iн-1тогда мне кажется, что половина матрицы смежности всегда будет содержать только0s, как это имеет место в следующем примере:

      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

Может быть, я просто прав, но есть ли формальный способ проверить это?