Teoría de grafos
Matemáticas: Aplicaciones e Interpretación
Conceptos clave
- Un grafo es un conjunto de vértices unidos por aristas.
- El grado de un vértice es cuántas aristas salen de él.
- Un grafo es ponderado si sus aristas tienen pesos (distancias, costes).
- Es dirigido si las aristas tienen sentido (flechas).
Matriz de adyacenciaNS
- Fila , columna = número de aristas de a .
- En grafo no dirigido la matriz es simétrica.
- La potencia cuenta los caminos de longitud entre vértices.
- Un bucle (arista a sí mismo) añade en la diagonal.
Árbol de expansión mínimaNS
- Conecta todos los vértices con el peso total mínimo, sin ciclos.
- Kruskal: añade la arista más barata que no forme ciclo, y repite.
- Prim: crece desde un vértice tomando siempre la arista más barata al árbol.
- Con vértices, el árbol tiene aristas.
Camino más cortoNS
- El algoritmo de Dijkstra halla la ruta de menor peso entre dos vértices.
- Etiqueta cada vértice con su distancia provisional y ve fijando la menor.
- Actualiza las distancias de los vecinos al fijar cada vértice.
- Sirve para rutas más rápidas o más baratas.
Recorridos: Euler y HamiltonNS
- Euleriano: recorre cada arista una sola vez.
- Existe un circuito euleriano si todos los vértices tienen grado par.
- Hamiltoniano: pasa por cada vértice una sola vez.
- El problema del viajante busca el circuito hamiltoniano más barato.
Cartero chinoNS
- Busca la ruta más corta que recorre todas las aristas y vuelve al inicio.
- Si hay vértices de grado impar, hay que repetir algunas aristas.
- Empareja los vértices impares con el menor coste extra total.
- La respuesta = suma de todas las aristas + repeticiones mínimas.
Ejemplo resueltoNS
- Problema: un grafo tiene grados . ¿Admite circuito euleriano?
- Un circuito euleriano existe si todos los grados son pares.
- Aquí los grados son : todos pares.
- Por tanto sí existe un circuito euleriano.
En la calculadora — CASIO fx-CG50
Introducir la matriz de adyacencia:
menu›Run-Matrix›OPTN›MAT/VCT›Mat
Potencia de la matriz (caminos): escribe y usa
Mat A
^
Sumar matrices de pesos: opera en
Run-Matrix
Leer una entrada concreta:
Mat A[i,j]
Términos IB
- Caminos de longitud n: eleva la matriz de adyacencia a la potencia n.
- Árbol de expansión mínima: aplica Kruskal o Prim.
- Camino más corto: usa el algoritmo de Dijkstra.
- Circuito euleriano/hamiltoniano: revisa grados (Euler) o vértices (Hamilton).