En $n$ grafo dirigido de nodos, cada vértice tiene grado de entrada y grado de salida igual a $4$ . Si cada vértice es accesible desde cualquier otro vértice dirigido por un camino de longitud como máximo $2$ . ¿Cómo podemos encontrar el valor máximo de $n$ ?
Respuesta
¿Demasiados anuncios?
user2097
Puntos
2061
La respuesta es $20$ . Para construir un ejemplo con $n=20$ tomemos el grafo cuyos vértices son todos los pares $(p,q)$ con diferentes $p,q\in\{1,2,3,4,5\}$ y supongamos que existe una arista desde $(i,j)$ a $(k,l)$ sólo si $j=k$ . Es evidente que $(i,j)\to(j,k)\to(k,l)$ es una ruta desde $(i,j)$ a $(k,l)$ si $j\neq k$ .
Evidentemente, el número de vértices que pueden alcanzarse a partir de determinados $u$ por caminos de longitud $k$ es como máximo $\mathrm{outdegree}^k$ de modo que el límite superior es $4^0+4^1+4^2=21$ . (En realidad, se trata de un comentario de Jorge Fernández.) Para ver que este límite no puede alcanzarse es más difícil, véase este documento para la prueba.
