🌐 Grafos: Conceptos Fundamentales
🔷 ¿Qué es un Grafo?
Un grafo es un conjunto de nodos (vértices) y aristas (conexiones) que los unen. Se pueden clasificar como:
- Dirigidos 🎯 (con flechas, tienen orientación)
- No dirigidos 🔄 (sin orientación)
📌 Tipos y Características
| Concepto | Descripción |
|---|---|
| Árbol | Grafo sin ciclos. Un árbol no jerárquico no permite referencias cíclicas. |
| Orden del grafo | Número de vértices. |
| Incidencia | Una arista es incidente a un vértice si lo une con otro. |
| Grado de un nodo | Número de aristas (o «vecinos») que conectan con él. |
| Grado de entrada/salida | En grafos dirigidos: aristas que llegan/salen de un vértice. |
| Adyacencia | Dos vértices son adyacentes si están conectados por una arista. |
| Ponderación | Cada arista puede tener un peso (coste, tiempo, longitud…). |
| Grafo completo | Todos los nodos están conectados entre sí. |
| Grafo euleriano | Recorre todas las aristas una vez sin repetir y termina en el mismo nodo. |
| Matriz de adyacencia | Tabla que indica conexiones y pesos entre nodos. |
| Lista de adyacencia | Vector con listas de nodos adyacentes por vértice. |
📘 Otros conceptos:
- Grafo mixto: combina aristas dirigidas y no dirigidas.
- Grafos trapezoidales: intersección de trapezoides entre líneas horizontales.
🔗 Algoritmos Clásicos de Grafos: Kruskal, Dijkstra, Boruvka, Floyd-Warshall, Ford-Fulkerson…
🗂️ Organización Secundaria: Ficheros de Índices
📌 ¿Qué son?
Permiten acceso rápido a registros sin tener que leer secuencialmente todo. Requieren un campo clave único para identificar cada registro.
📊 Tipos de Índices
| Tipo | Descripción |
|---|---|
| Agrupado (Clustered) | Datos y registros se almacenan ordenadamente juntos. Ej: guía telefónica. |
| No agrupado (NonClustered) | El índice apunta a otra ubicación donde están los datos. Ej: índice de un libro. |
🔍 Un índice agrupado = solo uno por tabla. Mejora búsquedas ordenadas.
🚀 Acceso a Ficheros Indexados
- Secuencial: Lee según el orden del campo clave.
- Directo: Usa directamente la clave para acceder. Necesita estructuras direccionables.
🧱 Estructura de un Fichero Indexado
- Área de datos: Contiene los registros en orden.
- Área de índices: Tabla con claves y direcciones.
- Área de desbordamiento: Registros extra sin espacio en la zona principal.
📚 Índices más usados:
- ISAM (Indexed Sequential Access Method)
- VSAM (Virtual Storage Access Method)
- ESDS, RRDS, KSDS (este último permite ficheros indexados secuenciales)
🧠 Buenas Prácticas:
- Evitar muchos índices si hay muchos cambios (inserciones/eliminaciones).
- Evitar fragmentación y mantener orden secuencial.
📌 Índice de Agrupamiento: Se define sobre un campo no clave en un fichero ordenado por ese campo.
