Conceptos Clave en Teoría de Grafos: Euler, Hamilton, Árboles y Bipartitos

Este documento explora definiciones y propiedades fundamentales de diversos tipos de grafos, incluyendo los grafos de Euler, los grafos de Hamilton, los árboles y los grafos bipartidos, proporcionando ejemplos y consideraciones prácticas para su identificación y comprensión.

Grafos de Euler y Hamilton: Ejemplos y Distinciones

A continuación, se analizan varios ejemplos de grafos para ilustrar las propiedades de los ciclos de Euler y Hamilton, así como sus diferencias.

Ejemplos de Grafos y sus Propiedades

• Grafo (a): Es de Euler porque es conexo y todos sus vértices tienen grado par (grado 2). Además, es de Hamilton porque el grafo en sí mismo constituye un ciclo hamiltoniano.
• Grafo (b): Es de Euler por ser conexo y tener todos sus vértices de grado par (todos de grado 2, excepto el central que tiene grado 4). Sin embargo, NO es de Hamilton. Esto se debe a que, al tener los dos vértices de la derecha grado 2, en cualquier ciclo hamiltoniano hipotético, las tres aristas del triángulo de la izquierda deberían intervenir, lo cual formaría un ciclo que no incluiría todos los vértices del grafo.
• Grafo (c): Es de Hamilton porque, siguiendo el camino indicado por las flechas, se obtiene un ciclo hamiltoniano. No obstante, NO es de Euler, ya que el vértice de la esquina superior izquierda tiene grado impar (grado 3).
• Grafo (d): Finalmente, el grafo (d) NO es de Euler, dado que los vértices inferiores tienen grado 3 (impar). Tampoco es de Hamilton, pues para formar un ciclo hamiltoniano se requeriría una arista entre vértices de la misma altura, lo cual no es posible en este grafo.

Es importante destacar que no existe una relación directa o inherente entre los grafos de Euler y los grafos de Hamilton; un grafo puede ser de un tipo y no del otro, o de ambos, o de ninguno.

Estrategias para la Búsqueda de Ciclos Hamiltonianos

Lamentablemente, no existen caracterizaciones sencillas o elegantes para determinar si un grafo es hamiltoniano. A continuación, se presentan algunas consideraciones clave para la búsqueda de ciclos hamiltonianos:

1. Si un grafo G posee un ciclo hamiltoniano, el grado de cada uno de sus vértices debe ser mayor o igual a 2.
2. Si deg(v) = 2 para un vértice v, las dos aristas incidentes a v deben formar parte de cualquier ciclo hamiltoniano de G.
3. Si deg(v) > 2, una vez que se atraviesa el vértice v, las aristas no utilizadas incidentes a v deben ser descartadas para la construcción del ciclo.
4. Al construir un ciclo hamiltoniano para G, no se debe formar un ciclo en un subgrafo de G a menos que dicho subgrafo contenga todos los vértices de G.

Conceptos Fundamentales en Teoría de Grafos: Árboles y Grafos Bipartidos

Árboles y Bosques: Definiciones y Características

Un árbol es un grafo conexo que no contiene ciclos. Un grafo que no contiene ciclos (pero que puede no ser conexo) se denomina bosque. A continuación, se presentan algunas propiedades fundamentales:

1. En un árbol, cualesquiera dos vértices están conectados por exactamente un camino simple.
2. Si G es un árbol con n vértices y m aristas, entonces m = n - 1. (Si G es un bosque con n vértices, m aristas y t componentes conexas —es decir, t árboles—, entonces m = n - t).

Grafos Bipartidos: Estructura y Apareamientos

Un grafo bipartido es un grafo G = (V, E) tal que su conjunto de vértices V puede ser particionado en dos conjuntos disjuntos V' y V'' (es decir, V = V' ∪ V'' y V' ∩ V'' = Ø) de tal manera que cada arista en E conecta un vértice de V' con un vértice de V''. En otras palabras, no hay aristas que conecten dos vértices dentro de V' ni dos vértices dentro de V''. Los conjuntos V' y V'' se denominan conjuntos de vértices complementarios o particiones bipartitas de G.

Caracterización de Grafos Bipartidos

Un grafo G es bipartido si y solo si no contiene ciclos de longitud impar.

Apareamientos en Grafos Bipartidos

Dado un grafo bipartido G con partición V = V' ∪ V'' y un conjunto V' = {v₁, ..., v_q}, un apareamiento (o matching) de V' a V'' es un subgrafo de G que consiste en q aristas de la forma {v_i, w_i} (donde 1 ≤ i ≤ q), tal que cada w_i ∈ V'' y todas las w_i son distintas. Es decir, cada vértice en V' está conectado a exactamente un vértice en V'', y ningún vértice en V'' está conectado a más de un vértice de V'.

En la Figura 7 (mencionada en el texto original), si el conjunto de vértices V se divide en V' = {v₁, v₂, v₃} y U = {u₁, u₂, u₃, u₄}, un ejemplo de apareamiento de V' a U podría ser el conjunto de aristas {(v₁, u₁), (v₂, u₂), (v₃, u₃)}. Es importante notar que este no es el único apareamiento posible.

Cuando el número de vértices es el mismo en ambos conjuntos complementarios (es decir, |V'| = |V''|) y se logra un apareamiento que cubre todos los vértices de ambos conjuntos, se denomina apareamiento perfecto.