1

TEORIA DE GRAFOS TEORIA DE GRAFOS IntroducciónIntroducción

Qué es un Grafo? En Matemática y ciencias de la computación, un

grafo (del griego grafos), es una imagen que permiten expresar de una forma visual muy sencilla y efectiva las relaciones que se dan entre elementos de muy diversa índole. Un grafo está formado por dos conjuntos:

Un conjunto V de puntos llamados vértices o nodos y un conjunto de pares de vértices que se llaman aristas o arcos y que indican qué nodos están relacionados.

De una manera más informal podemos decir que un grafo es un conjunto de nodos con enlaces entre ellos, denominados aristas o arcos

Aplicaciones Entre las múltiples aplicaciones que tienen

estas estructuras podemos mencionar algunas que sirven para modelar situaciones como:

sistemas de aeropuertos Flujo de Tráfico Contactos

Responder a las preguntas: ¿Qué tiempo es más corto?, ¿Cuándo es más barato?,¿Qué tarea debo hacer primero?. ¿Están todas las componentes conectadas?.

Cómo se representa un Grafo?

VERTICESO NODOSARISTAS

O ARCOS

5

Concepto y representación Concepto y representación MatemáticaMatemática

Un grafo Un grafo GG es un par es un par (V,E)(V,E) donde: donde: V ={vV ={v11,…,v,…,vnn}} es un conjunto de vértices es un conjunto de vértices

E = {eE = {e11,…,e,…,emm}} es un conjunto de aristas, es un conjunto de aristas,

con cada con cada eekk {v {vii, v, vjj}}, con , con vvii, v, vj j V V, , vvii ≠ v ≠ vjj

Los vértices se representan como puntos y las Los vértices se representan como puntos y las aristas como líneas entre vérticesaristas como líneas entre vértices

Ejemplo:Ejemplo: G = (V,E)G = (V,E) V = {a,b,c,d }V = {a,b,c,d } E = {{a,b}, {b,c}, {a,c}, {a,d}, {d,b} }E = {{a,b}, {b,c}, {a,c}, {a,d}, {d,b} }

Proponer otro recorrido:Proponer otro recorrido:

6

UtilidadesUtilidades

Red de ordenadoresRed de ordenadores

Red de Carreteras

Madrid

Murcia

Valencia

GranadaSevilla

Cádiz

Badajoz

Vigo

Coruña

GeronaBarcelona

Zaragoza

BilbaoOviedo

Valladolid

Jaén

251

150

403

241

349

191

99

125

356

304

395

455171

280

193

324

325296 10

0

335

278242256

Albacete

Cuando las aristas tienen un valor numérico asociado se llama Cuando las aristas tienen un valor numérico asociado se llama de de grafos valoradosgrafos valorados: Al valor numérico asociado se le llama: Al valor numérico asociado se le llamacostecoste de la arista de la arista

8

Tipos de grafosTipos de grafos Es importante recordar que un mismo grafo puede Es importante recordar que un mismo grafo puede

tener diferentes representaciones gráficastener diferentes representaciones gráficas EjemploEjemplo::

Dos representaciones del mismo grafoDos representaciones del mismo grafoG = ({a,b,c,d,e,f},{{a,b},{a,e},{a,f}{e,f},{b,c},G = ({a,b,c,d,e,f},{{a,b},{a,e},{a,f}{e,f},{b,c},

{c,d},{e,d},{d,f}}){c,d},{e,d},{d,f}})¿Se te ocurre otra representación?¿Se te ocurre otra representación?

9

Tipos de GrafosTipos de Grafos

Si el orden influye en la aristas se habla de Si el orden influye en la aristas se habla de grafos dirigidosgrafos dirigidos::

En este caso a las aristas se les llama En este caso a las aristas se les llama arcosarcos y y se representan como pares para indicar el se representan como pares para indicar el orden:orden: V = { a,b,c,d,e}V = { a,b,c,d,e} E ={(e,a), (a,b), (b,a), (d,a), (c,d), (d,c),(b,c),E ={(e,a), (a,b), (b,a), (d,a), (c,d), (d,c),(b,c),

(c,b) }(c,b) }

10

Tipos de GrafosTipos de Grafos

Si se permite que haya más de una Si se permite que haya más de una arista se habla de arista se habla de multigrafosmultigrafos::

Conclusiones