Algoritmia

UNIVERSIDAD CATÓLICA DE SANTA MARIA
P. P. INGENIERÍA SISTEMAS
LABORATORIO DE ALGORITMIA Y ESTRUCTURA DE DATOS II
GRAFOS
I OBJETIVOS
Explicar el TAD Grafo.
Implementar el TAD Grafo.
Utilizar el TAD Grafo para la resolución de problemas.
II TEMAS
TAD Grafo
III MARCO TEÓRICO
INTRODUCCIÓN
Los grafos sirven para representar relaciones arbitrarias (no necesariamente jerárquicas) entreobjetos de datos
Sesión
3
Mgter. Juan Pablo Apaza Condori 2
GRAFOS: APLICACIONES
Circuitos electrónicos
Tarjetas impresas
Circuitos integrados
Redes de transporte
Autopistas
Vuelos
Redes de ordenadores
LANs
Internet
Web
Bases de datos
Diagramas entidad/relación
Aplicación Vértices Aristas
Redes de computadoras Computadoras y equipos de
telecomunicaciones
Medios de comunicaciónSistemas de transporte Ciudades, puertos,
aeropuertos, etc.
Autopistas, rutas de
navegación, etc.
Redes eléctricas Subestaciones Conductores
Red telefónica Centrales telefónicas Troncales
Distribución de fluidos Estaciones de bombeo Tuberías
Mgter. Juan Pablo Apaza Condori 3
Mgter. Juan Pablo Apaza Condori 4
GRAFOS: DEFINICIÒN
Un grafo G = (V, A) agrupa entes conceptuales y sus relaciones.Conjunto de vértices o nodos V = {1,4,5,7,9}
Conjunto de arcos A = { (1,4), (5,1), (7,9), (7,5), (4,9)} son las relaciones entre nodos.
Un arco o arista está formado por un par de nodos u y v, y se representa por (u,v)
Un grafo no dirigido es aquel que las aristas están formados por pares de nodos no
ordenados, se representa u v.
O grafo en el que las aristas están formadas por pares denodos no ordenados, no apuntados.
Un grafo es dirigido si los pares de nodos que forman los arcos son ordenados y se
representan u ® v.
Grafo dirigido o dígrafo, los pares de nodos que forman los arcos son ordenados.
Grafo valorado o ponderado: Grafo cuyos arcos tienen asociados un peso o coste.
Cuando una relación entre dos nodos tiene asociada una magnitud denominada factor de
peso
Si (u,v)es una arista en A(G), entonces u y v se dice que son vértices adyacentes.
Dos vértices son adyacentes si existe un arco que los una (para grafos dirigidos: “adyacentes a”)
Mgter. Juan Pablo Apaza Condori 5
GRAFOS: NO DIRIGIDOS Y DIRIGIDOS
GRAFO NO DIRIGIDO
V(G1) = {a,b,c,d}
A(G1) = {(a,b),(a,d),(b,c),(b,d)}
GRAFO DIRIGIDO
V(G2) = {1,3,5,7,9}
A(G2) = {(1,3),(3,1),(9,1), (3,5),(5,7)}Mgter. Juan Pablo Apaza Condori 6
GRADO DE UN NODO
En un grafo no dirigido
Grado de un nodo u = nº de aristas que contienen a u
En un grafo dirigido
Grado de entrada de u = nº de arcos que llegan a u
Grado de salida de u = nº de arcos que salen de u
GRAFOS CONEXOS
Para un grafo no dirigido, es conexo si existe un camino entre cualquier par de nodos que
forman el grafo.
EJEMPLOS:
GRAFOSFUERTEMENTE CONEXOS
Para un grafo dirigido, es fuertemente conexo si existe un camino desde un vértice a
cualquier otro.
Grafo no conexo con dos
componentes conexas
Grafo conexo
Mgter. Juan Pablo Apaza Condori 7
GRAFOS: CAMINOS
Un camino P de longitud n en el grafo G desde 0 u a n u es la secuencia de n+1 vértices
P (u , u , ..., u ) 0 1 n = tal que (ui ,ui+1 ) son arcos de G para 0 £ i £ n .Un camino es simple si todos los nodos que forman el camino son distintos, pudiendo ser iguales
los extremos del camino
Ejemplo:
P1 es simple
P2 no es simple
Mgter. Juan Pablo Apaza Condori 8
GRAFOS: CICLOS Y BUCLES
Un ciclo es un camino simple cerrado con u = un 0 , compuesto al menos por tres nodos
Un ciclo es simple si todos sus vértices y arcos son distintos
Un arco que va desde unvértice a sí mismo (u,u )se denomina bucle
Ejemplo
C1 es un ciclo simple
C2 es un ciclo no simple
Mgter. Juan Pablo Apaza Condori 9
GRAFOS: REPRESENTACIÓN CON MATRIZ DE ADYACENCIA
Sea G = (V, A) un grafo de n nodos, suponemos que los nodos V = {u1,..., un} están
ordenados y podemos representarlos por sus ordinales {1,2,...,n}.
La representación de los arcos se hace con una matriz A de nxn...