Explorando Grafos y Árboles: Conceptos y Algoritmos Clave

Conceptos Fundamentales de Grafos

Grafo Completo (K_n)

Un grafo completo es aquel donde todos los vértices están conectados entre sí. El número de aristas en un grafo no dirigido es n*(n-1)/2, y en un grafo dirigido es n*(n-1), donde 'n' es el número de vértices.

Grafo Bipartito (K_m,n)

En un grafo bipartito, los vértices se dividen en dos conjuntos disjuntos, y las aristas solo conectan vértices de conjuntos diferentes. Los vértices de un mismo conjunto no pueden ser adyacentes. El número máximo de aristas en un grafo bipartito es (n²)/4 (cuando los dos conjuntos tienen el mismo número de elementos, o lo más cercano posible).

Subgrafos

• Subgrafo Propio: Contiene un subconjunto de vértices y aristas del grafo original, verificando que las conexiones existan.
• Subgrafo Expandido (Spanning Subgraph): Contiene el mismo número de vértices que el grafo original, pero puede tener un subconjunto de las aristas.
• Subgrafo Inducido: Contiene un subconjunto de vértices del grafo original y todas las aristas que conectan esos vértices en el grafo original.

Trayectoria Simple

Una trayectoria simple es una secuencia de vértices y aristas donde no se repiten aristas. Representa una forma de ir desde un vértice 'a' hasta un vértice 'b' sin repetir aristas.

Grafos Isomorfos

Dos grafos son isomorfos si tienen el mismo número de vértices y aristas, y los grados de los vértices correspondientes son iguales. Esencialmente, existe una correspondencia uno a uno entre los vértices de ambos grafos que preserva las adyacencias. Una forma de verificarlo es construir las matrices de adyacencia de ambos grafos; si son iguales (o se pueden permutar para ser iguales), los grafos son isomorfos.

Grafo Euleriano

Un grafo es euleriano si todos sus vértices tienen grado par. Un camino euleriano es un camino que recorre todas las aristas del grafo exactamente una vez. Un circuito euleriano es un camino euleriano que comienza y termina en el mismo vértice.

Trayectoria Euleriana

Existe una trayectoria euleriana si y solo si hay exactamente dos vértices de grado impar. La trayectoria comienza en uno de los vértices de grado impar y termina en el otro.

Grafo Hamiltoniano

Un grafo es hamiltoniano si contiene un ciclo hamiltoniano. Un camino hamiltoniano visita cada vértice exactamente una vez. Un ciclo hamiltoniano es un camino hamiltoniano que comienza y termina en el mismo vértice.

Algoritmos en Grafos

Algoritmo de Dijkstra

Este algoritmo encuentra el camino más corto desde un vértice de origen a todos los demás vértices en un grafo ponderado (con pesos no negativos). Se utiliza una tabla para registrar las distancias mínimas y se actualiza iterativamente.

1. Inicialización:
   • S₀: Conjunto de vértices visitados (inicialmente solo el vértice de origen).
   • C: Conjunto de vértices restantes.
   • Dist: Distancia desde el origen a cada vértice (inicialmente 0 para el origen e infinito para los demás).
2. Iteración:
   • Seleccionar el vértice X en C con la menor Dist.
   • Mover X de C a S₀.
   • Para cada vecino K de X que esté en C, calcular: Dist{K} = min(Dist{K}, Dist{X} + Dist{X,K}).
3. Terminación: Repetir hasta que C esté vacío.

Árboles

Terminología de Árboles

• Raíz: El nodo superior del árbol.
• Hojas: Nodos sin hijos.
• Orden: Número de hijos de la raíz.
• Grado de un nodo: Número de subárboles de un nodo.
• Grado del árbol: Máximo grado de todos los nodos.
• Nivel de un nodo: La raíz tiene nivel 1, y cada nivel subsiguiente aumenta en 1.
• Altura del árbol: Máximo nivel de todos los nodos.
• Ancestros: Todos los nodos en el camino desde un nodo dado hasta la raíz.

Árbol Binario de Búsqueda

Un árbol binario de búsqueda es un árbol binario donde el valor de cada nodo en el subárbol izquierdo es menor que el valor del nodo raíz, y el valor de cada nodo en el subárbol derecho es mayor. La raíz se establece con el primer número de los datos, y los siguientes se insertan manteniendo el orden relativo.

Algoritmos en Árboles (Árboles de Expansión Mínima)

Algoritmo de Prim

Este algoritmo encuentra un árbol de expansión mínima (MST) para un grafo ponderado conexo. El MST es un subgrafo que conecta todos los vértices con el menor costo total de aristas posible.

1. Comenzar con un vértice arbitrario (o uno especificado).
2. Seleccionar la arista de menor peso conectada a un vértice ya incluido en el árbol.
3. Agregar la arista y el vértice conectado al árbol.
4. Repetir hasta que todos los vértices estén incluidos, descartando aristas que formen ciclos.
5. El costo mínimo es la suma de los pesos de las aristas seleccionadas.

Algoritmo de Kruskal

Este algoritmo también encuentra un árbol de expansión mínima (MST).

1. Crear una lista de todas las aristas del grafo, ordenadas por peso de menor a mayor.
2. Seleccionar la arista de menor peso.
3. Si la arista no forma un ciclo con las aristas ya seleccionadas, agregarla al árbol.
4. Repetir hasta que se hayan considerado todas las aristas (o hasta que se hayan conectado todos los vértices).
5. El costo mínimo es la suma de los pesos de las aristas seleccionadas.

Nota: En Prim y Kruskal, es útil marcar las aristas seleccionadas para evitar ciclos y facilitar la visualización del árbol de expansión mínima resultante.