¿Cuántos bordes puede haber en un DAG?

En un gráfico acíclico dirigido con n vértices, ¿cuál es el número máximo posible de bordes dirigidos en él?¿Cuántos bordes puede haber en un DAG?

Fuente

2012-07-28 user1559262

Esta pregunta es fuera de tema para el desbordamiento de pila . Puede probar http://math.stackexchange.com/, que acepta preguntas de matemáticas en todos los niveles. –

Sin mencionar, esto suena como un problema de tarea. Y tomé el cebo: -/ –

Además, es un duplicado de [¿Cómo puedo probar la cantidad máxima de bordes?] (Http://math.stackexchange.com/questions/61579/how-can-i-prove- the-maximum-number-of-edges) –

Supongamos N vértices/nodos, y exploremos la construcción de un DAG con bordes máximos. Considere cualquier nodo dado, digamos N1. El número máximo de nodos a los que puede apuntar, o bordes, en esta etapa inicial es N-1. Vamos a elegir un segundo nodo N2: puede apuntar a todos los nodos, excepto a sí mismo y N1 - eso es N-2 bordes adicionales. Continúe por los nodos restantes, cada uno puede apuntar a un borde menos que el nodo anterior. El último nodo puede señalar a otros 0 nodos.

Suma de todos los bordes: (N-1) + (N-2) + .. + 1 + 0 == (N-1) (N)/2

Fuente

2012-07-28 07:19:51

Muchas gracias por su respuesta. – user1559262

Hmm, [esto] (http://stackoverflow.com/questions/5058406/what-is-the-maximum-number-of-edges-in-a-directed-graph-with-n-nodes) parece argumentar con la respuesta –

@RealzSlaw La distinción es que un DAG es "acíclico"; la publicación a la que se refiere discute gráficos dirigidos en general. –

¿Cuántos bordes puede haber en un DAG?

Respuesta

Cuestiones relacionadas