Combinatoria
Olimpiada Nacional China (2016)
Olimpiada Nacional China 2016 Problema 6
6 Sea $G$ una gráfica dirigida completa con $100$ vértices tal que para cualesquiera dos vértices $x,y$ se puede encontrar una trayectoria dirigida de $x$ a $y$ . a) Demuestre que para cualquier $G$ de este tipo, se puede encontrar un $m$ tal que para cualesquiera dos vértices $x,y$ se puede encontrar una trayectoria dirigida de longitud $m$ de $x$ a $y$ (los vértices pueden repetirse en la trayectoria) b) Para cualquier gráfica $G$ con las propiedades anteriores, defina $m(G)$ como el menor $m$ posible definido en la parte a). Halle el valor mínimo de $m(G)$ sobre todas las gráficas $G$ posibles.
4
0
Kevin
Inicia sesión para agregar soluciones y pistas