Si topológicamente clasifico un DAG, ¿puedo soltar la mitad de la matriz de adyacencia?

Question

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, si no es así, es probable que tenga errores bastante extraños. Así que me gustaría estar seguro, y agradecería que alguien con un fondo más sólido pudiera revisar mi razonamiento.

Di represento un DAG de n vértices en un * n matriz de adyacencia n de tal manera que la entrada i,j es 1 si hay un borde de vértice i al vértice j, 0 lo contrario. Debido a que el gráfico es dirigido y acíclico, se deduce que, si es i,j = 1, entonces j,i = 0. Si ahora clasifico los nodos en la matriz de modo que el nivel topológico del nodo en i _n sea igual o mayor que el nodo en i _n-1, entonces me parece que la mitad de la matriz de adyacencia siempre sólo contienen 0 s, como es el caso en el ejemplo siguiente:

 
     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 

Tal vez estoy bien, pero hay una manera formal para comprobar esto?

Answer 1

Sea adj [i] [j] la entrada de adyacencia del nodo i al nodo j y la ha ordenado de tal manera que para todos los nodos i < j, el nodo i está más arriba en la jerarquía topológica que el nodo j.

Supongamos por un momento que su suposición es incorrecta: que tenemos un contraejemplo para el cual adj [i] [j] == 1 para i> j (es decir, uno en la mitad superior derecha de su representación matricial). Esto implica que debe haber un ciclo que contenga i y j, ya que nuestra clasificación garantiza que el nodo j está más arriba que el nodo i, pero adj [i] [j] == 1 implica que podemos "subir" en la jerarquía. Esto es una contradicción, ya que sabemos que tenemos un DAG. Por lo tanto, hemos demostrado que su suposición es correcta.

Answer 2

Esto solo es correcto si su matriz de adyacencia está construida con el gráfico etiquetas en orden ordenado. Para un contraejemplo construya la matriz de adyacencia para B-> C-> A.

Si mantiene un hash del nodo verdadero en su posición de clasificación topológica y construye la matriz de adyacencia, puede ahorrar espacio en una matriz grande, ya que está guardando O (n2) espacio en la matriz con un O (n) tamaño hashtable.