METODOS Y CONSEPTOS ESTRUCTURA DE GRAFOS

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