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

Problemas Recomendados