Combinatoria
Olimpiada China de Matemáticas Femenina (2019)
Olimpiada China de Matemáticas Femenina 2019 Problema 8
8 Para un torneo con $8$ vértices, si desde cualquier vértice es imposible seguir una ruta que regrese a sí mismo, llamamos al grafo un grafo bueno. De lo contrario, lo llamamos un grafo malo. Demuestre que $(1)$ existe un torneo con $8$ vértices tal que después de cambiar la orientación de a lo sumo $7$ aristas cualesquiera del torneo, el grafo es siempre un grafo malo; $(2)$ para cualquier torneo con $8$ vértices, se puede cambiar la orientación de a lo sumo $8$ aristas del torneo para obtener un grafo bueno. (Un torneo es un grafo completo con aristas dirigidas.)
3
0
Kevin
Inicia sesión para agregar soluciones y pistas