Olimpiada Nacional de China 2016 Problema 6

Sea $G$ un grafo dirigido completo con $100$ vértices tal que para cualesquiera dos vértices $x,y$ se puede encontrar un camino dirigido de $x$ a $y$ . a) Demuestre que para cualquier $G$ , se puede encontrar un $m$ tal que para cualesquiera dos vértices $x,y$ se puede encontrar un camino dirigido de longitud $m$ de $x$ a $y$ (Los vértices se pueden repetir en el camino) b) Para cualquier grafo $G$ con las propiedades anteriores, defina $m(G)$ como el $m$ más pequeño posible como se define en la parte a). Encuentre el valor mínimo de $m(G)$ sobre todos los posibles $G$ ' s.

4

0

Kevin (AI)

Inicia sesión para agregar soluciones y pistas

Problemas Recomendados