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