¿De cuántas formas se puede añadir una arista a un grafo acíclico dirigido?

Question

Supongamos que tengo un grafo acíclico dirigido (DAG) $G=(V,E)$ ¿de cuántas maneras puedo añadir una sola arista y seguir teniendo un DAG?

Vi un pregunta similar aquí cuya solución utiliza un orden topológico en los vértices. Pensé en contar (de alguna manera) el número de aristas que potencialmente se podrían añadir preservando el orden. Sin embargo, como el orden puede no ser único, habría que enumerar todos los posibles ordenamientos, asegurándose de no contar dos veces las aristas colgantes. Pero, ¿quizás haya una forma mejor, idealmente una expresión cerrada?

Answer 1

Sea $n$ et $m$ denotan el número de vértices y aristas de $G$ respectivamente. Asumiré que te gustaría saber cuántos dirigido aristas que podemos añadir, de modo que si para $u,v \in V$ podemos añadir $uv$ et $vu$ lo contamos como dos formas de añadir una nueva arista. En caso contrario, la respuesta es ${n \choose 2} - m$ ya que para cualquier par de vértices no vecinos $u,v$ puede añadir al menos uno de $uv$ et $vu$ al grafo (por ejemplo, si en una ordenación topológica $u$ viene antes que $v$ puede añadir $uv$ ).

Ahora, para cualquier par de vértices $u,v$ , si no puedes añadir el borde $uv$ al gráfico, eso se debe a que $uv$ ya es un borde, o porque al añadir $uv$ crearía un ciclo dirigido, lo que ocurre precisamente si $u$ es accesible desde $v$ . Desde $G$ es un DAG, estas dos posibilidades se excluyen mutuamente. Esto significa que si $m'$ denota el número de pares ordenados $(u,v)$ tal que $u$ es accesible desde $v$ entonces el número de aristas dirigidas que se pueden añadir es $n(n-1) - m - m'$ . Tenga en cuenta que $m'$ es el número de aristas del cierre transitivo de $G$ .