Teoría de GRAFOS en INFORMÁTICA: Que es un grafo, Tipos de Grafos, como representarlos y ejemplos

Teoría de Grafos: Introducción

Key Concepts:

• Teoría de grafos: Representación y modelado de relaciones entre conjuntos de datos.
• Vértices (nodos): Piezas fundamentales de un grafo, representan entidades.
• Arcos (aristas): Líneas que conectan vértices, representan relaciones.
• Grafos no dirigidos: Arcos sin orientación (V-U es idéntico a U-V).
• Grafos dirigidos: Arcos con orientación (V-U no es idéntico a U-V).
• Grafos con pesos: Arcos con un valor numérico asociado (peso).
• Árboles: Grafos no dirigidos sin ciclos.
• Árboles con raíz: Grafos dirigidos con un vértice desde el cual se puede llegar al resto.
• Grafos acíclicos dirigidos (DAG): Grafos dirigidos sin ciclos.
• Grafos bipartitos: Vértices separables en dos grupos, conexiones solo entre grupos.
• Matriz de adyacencia: Representación con filas/columnas como vértices, celdas como pesos de arcos.
• Lista de adyacencia: Lista por vértice con tuplas (vértice destino, peso del arco).

¿Qué es la Teoría de Grafos?

La teoría de grafos en ciencias de la computación se enfoca en representar y modelar relaciones entre conjuntos de datos. Permite modelar una amplia variedad de problemas. Un ejemplo es modelar una red social donde los vértices son personas y los arcos representan relaciones de amistad.

• Ejemplo: En una red social modelada como un grafo, se puede determinar cuántos amigos directos tiene una persona (vértices vecinos) o cuántos grados de separación hay entre dos personas. Si Tadeo tiene tres amigos directos (Juan, Juaco y Mica), estos son sus vértices vecinos.

Componentes de un Grafo

1. Vértices: Son los nodos o círculos que representan las entidades. En el ejemplo, Tadeo, Juan, Juaco, Mica, Luz y Juli son vértices.
2. Arcos: Son las líneas que conectan los vértices, representando las relaciones entre ellos.

Tipos de Grafos

1. Grafos No Dirigidos: Los arcos no tienen una dirección específica. El arco que conecta el vértice 0 y el vértice 5 es el mismo que el que conecta el vértice 5 y el vértice 0.
2. Grafos Dirigidos: Los arcos tienen una dirección. El arco que conecta el vértice 0 con el vértice 5 está dirigido desde el vértice 0 hacia el vértice 5, pero no al revés.
3. Grafos con Pesos: Los arcos tienen un peso asociado, que puede representar distancias, costos, o cualquier otra métrica relevante. Pueden ser dirigidos o no dirigidos.

Grafos Especiales

1. Árboles: Son grafos no dirigidos que no contienen ciclos.
2. Árboles con Raíz: Son grafos dirigidos que tienen un vértice raíz desde el cual se puede acceder a todos los demás vértices. En el ejemplo, desde el vértice 0 se puede llegar a los vértices 1, 2, 3, 4 y 5.
3. Grafos Acíclicos Dirigidos (DAG): Son grafos dirigidos que no contienen ciclos.
   • Dato Curioso: El protocolo IOTA de criptomonedas utiliza un DAG en su arquitectura.
4. Grafos Bipartitos: Los vértices se pueden dividir en dos grupos, y los arcos solo conectan vértices de grupos diferentes. Un vértice de un grupo solo se conecta con vértices del otro grupo, nunca con uno de su mismo grupo.

Representación de Grafos

1. Matriz de Adyacencia:
   • Las filas y columnas representan los vértices del grafo.
   • Cada celda (i, j) contiene el peso del arco que conecta el vértice i con el vértice j. Si no hay arco, el valor es 0.
   • Ejemplo: Para un grafo con vértices A, B, C, D, la matriz se construye preguntando el peso de ir de un vértice a otro. Por ejemplo, el peso de ir de A a A es 0, de A a B es 1, de A a C es -4, y de A a D es 2.
2. Lista de Adyacencia:
   • Se crea una lista para cada vértice.
   • Cada lista contiene tuplas (vértice destino, peso del arco).
   • Ejemplo: Para el vértice A, la lista contendría (B, 1), (C, -4), (D, 2), indicando que desde A se puede ir a B con peso 1, a C con peso -4, y a D con peso 2.

Conclusión

La teoría de grafos es una herramienta poderosa para modelar relaciones entre datos. Comprender los diferentes tipos de grafos y cómo representarlos es fundamental para resolver problemas en ciencias de la computación. La matriz de adyacencia y la lista de adyacencia son dos métodos comunes para representar grafos en la programación.