Conceptos Esenciales y Algoritmos Fundamentales de la Teoría de Grafos

Fundamentos de la Teoría de Grafos

Un Grafo es una estructura de datos no lineal, que puede ser considerada como un conjunto de vértices y arcos que conectan esos vértices.

Definiciones Clave

Arista / Arco

Elemento que conecta dos vértices en un grafo.

Camino

Es una secuencia de vértices. La longitud del camino es la cantidad de arcos que este contiene.

Camino Simple

Es aquel donde todos sus vértices son distintos. Solo el primero y el último pueden coincidir.

Ciclo

Es un camino simple y cerrado.

Grafo Conexo

Si desde cualquier vértice existe un camino hasta cualquier otro vértice del grafo.

Grafo Fuertemente Conexo (Dígrafo)

Si para todo par de vértices existe un camino dirigido.

Árbol

Si un grafo no dirigido es conexo y acíclico.

Propiedades y Terminología de Vértices y Aristas

• Dos vértices son adyacentes si son extremos de una misma arista.
• Dos aristas son adyacentes si tienen un extremo en común.
• Un vértice y una arista son incidentes si el vértice es extremo de la arista.
• Un vértice es aislado si no tiene otros vértices adyacentes.

Métricas del Grafo

Grafo Completo

Es un grafo simple en el que todo par de vértices está unido por una arista.

Orden

Número de vértices.

Tamaño

Número de aristas.

Grado de Vértice

Número de aristas que lo tienen como extremo (aristas incidentes).

Representación de Grafos en Memoria

Existen dos maneras principales de mantener un grafo en la memoria (MEM):

1. Representación Secuencial: Matriz de adyacencia.
2. Representación Enlazada: Listas enlazadas.

Recorridos en Grafos y Árboles

Recorridos de Grafos

Recorrido por Amplitud (BFS - Breadth-First Search)

Se visita a todos los vecinos directos del nodo inicial, luego a los vecinos de los vecinos, y así sucesivamente (por niveles).

Recorrido por Profundidad (DFS - Depth-First Search)

La idea es alejarse lo más posible del nodo inicial, luego devolverse un paso e intentar lo mismo por otro camino.

Recorridos de Árboles Binarios

Estos recorridos son específicos para estructuras de árbol:

• Recorrido Postorden: Izquierda - Derecha - Raíz
• Recorrido Inorden: Izquierda - Raíz - Derecha
• Recorrido Preorden: Raíz - Izquierda - Derecha

Algoritmos Fundamentales en Grafos

Árbol Cobertor Mínimo (ACM)

Dado un grafo G no dirigido y conexo, se dice que un subgrafo T de G es un Árbol Cobertor si es un árbol y contiene el mismo número de nodos que G.

Los siguientes algoritmos se utilizan para encontrar un Árbol Cobertor Mínimo en un grafo no dirigido, conexo y con costos asociados a los arcos:

1. Algoritmo de Kruskal

Comienza inicialmente con un grafo que contiene solo los nodos del grafo original, sin arcos. Luego, en cada iteración, se agrega al grafo el arco más barato que no introduzca un ciclo. El proceso termina cuando el grafo está completamente conectado.

2. Algoritmo de Prim

Al inicio, el conjunto B contiene un vértice arbitrario. En cada paso, el algoritmo considera todas las aristas que tocan a B y selecciona la de menor peso. Después, el algoritmo añade a B el vértice ligado por esa arista que no estaba en B. El proceso continúa hasta que B contenga a todos los vértices de G.

Algoritmo de Dijkstra

Halla la distancia más corta entre dos vértices dados en un grafo con pesos no negativos.