UNIVERSIDAD PARA EL
DESARROLLO ANDINO -
UDEA
SEMANA 15:
DEFINICION E IMPLEMENTACION DE
GRAFOS DEL TDA (TAD), GRAFOS Y SU
REPRESENTACION MATRICIAL DE GRAFOS
ING. JHAN CARLO ALVARADO PEREZ
Grafos
Un grafo es una estructura de datos que consiste
en un conjunto de nodos (o vértices) y un conjunto
de aristas (o arcos) que conectan pares de nodos.
Los grafos se utilizan para modelar relaciones entre
objetos en diversas aplicaciones, como redes
sociales, mapas de rutas, redes de computadoras,
entre otros.
Son otra estructura no lineal y que tiene gran
numero de aplicaciones. El estudio del análisis de
grafos a interesado a los matemáticos durante
varios siglos y representa una parte importante de
la teoría combinatoria en matemáticas. Aunque la
teoría de grafos es compleja y amplia, en esta
sección se realizara una introducción a la teoría de
grafos y a los algoritmos que permiten su solución
por computadora.
Componentes de un Grafo
1. Nodos (Vértices): Son los
elementos individuales del grafo.
2. Aristas (Arcos): Son las
conexiones entre los nodos.
Pueden ser:
1. Dirigidas: La relación tiene una
dirección (de un nodo a otro).
2. No dirigidas: La relación no tiene
dirección (la conexión es
bidireccional).
Tipos de Grafos
• Grafo Simple: Sin bucles ni aristas
múltiples.
• Grafo Dirigido: Las aristas tienen una
dirección.
• Grafo No Dirigido: Las aristas no tienen
dirección.
• Grafo Ponderado: Las aristas tienen un
peso o costo asociado.
• Grafo Conexo: Hay un camino entre cada
par de nodos.
• Grafo Completo: Cada par de nodos está
conectado por una arista.
EJEMPLO 01
