Upload
junior-vallenilla
View
60
Download
0
Embed Size (px)
Citation preview
República Bolivariana de VenezuelaMinisterio del Poder Popular Para la Educación SuperiorInstituto Universitario Politécnico “Santiago Mariño”Barcelona - Edo. Anzoátegui
METODOS Y CONSEPTOSESTRUCTURAS DISCRETAS Y GRAFOS
SECCION: SV
BACHILLER: JESUS VALLENILLAC.I: 18,569,234
BARCELONA , JUNIO DEL 2016
¿Qué es un Grafo?
• Es un conjunto de: puntos (NODOS o VÉRTICES) unidos por líneas (ARCOS o ARISTAS)
¿Por qué se estudian Grafos?
• Porque permiten estudiar interrelaciones entre elementos que interactúan unos con otros• Dado un escenario donde ciertos objetos se relacionan se puede “modelar el grafo” y luego aplicar algoritmos para resolver diversos problemas• Son aplicables en:
Ingeniería de SistemasModelado de Redes Ingeniería Industrial, ElectrónicaQuímicaGeografía, etc.
¿Qué podemos representar con un Grafo?
• Red de Computadoras• Conexiones de vuelo de una aereolínea• Carreteras que unen ciudades• Actividades de un proyecto• Circuitos electrónicos• Representación de un mapa
Impresora
Modem
PC2
Servidor
PC1
Practicamente cualquier problema puede representarse mediante un grafo
Recorrer cada carreteraexactamente una vez y regresaral punto de partida
Recorrer cada ciudad una vezy regresar a la ciudad de origeny todo al menor costo posible
Encontrar el camino más cortoentre 2 cuidades cualesquiera
Ejemplo de Aplicación de los Grafos
Grafo – Definición formal
Un grafo G = (V,E)
V, el conjunto de vértices o nodosV={v1, v2, ..vn}Representan los objetos
E, el conjunto de arcos o aristasRepresentan las relaciones
E ={vivj, vmvn, ..}
V = {1, 4, 5, 7, 9}
E= {(1,4), (4,9), (9,7), (7,5), (5,1), (4,1), (1,5), (5,7), (7, 9), (9,4)}
1 4
5
7 9
Vértices Adyacentes: 2 vértices unidos por un arco
Grado de un Grafo
• Grado de un NODO: Es el # de arcos que inciden en un vértice• Caso especial (lazo): se considera 2
• Grado de un GRAFO: Suma de los grados de los vértices. • Teorema de Grado de un GRAFO: Suma de grados de vértices
equivale al doble del número de arcos.
C E
DF
H
Grado (D) = 3 Grado (F) = 3Grado (H) = 3 Grado (C) = 3Grado (E) = 4
Grado del Grafo = 16 = 2 * 8 arcos
Tipos de Grafos
• Grafo Regular• Todos los vértices tienen el mismo grado• Si el grado es k, el grafo es k-regular
x
u
y zGrafo 3 - regular
• Grafo Completo• Tiene una arista entre cualquier par de vértices
a b
c d
Grafo completo
a b
cd
e
Grafo No completo
Tipos de Grafos
• Grafo Bipartito• “Bipartito” significa que tiene 2 partes• G= { V1 u V2, E}• Sus vértices son la unión de dos grupos de vértices bajos las siguientes condiciones:
• V1 y V2 son conjuntos disjuntos• Cada arista del Grafo une un vértice de V1 con uno de V2• No existen aristas uniendo vértices del mismos conjunto V1 o V2
a b
d e
c
Grafos Bipartitos
a b
c
Tipos de Grafos
• Mulitgrafo • Es un grafo que tiene arcos múltiples (paralelos) o lazos
• Grafo Simple• Es un grafo o digrafo que no tiene bucles y que no es un multigrafo
x u
y zGrafo simple
x u
y z
Multigrafo
Lazo o bucle
Arcos múltiples o paralelos
Tipos de Grafos (dirección)
• Grafos dirigidos o DigrafosSi los pares de nodos que forman
arcosson ordenados, de tal forma que el arco se puede recorrer en un solo sentido. Ej.: (u->v)
• Grafos no dirigidos• Si los pares de nodos de los arcosno son ordenadosEl arco se puede recorrer en ambos
sentidos Ej.: u-v
C E
DF
HV = {C, D, E, F, H} E= {(E,H), (H,E), (E,C), (C,D), (D,F)}
1 4
5
7 9
Grado de un Digrafo
E
L
B
M
P
• En un grafo dirigido los arcos son pares ordenados.
• Implica que (u,v) ≠ (v,u)• Las líneas se convierten en flechas• El grado de entrada de un nodo es el número de arcos entrantes• El grado de salida de un nodo es el número de arcos salientes
Grafos ponderados
• Costo o Factor de Peso• Valor que se puede asociar con un arco• Depende de lo que el grafo represente• Si los arcos de un grafo tienen un costo: Grafo valorado o ponderado
Grafo Dirigido con Costo
Grafo No Dirigido con Costo
a b
c d
a b
c d
20
3025
15
40 40
a b
c d
a b
c d
20
3025
15
Conectividad
• Grafo Conexo• Existe un camino entre cualquier par de nodos
3
9
5
72
Grafo inconexo
Grafo conexo
Grafo conexo
GRACIAS POR SU ATENCION