Aquí tienes todo el contenido completo y organizado que puedes copiar y pegar en un
documento (Word, Google Docs) y luego exportarlo como PDF. Está diseñado para que te
sirva de estudio en profundidad y te ayude a sacar un 10/10 en tu evaluación:
1. Fundamentos y Terminología
Grafo G=(V,E)G = (V, E): conjunto de vértices (nodos) y aristas (conexiones)
(geeksforgeeks.org).
Tipos de grafos:
o No dirigido vs dirigido (dígrafo).
o Ponderado (con peso) vs no ponderado.
o Simple, multigrafo (aristas múltiples), con bucles, bipartito, regular, plano,
completo (geeksforgeeks.org, numberanalytics.com).
Propiedades importantes:
o Grado de un vértice = número de aristas incidentes (los bucles cuentan
doble) .
o Vértices aislados (grado = 0), colgantes (grado = 1).
2. Representaciones de Grafos
2.1 Matriz de adyacencia
Matriz n×nn \times n donde aij=1a_{ij} = 1 si existe la arista (o el peso si es
ponderado), o 0 si no (medium.com).
Es simétrica para grafos no dirigidos.
Propiedad útil: al calcular AkA^k, el elemento (i,j)(i,j) da el número de caminos de
longitud k entre ii y jj (ranger.uta.edu).
2.2 Matriz de incidencia
Matriz ∣V∣×∣E∣|V| \times |E|, donde cada columna representa una arista. En grafos no
dirigidos, cada columna tiene dos entradas “1” correspondientes a los extremos de
la arista .
2.3 Lista de adyacencia
Para cada vértice, se mantiene una lista con sus vecinos. Es más eficiente para
grafos dispersos, con complejidad O(∣V∣+∣E∣)O(|V| + |E|) vs la matriz, que es
O(∣V∣2)O(|V|^2) (courses.cs.washington.edu).
3. Caminos, Trayectorias y Conectividad
Caminata (walk): secuencia de vértices/aristas, pueden repetirse.
Trayecto (trail): no repite aristas.
Camino (path): no repite vértices ni aristas.
Circuito o ciclo: camino cerrado.
Tipos especiales:
o Ciclo Euleriano: recorre todas las aristas exactamente una vez.
o Camino Hamiltoniano: recorre todos los vértices exactamente una vez.
Un grafo es conexo si hay un camino entre cualquier par de vértices; en dígrafos se
habla de “fuertemente conexo” (en.wikipedia.org).
4. Árboles y Árboles de Expansión
Un árbol es un grafo conexo sin ciclos. Tiene nn vértices y n−1n-1 aristas, y al
menos dos hojas .
Un árbol de expansión mínima (MST) es un subgrafo con todas las conexiones sin
ciclos y peso total mínimo (tutorialspoint.com).
5. Algoritmos Clave
5.1 Recorridos de grafos
BFS (Breadth-First Search)
Usa cola (FIFO) y explora nivel por nivel.
Útil para encontrar el camino más corto en grafos no ponderados y para detectar
bipartición (jsums.edu).
Complejidad: O(∣V∣+∣E∣)O(|V| + |E|) con listas de adyacencia.
DFS (Depth-First Search)
Usa recursión o pila (LIFO); explora profundamente hasta no poder seguir .
Eficaz para detectar ciclos, componentes conectados, puntos de articulación.
5.2 Caminos más cortos
Dijkstra
Usa cola de prioridad (heap); complejidad O(∣E∣log∣V∣+∣V∣log∣V∣)O(|E|\log|V|+|V|\
Funciona en grafos con pesos no negativos.
log|V|) (pages.cs.wisc.edu, en.wikipedia.org).
Bellman-Ford
Admite pesos negativos y detecta ciclos negativos; complejidad O(∣V∣∣E∣)O(|V||E|) .
Otras variantes:
Floyd-Warshall (O(n3)O(n^3)), Johnson, etc. .
5.3 Árbol de expansión mínima
Kruskal
Complejidad: O(∣E∣log∣E∣)O(|E|\log|E|) .
Ordena aristas por peso y las añade evitando ciclos con estructura union-find.
Prim
Parte de un vértice y añade sucesivamente la arista más barata que conecta a un
vértice nuevo.
Usa cola de prioridad; complejidad similar a Kruskal .
6. Ejercicios con Matrices y Tablas
Ejemplo: Grafo completo de 3 vértices V={1,2,3}V = \{1,2,3\}
Matriz de adyacencia:
12 3
1 011
2 101
12 3
3 110
Matriz de incidencia:
V\ e1=(1- e2=(2- e3=(3-
E 2) 3) 1)
1 1 0 1
2 1 1 0
3 0 1 1
Resumen de pasos:
Paso Adyacencia Incidencia
Filas: vértices; Columnas:
Índices Vértices ↔ filas/col.
aristas
Inicializació
Zeros Zeros
n
bij=1b_{ij}=1 si el vértice i
Llenado aij=1a_{ij}=1 si hay arista
incide en la arista j
Cada columna = 2 unos en
Propiedades Simétrica si no dirigido
grafos no dirigidos
Cálculos Caminos con potencias de A,
Grados por suma de fila
extra grados por suma de fila
7. Consejos de Estudio
1. Dibuja grafos y rellena matrices a mano para afianzar los conceptos.
2. Aplica BFS/DFS para verificar conectividad, componentes, ciclos.
3. Usa Kruskal/Prim para practicar árboles de expansión sobre ejemplos.
4. Ejecuta Dijkstra/Bellman-Ford en grafos con y sin pesos negativos.
5. Resuelve ejercicios variados: grafos simples, dirigidos, ponderados.
6. Usa diagramas esquemáticos y revisa soluciones tipo PAU.
7. Divide sesiones de estudio en bloques de: teoría, ejemplos, ejercicios.
8. Recursos Recomendados
GeeksforGeeks: Introducción a grafos con definiciones y ejemplos
(geeksforgeeks.org, numberanalytics.com, tutorialspoint.com).
Number Analytics: guía sobre algoritmos básicos (BFS, DFS, MST y caminos
cortos) (numberanalytics.com).
PDF “Graph Theory Basics” del curso CSE5311: resumen de algorítmica, MST,
caminos cortos (ranger.uta.edu).
Tutorialspoint: implementación y pseudocódigo de algoritmos clave
(tutorialspoint.com).
✅ Ahora solo copia todo esto, pégalo en tu editor,
ajusta el formato (negritas, tablas, etc.), y ¡exporta a
PDF!
Si deseas, puedo ayudarte con formato de tablas o esquemas visuales adicionales antes de
generar.
