Grafos - Parte 1

Vista previa del material en texto

Algoritmos y Estructuras de 
Datos
Departamento de Informática
LAS - TUP
Unidad N° 6: Grafos - Parte I
Temario
1. Introducción a conceptos de grafos.
2. Tipo abstracto de Datos.
3. Implementación.
4. Utilización.
Introducción
El origen de la palabra grafo es griego y su significado es ”trazar”. 
Cotidianamente, se usan grafos para representar:
● Jerarquía: Estructura de una organización.
● Redes: viales, eléctricas, aéreas, informáticas, sociales, etc.
Los grafos tienen un amplio campo de aplicaciones. Debido a esto es que 
diferentes disciplinas como las Ciencias de la computación, las Matemáticas 
y la Ingeniería entre otras, se han dedicado a su estudio.
Introducción
La situación se debe poder representar mediante un conjunto de nodos y un 
conjunto de líneas. 
Definición
Un grafo está formado por un conjunto de nodos (vértices) y un conjunto de líneas 
llamadas aristas (arcos) que conectan a los diferentes nodos.
Formalmente, un grafo se define: G=(V,E) o G=(V, A)
donde:
V(G): es un conjunto finito de vértices o nodos.
E(G) o A(G): es un conjunto de aristas (edges) o arcos (arcs).
Definición
Un grafo está formado por un conjunto de nodos (vértices) y un conjunto de líneas 
llamadas aristas (arcos) que conectan a los diferentes nodos.
Formalmente, un grafo se define: G=(V,E) o G=(V, A)
donde:
V(G): es un conjunto finito no vacío de vértices o nodos.
E(G) o A(G): es un conjunto de aristas (edges) o arcos (arcs).
¿Que es E(G) o A(G)? ¿Cuál es la diferencia?
Definición
Dado un grafo G=(V,A), en el que V es un conjunto de elementos llamados 
vértices:
Siendo x,y ∈ V:
❖ Puede ocurrir que (x,y) ∈ A. Si es así, los vértices x e y están relacionados. 
Es decir, existe una arista que une x con y.
❖ Pero también puede ocurrir que (x,y) ∉ A. En tal caso, dichos vértices no 
están relacionados.
Es decir, NO existe una arista que une x con y.
Definición
Dado un grafo G=(V,A), en el que V es un conjunto de elementos llamados 
vértices:
❖ El grafo es no dirigido si A una familia de pares no ordenados de vértices 
(aristas). 
Es decir que NO tienen asociado asociada una dirección.
❖ El grafo es dirigido o digrafo si A una familia de pares ordenados de 
vértices (arcos). 
Es decir que SI tienen asociado asociada una dirección.
Ejemplo
V(G)=
A(G)=
Ejemplo
• Ejemplo de grafo dirigido: Grafo de herencia de interfaces en Java. 
• Ejemplo de grafo dirigido: Grafo donde los nodos son esquinas de una 
ciudad y los arcos son cuadras de una mano. 
• Ejemplo de grafo dirigido: Grafo donde los nodos son números enteros y 
los arcos indican qué número divide a otro. E.g. como “2 divide a 6”, 
habrá un arco (2,6). 
• Ejemplo de grafo no dirigido: Grafo de colaboración entre coautores 
científicos. 
• Ejemplo de grafo no dirigido: Grafo donde los nodos son esquinas de un 
pueblo chico y los arcos son calles doble mano. 
Propiedades
Orden: Se llama orden de G al cardinal de vértices | V |. 
Tamaño: Es el número de aristas del grafo.
Adyacencia: dos aristas son adyacentes si tienen un vértice en común. Dos 
vértices son adyacentes si una arista los une.
Ponderación: al grafo se agrega una función que a cada arista le asocia un valor 
(peso). 
Etiquetado: es la distinción que se hace a los vértices y/o aristas mediante una 
etiqueta que los identifica unívocamente
Propiedades
Grado: 
● Grado de entrada de un vértice es el número de aristas(arcos) que inciden en el vértice v. 
● Grado de salida de un vértice es el número de aristas(arcos) que emergen del vértice v. 
● Grado de un vértice (grafo dirigido) es la suma de los grados de entrada y salida del vértice 
v. 
● Grado de un vértice (grafo no dirigido) es la suma de los grados de entrada del vértice v. 
● El grado de un grafo es el máximo grado de todos sus vértices.
Propiedades
Grado: El grado de un vértice u es el número de vértices adyacentes a u. Para un 
grafo dirigido, el grado de salida de un vértice u es el número de vértices adyacentes 
desde u, mientras que el grado de entrada de un vértice u es el número de vértices 
adyacentes a u. 
Propiedades
Grado: 
Para el siguiente grafo dirigido, el Grado+(2)=2, el Grado−(2)=1, Grado(2)=3.
Propiedades
Camino: de longitud q es una secuencia de q arcos que conectan dos vértices
P = {u1, u2, . . . , uq}, con u1 = (i0, i1), u2 = (i1, i2), . . . , uq = (iq−1, iq)
El vértice i0 es el vértice inicial del camino P y el vértice iq el final.
En otras palabras, un camino es una cadena cuyos arcos tienen una misma 
dirección. La distinción entre cadena y camino, es que el primero se aplica a 
grafos, mientras que el segundo a grafos dirigidos (digrafos).
Longitud de camino: El número de arcos que lo forman
Propiedades
Un camino que conecta los vértices 2 y 5 es la 
secuencia de arcos P1={(2,3),(3,4),(4,5)}. 
P2={(2,1),(1,5)} pues el arco (1,5) no existe.
Camino simple: es un camino en el que todos los 
vértices son distintos. El camino P1={(2,3),(3,4),(4,5)} 
es simple, mientras que el camino 
P2={(2,1),(1,2),(2,3),(3,5)} no lo es. 
Ciclo: es una sucesión de aristas adyacentes, donde no 
se recorre dos veces la misma arista y donde se 
regresa al vértice inicial.
Propiedades
Camino hamiltoniano: es un sucesión de arcos que visita TODOS los vértices 
del grafo una sola vez. 
Ciclo hamiltoniano: es un camino hamiltoniano tal que el vértice final del camino 
es adyacente al vértice inicial. 
Nota: se entiende entonces que un camino (o cadena) es ”más chico” que un 
camino hamiltoniano (o ciclo hamiltoniano) en cuanto a que no incluye a todos los 
vértices del grafo.
Propiedades
 Un ciclo es (1,3),(3,5),(5,1). 
