Dado un conjunto $V$ el número de DAGs con conjunto de vértices $V$ es super exponencial en $|V|$ . ¿Existen límites conocidos para el número de DAGs sobre $V$ ? Me interesan los límites inferiores "ajustados", si existen.
Respuesta
¿Demasiados anuncios?
NMoney
Puntos
4209
Aquí hay un límite, aunque no es un límite estricto. El número de DAGs está limitado por el número de grafos no dirigidos porque todo DAG puede convertirse en un UG eliminando las orientaciones de las aristas.
¿Cuántos grafos no dirigidos hay? Para cada par de nodos, pueden estar conectados o desconectados (dos opciones). Si $|V| = p$ Hay ${p \choose 2} = \frac{p(p - 1)}{2}$ pares de nodos distintos. Por lo tanto, el número de DAGs está limitado por $2^{p(p-1 )/2}$ .
Podemos limitar el número de DAGs con un argumento similar. Ignorando el requisito de acyclicidad, cada par de nodos $A$ y $B$ puede estar desconectada, conectada $A \to B$ o conectado $B \to A$ (tres opciones). Por lo tanto, el número de DAGs está limitado por $3^{p(p-1 )/2}$ .
