Categoría: Teoría de grafos

Un ciclo que pasa por todos los vértices son llamados ciclos Hamiltonianos. Un grafo que contiene un ciclo de Hamilton se llama grafo Hamiltoniano.

Una trayectoria que pasa por todos los vértices se denomina trayectoria Hamiltoniana.

Si el último enlace de un ciclo Hamiltoniano es borrado conseguiremos una trayectoria Hamiltoniana, sin embargo, un grafo no Hamiltoniano puede tener una trayectoria Hamiltoniana.

Ejemplos:

El n-ciclo $C_n$ con n vértices distintos es Hamiltoniano. Ahora, dado cualquier grafo Hamiltoniano G, el supergrafo G’, obtenido por añadir nuevos enlaces entre vértices no adyacentes también es Hamiltoniano. Por ejemplo $K_n$ es un supergrafo de $C_n$ y por lo tanto $K_n$  es Hamiltoniano.

El siguiente teorema, debido a Dirac, nos da condiciones suficientes para tener un grafo Hamiltoniano.

 

Teorema. (Dirac) Si G es un grafo con n vértices, donde $n\geq 3$ y $d(v)\geq n/2$, para cada vértice $v$ de G, entonces G es Hamiltoniano. 

 

Prueba.

Supongamos que G no es Hamiltoniano. Entonces para algún valor $n\geq 3$ hay un grafo no Hamiltoniano H en el cual $d(v)\geq n/2$ para cada vértice de H. Entonces en cualquier supergrafo  K de H esa desigualdad se mantiene si K tiene el mismo conjunto de vértices que H, pues en ese caso a K se lo obtiene simplemente por añadir enlaces a H. Entonces existe un grafo no Hamiltoniano maximal G con n vértices y que satisface la desigualdad $d(v)\geq n/2$ para cada vértice de G.

 

Obviamente G no es la gráfica completa $K_n$, pues dicha gráfica es Hamiltoniana. Luego, hay en G vértices que no están conectados u, v. Sea G+uv un nuevo supergrafo de G. Dado que G es no Hamiltoniano maximal, entonces G+uv es Hamiltoniano, y uv pertenece al ciclo Hamiltoniano.

Sea $C: u=v_1 v_2 v_3.. v_n=v$, ahora sea $S=\{v_i \in C: uv_{i+1}\in E(G)\}$ y $T=\{v_j \in C: vv_{j}\in E(G)\}$. Observemos que v no pertenece al conjunto T ni al conjunto S.

Sea $|S| , |T|$ y  $| S \cup T |$ las cardinalidades de dichos conjuntos. Entonces $|S \cup T|<n$, y para cada enlace incidente con u, corresponde un vértice $v_i \in S$, así $|S|=d(u)$. Usando un argumento parecido, $|T|=d(v)$.

La siguiente idea es interesante: Supongamos que algún vértice $v_k\in S\cap T$, entonces hay dos enlaces, uno que une a u con $v_{k+1}$  y otro que une a v con $v_k$. Esto implica que el conjunto $C'=v_1, v_{k+1}, v_{k+2}, .., v_n, v_k, v_{k-1}, .., v_1$ es un ciclo Hamiltoniano en G, lo que contradice que G sea no Hamiltoniano. Así $S\cap T$ es vacío.

 

Finalmente $|S\cup T|=|S|+|T|-|S\cap T|$ nos da que $|S|+|T|=|S \cup T|$, tal que $d(u)+d(v)<n$. Esto es una contradicción porque $d(u)\geq n/2$ para todo vértice en G. Y la prueba está terminada.

 

 

En teoría de grafos una técnica bastante usada es proceder suponiendo que la proposición es falsa y analizando las consecuencias de dicha suposición hasta llegar a una contradicción.

El siguiente teorema fue realizado por Erdös en 1965.

 

Teorema. (Erdös) Cada grafo sin lazos contiene un subgrafo bipartito generador $F$ tal que $d_F(v)\geq \frac{1}{2} d_G(v)$ para todo $v\in V$

Demostración.

Sea $G$ un grafo sin lazos. G tiene un subgrafo generador bipartito, uno de ellos es, por ejemplo, el subgrafo generador vacío. Sea $F=F[X, Y]$ un subgrafo generador bipartito con el máximo número de enlaces. Afirmamos que $F$ satisface la propiedad requerida. Supongamos que no, entonces existe algún vértice tal que

 

$d_F(v) < \frac{1}{2} d_G(v)$

Sin pérdida de generalidad, podemos suponer que v está en el conjunto X. Consideremos el subgrafo bipartito generador F’ cuyo conjunto de enlaces consiste de todos los enlaces de G con un terminal en $X\setminus v$ y otro en $Y\setminus v$. El conjunto de enlaces de F’ es el mismo conjunto de enlaces de F excepto por aquellos enlaces incidentes en v, aquellos que están en F no están en F’ y aquellos que no están en F están en F’.

$\begin{aligned}e(F')=e(F)-d_F(v)+(d_G(v)-d_F(v))\\=e(F)+(d_G(v)-2d_F(v))>e(F) \end{aligned}$

Pero esto contradice que F sea el subgrafo bipartito generador con mayor número de enlaces.

Un grafo completo es un grafo simple en el todo vértice está conectado a todos los vértices restantes. Si a este grafo completo le damos dirección a sus enlaces obtendremos un grafo dirigido, al cual le llamaremos torneo.

Una trayectoria hamiltoniana es una trayectoria que pasa por todos los vértices del grafo. En 1934 Rédei probó un teorema básico sobre torneos y lo hizo usando un argumento de inducción.

 

 

Teorema. (Teorema de Rédei) Todo torneo tiene una trayectoria Hamiltoniana dirigida.

Demostración.

Usaremos inducción sobre el número de vértices.

Caso base: $n=1$ . El torneo trivial (sobre un vértice) tiene una trayectoria Hamiltoniana dirigida.

 

Paso inductivo. Supongamos ahora que $n\geq 2$ y que todo torneo sobre $n-1$ vértices tiene una trayectoria Hamiltoniana dirigida. Sea  $T$ un torneo sobre $n$ vértices y sea $v\in V(T)$. El digrafo $T'=T-v$ es un torneo sobre $n-1$ vértices y por hipótesis de inducción tiene una trayectoria Hamiltoniana dirigida $P'=v_1v_2..v_{n-1}$.

 

Caso 1: $(v, v_1)$ es un arco. En este caso la trayectoria Hamiltoniana buscada es $T=v\cup T'$

Caso 2: $(v_{n-1}, v)$ es un arco. En este caso la trayectoria Hamiltoniana buscada es $T= T'\cup v$

Caso 3: $(v_1, v) y (v, v_{n-1})$ son arcos. En este caso existe un $v_j$ tal que  $(v_j, v)$ y $(v, v_{j+1})$ son arcos. En tal caso la trayectoria $T$ buscada sería $T=v_1 v_2.. v_j v v_{j+1}..v_{n-1}$.

De lo que se concluye la prueba.