Demuestre que cada torneo contiene al menos una ruta hamiltoniana.

Question

Un torneo es un grafo dirigido con exactamente una arista entre cada par de vértices. (Así, para cada par (u,v)(u,v) de los vértices, el borde de uu a vv o de vv de uu existe, pero no tanto.) Usted puede pensar en los nodos como los jugadores en un torneo, donde cada jugador tiene que jugar contra todos los demás jugadores. El borde puntos del ganador al perdedor de un juego. Un camino Hamiltoniano (no ciclo) es una secuencia de consecutivos dirigida bordes que visita cada vértice exactamente una vez.

Cómo puedo probar que cada torneo en el que contiene al menos un camino Hamiltoniano? gracias a tu ayuda!

Answer 1

Esto puede ser demostrado mediante fuertes de la inducción. Deje $n$ el número de vértices. Al $n \le 2$, un camino hamiltoniano. Ahora, para todas las $n > 2$, recoger cualquier vértice $v$. Partición de todos los otros vértices distintos de $v$ en los conjuntos de $V_{out}$ y $V_{in}$ -- $V_{out}$ contiene a todos los demás vértices $u$ de manera tal que el borde de la $(v, u)$ existe, mientras que $V_{in}$ contiene a todos los demás vértices $u$ de manera tal que el borde de la $(u, v)$ existe.

Claramente $|V_{out}| < n$$|V_{in}| < n$, de modo que por la hipótesis inductiva, existe un camino hamiltoniano en ambos conjuntos. Deje $H_{out}$ ser cualquier camino hamiltoniano en $V_{out}$ $H_{in}$ ser cualquier camino hamiltoniano en $V_{in}$. Usted puede entonces formar un camino hamiltoniano para todos los vértices mediante la concatenación de $H_{in}$, $v$, y $H_{out}$.