Un camino hamiltoniano es P1={(1,2),(2,3),(3,4),(4,5)}.
Un ciclo hamiltoniano es P2={(1,2),(2,3),(3,4),(4,5),(5,1)}. 
Tipos de grafos
Grafo nulo: es aquel que no tiene vértices ni aristas.
Grafo vacío(libre): si A={}. Es decir, si no tiene aristas.
Grafo completo. Un grafo completo tiene cada par de vértices unido por una arista. 
Se denota por Kn al grafo completo de n vértices.
Grafo conexo: si para cualesquiera par de vértices (i,j), existe una cadena(camino) 
que los une.
Grafo regular: Aquel con el mismo grado en todos los vértices. Si ese grado es k lo 
llamaremos k-regular.
p-Grafo: es un grafo que no tiene más de p arcos entre dos cualesquiera vértices i,j.
Representación
Un grafo puede representarse de varias formas equivalentes, poniendo de 
manifiesto determinadas caracter´ısticas. Entre ellas:
● Simbólicamente, es decir como un par (V,A) donde V es un conjunto de 
vértices y A un conjunto de aristas entre pares de vértices.
● Gráficamente, mediante un diagrama formado por un conjunto de puntos 
(uno por cada vértice de V) y un conjunto de líneas (una por cada arista de 
A).
● Numéricamente.
Representación
Existen dos técnicas para representar a los grafos de manera numérica:
❖ Matriz de adyacencia (usando arreglos).
❖ Lista de adyacencia (usando listas enlazadas).
Representación - Matriz de adyacencia
Sea G=(V,A) un grafo de orden n, suponemos que los vértices de V={v1; v2; : : : ; vn} 
están ordenados y pueden ser representados por los valores ordinales {1,2,. . . ,n}.
En tanto, la representación de los arcos(aristas) se realiza con una matriz A de orden 
n de elementos aij tal que eij = 1 si existe el arco (i,j) y 0 c.o.c.
La matriz A se denomina matriz de adyacencia del grafo G.
Representación - Matriz de adyacencia
Sea G=(V,A) un grafo de orden n, suponemos que los vértices de V={v1; v2; : : : ; vn} 
están ordenados y pueden ser representados por los valores ordinales {1,2,. . . ,n}.
En tanto, la representación de los arcos(aristas) se realiza con una matriz A de orden 
n de elementos aij tal que eij = 1 si existe el arco (i,j) y 0 c.o.c.
La matriz A se denomina matriz de adyacencia del grafo G.
¿Características de la matriz?
Representación - Matriz de adyacencia
La matriz A tiene toda la información topológica del grafo.
Por lo tanto, la matriz caracteriza al grafo. Es importantetener en cuenta que:
● La matriz de adyacencia de un grafo es simétrica (no así en un digrafo).
● La matriz de adyacencia de un grafo completo debe tener 1 en toda la matriz 
excepto en la diagonal.
● Un grafo con un vértice i sin conexión con los demás vértices (grafo conexo), 
tiene una matriz con la fila y columna i con elementos nulos.
Representación - Matriz de adyacencia
¿Desventaja?
Representación - Lista de adyacencia
La lista de adyacencia para un vértice i es una lista, en algún orden, de todos los 
vértices adyacentes a i.
Representación - Lista de adyacencia
Se puede representar el grafo G por medio de un arreglo tal que cada elemento i-
ésimo del mismo tiene una referencia a la lista de adyacencia del vértice i.
La representación de grafo con lista de adyacencia requiere un espacio 
proporcional a la suma del cardinal de vértices más el número de arcos. Una 
desventaja con esta representación es que puede llevar un tiempo O(n) saber si 
dos vértices i y j son adyacentes.
Representación - Lista de adyacencia
Ejemplo:
Conclusiones
❖ Son contenedores no lineales con un amplio campo de aplicaciones.
❖ En cuanto a su representación en memoria, se pueden utilizar arreglos o 
listas enlazadas.
❖ Además de manipularlos, resolveremos algunos problemas clásicos.