Esta pregunta se refiere a un método para dibujar gráficos y a una característica de los mismos sobre la que quiero aprender más.
Consideremos un grafo dirigido conectado con al menos un nodo con grado de entrada 0 y un nodo con grado de salida 0 (llamémoslo gráfico de entrada-salida ). Dibuja los nodos de entrada igualmente espaciados en la capa 0:
Cada nodo tiene una distancia mínima bien definida $d_{in}$ a la capa de entrada 0. Dibuja los nodos con $d_{in}=n$ en la capa $n$ :
Ahora dibuja todas las aristas que conectan las capas adyacentes:
Y por último, dibuja todas las demás aristas:
Tenga en cuenta que ninguna de estas capas puede interpretarse como el capa de salida, sino que se basa en una prescrito capa de salida se puede hacer la misma construcción (en sentido contrario).
Cada borde $(v_0,v_1)$ tiene una longitud única y bien definida $\lambda$ con respecto a las capas que conecta. Sea $v_0$ sea un nodo de la capa $n_0$ y $v_1$ un nodo en la capa $n_1$ .
$$\lambda((v_0,v_1)) = n_1 - n_0$$
Obsérvese que, por construcción, no puede haber una arista con $\lambda(e)>1$
La característica que tengo en mente no es otra que la distribución $d$ de las longitudes $\lambda$ :
$$d(l) = \text{number of edges $ e $ with $ \N -lambda(e)=l $}$$
Nótese que la distribución correspondiente con respecto a la capa de salida puede ser muy diferente.
Es obvio que para los gráficos de entrada-salida estrictamente estratificados (especialmente los árboles) $d(1) = \text{number of edges}$ y $d(l)=0$ Para $l\neq 1$ .
Pero, ¿qué pasa con los gráficos de entrada-salida aleatorios o de mundo pequeño? ¿Sería una buena característica para distinguirlos?
Pregunta : ¿Se ha definido antes esta característica y con qué nombre?
