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

Problemas Recomendados