Teoría de Grafos: Primera Parte

Introducción

• Los grafos son modelos naturales para representar relaciones arbitrarias entre objetos de datos.
• Juegan un papel importante en las matemáticas y en la fundamentación de Ciencias de la Computación.
• Existen dos tipos principales de grafos:
  • Grafos no dirigidos
  • Grafos dirigidos o digrafos

Terminología Básica

• Digrafo: Conjunto de vértices (X) y arcos (U).
  • Los vértices se representan con puntos o círculos.
  • Los arcos se representan con flechas que conectan pares de vértices.
• Grafo: Conjunto de vértices y aristas sin dirección.
• Arcos Paralelos: Arcos que tienen los mismos vértices inicial y final.

Especificaciones Formales

• Digrafo (G) definido por la terna (X, U, ℓ):
  • X: Conjunto de vértices.
  • U: Conjunto de arcos.
  • ℓ: Función de incidencia ℓ: U → X².
• Funciones:
  • ℓ⁻¹: Inversa de la función de incidencia.
  • Funciones de incidencia negativa (ℓ⁻) y positiva (ℓ⁺).
  • Grado de salida (g⁺) y entrada (g⁻) de un vértice.

Características de los Vértices

• Vértice aislado: No tiene arcos entrantes ni salientes.
• Fuente: Vértice sin arcos entrantes.
• Sumidero: Vértice sin arcos salientes.

Características de Grafos

• Regularidad: Todos los vértices tienen el mismo grado.
• Simetría: Un digrafo es simétrico si para cada arco en un sentido hay otro en el sentido contrario.
• Completitud: Grafos donde existen aristas entre cada par de vértices.

Subgrafos y Grafos Parciales

• Subgrafo: Parte de un grafo que conserva su estructura.
• Grafo parcial: Mantiene los vértices pero omite algunas aristas.
• Subgrafo parcial: Combinación de subgrafo y grafo parcial.

Cadenas, Caminos, Ciclos y Circuitos

• Cadena: Secuencia de arcos con extremos compartidos.
• Camino: Secuencia de arcos siguiendo una dirección.
• Ciclo: Cadena cerrada simple.
• Circuito: Camino que es también un ciclo.

Conexidad

• Conexo: Existe una cadena entre cada par de vértices.
• Fuertemente conexo: Existe un camino entre cada par de vértices.
• Componentes conexas: Subgrafos conexos máximos.

Cociclos y Cocircuitos

• Cociclo: Conjunto de arcos que conecta subconjuntos de vértices.
• Cocircuito: Cociclo donde todos los arcos salen de o llegan a un conjunto de vértices.

Ejemplos

• Ejemplos prácticos de grafos dirigidos en diferentes contextos como empresas, materias, transporte, etc.

Reconocimientos

• Basado en trabajos de Hugo Ryckeboer y libros de Claude Berge y Jonathan Gross y Jay Yellen.

Estas notas resumen los conceptos clave de la teoría de grafos, útil como una herramienta para modelizar fenómenos discretos y comprender estructuras de datos y algoritmos. La teoría abarca desde terminología y características básicas hasta tipos de grafos más complejos como bipartitos y completos.