Grafos
Definición
• Los grafos son estructuras de datos no lineales donde cada componente
puede tener uno o más predecesores y sucesores.
• No existe jerarquía padre-hijo.
• No hay un orden consecutivo para las operaciones a realizar.
Elementos
• Vértices (V): son los nodos.
• Son elementos individuales en el grafo. Cada vértice puede representar entidades como
personas, lugares, o cualquier objeto que estemos modelando.
• Aristas (A): arcos que conectan un vértice con otro.
• Estas aristas pueden ser direccionales o no direccionales, dependiendo del tipo de relación
que queremos representar.
Grafo (V, A)
Conceptos relacionados
• Grado de un vértice grado(v): es el número de aristas que contienen a v, es decir,
que tienen a v como extremo. Si grado(v)=0, se dice que v es un nodo aislado.
• Lazo o bucle: Es una arista que conecta a un vértice consigo mismo, a=(u,u)
• Camino (P): Un camino P de longitud n se define como la secuencia de n vértices
que deben seguir para llegar del vértice origen v1 al vértice destino vn. P=(v1,…, vn)
• Camino cerrado: Un camino P es cerrado si el primero y último vértice son
iguales, es decir v1= vn
• Camino simple: El camino es simple si todos sus nodos son distintos, con
excepción del primero y el último, que pueden ser iguales; es decir, P es simple
si v1, v2 , … son distintos
Conceptos relacionados
• Ciclo: Es un camino simple
cerrado de longitud 3 o mayor.
Un ciclo de longitud k se llama k-
ciclo.
• Gráfica conexa: Se dice que una
gráfica es conexa si existe un
camino simple entre
cualesquiera dos de sus nodos.
Conceptos relacionados
• Gráfica árbol: cuando G es una
gráfica conexa sin ciclos.
• Gráfica completa: cuando cada
vértice v de G es adyacente a todos
los demás vértices de G. Una gráfica
completa de n vértices tendrá n(n-1)/2
aristas.
Conceptos aplicados
• Todos los vértices tienen grado 4
• Un camino P para llegar del vértice A al
D puede ser:
• ABCD
• ED
• AD
• ACDA, es camino cerrado, camino
simple y ciclo.
• Es una gráfica conexa porque todos los
nodos tienen al menos un camino a
otro nodo.
Ejemplos
En este grafo se presentan las capitales sudamericanas y la conexión entre ellas.
Vértices Ciudades
Aristas Distancias entre ciudades (carreteras)
Grafos dirigidos
Grafos dirigidos = dígrafo
• Lo que se estudian son
grafos dirigidos.
• Son estructuras de datos
• a empieza en u y termina en v.
abstractas. • u es el origen o punto inicial de a, y v es el
destino o punto terminal de a.
• Se representan con: • u es el predecesor de v y v es un sucesor o
• Matrices y listas de vecino de u.
• u es adyacente hacia v y v es adyacente desde
adyacencia. u.
• Se observa que se tiene la dirección indicada
• Árboles o listas. por una flecha.
Matriz de adyacencia
• Se trata de una matriz cuadrada de n filas por n columnas (siendo n el
número de vértices del grafo).
• Para efectos de construir la matriz de adyacencia,
• cada elemento a{i,j} vale {{1}} cuando haya una arista que una los vértices i y j.
En caso contrario, el elemento a{i, j} vale 0.
Ejemplo 1
Ejemplo
1 2 3 4 5
1 0 1 1 1 0
2 1 0 0 0 1
3 1 0 0 1 1
4 1 0 1 0 0
5 0 1 1 0 1
Ejemplo 2
Ejemplo
a e i o u
a 0 1 1 0 0
e 0 0 0 1 0
i 0 0 0 0 1
o 0 0 1 0 0
u 1 0 0 1 0
Ejercicios para entregar
1. Obtenga la matriz de adyacencia de los siguientes grafos.
Ejercicios
• 2. Dado el código presentado en el libro
• Hernández Bejarano, M. y Baquero Rey, L. E. (2022). Estructuras de datos:
fundamentación práctica: (1 ed.). Madrid, RA-MA Editorial. Recuperado de
[Link]
• Realice las modificaciones necesarias para mostrar la tabla de adyacencia del
ejemplo 2 y el ejercicio 1.
Ejercicios
• 3. Para cada uno de los grafos de la figura indique:
• Aquellas que son gráficas conectadas.
• Aquellas que son gráficas cíclicas.
• Aquellas que son gráficas conexas.
• Aquellas que son gráficas completas.
• Todos los pares de vértices adyacentes.
• Un camino entre los vértices a y c, si es posible
• Un camino cerrado entre cualquier par de vértices, si es posible.
• Un camino simple entre cualquier par de vértices, si es posible.
• El grado de cada vértice
