Grafos

INTRODUCCIÓN:LOS SIETE PUENTES DE KÖNIGSBERG

1

• La ciudad de Königsberg está recorrida por el río Pregel que crea dos islas.

El matemático Leonard Euler se preguntó : ¿Se puede recorrer toda la

ciudad pasando una sola vez por todos los puentes y volver al lugar de

partida?. Ésta es la pregunta que origino al problema de los puentes de

Königsberg y que dio inicio a la Teoría de Grafos

La solución de Euler. El famoso matemático

abstrajo los detalles de la forma de la ciudad y sus

puentes para quedarse con la conectividad, dando

lugar a una de las primeras gráficas.

Euler represento mediante puntos a los lugares y

mediante arcos a cada puente

2

A

B

D

C

Llamó orden (grado) de cada vértice al número de arcos que

se reunían en él y se percató que el orden de cada vértice

visitado en un recorrido sin saltos debía ser par (para poder

entrar por una arista y salir por otra) excepto para dos

puntos de la gráfica; aquellos donde se inicia y donde se

acaba el recorrido, los que han de tener orden impar. Dedujo

que si el vértice donde se inicia y se acaba el recorrido

coinciden entonces todos los vértices debían ser de

orden par.

Solución del Problema de los Puentes de Königsberg :

Dado que el orden de todos los vértices es impar,

entonces es imposible recorrer todas las aristas (puentes)

pasando una sola vez por cada uno de ellos y volver al punto

de partida

3

DEFINICIONES: GRAFOS NO DIRIGIDOS Un grafo no dirigido G (o simplemente Grafo)

consta de un conjunto finito V de objetos llamados

vértices o nodos, un conjunto finito E de objetos

llamados aristas o arcos y una función que

asigna a cada arista eE un par no ordenado de

vértices {v,w}, donde v , w V.

Notación: G = (V , E, )

(e) ={v,w} significa que la función asigna a la arista e

los vértices v y w . También se dice que e incide en v

y w o que v y w son adyacentes a través de e

4

Los grafos son usados para

registrar información acerca

de relaciones o conexiones. Una arista entre vi y vj

indica una conexión entre los objetos vi y vj , y

ésta es la información más importante, y por

lo general la misma gráfica

puede representarse con

distintas apariencias

5Enlace motivador:

http://www.mathsmovies.com/curso/altas_capacidades/grafos.htm

http://www.mathsmovies.com/curso/altas_capacidades/grafos.htm

¿CÓMO SE REPRESENTA UN GRAFO?

6

Vértices o nodos

Aristas o arcosv2

v1

v3

v4v5

v6

v7

v8

v9

v10

e1e2

e3

e4

e5

e6e7

e8

e9

e10

e11

e12

e13

e14e15

La funcion esta dada por (e1) ={v1, v9}(e2) ={v1, v2}

::

(e15) ={v10, v2}

EJEMPLO

7

V = {v1,v2,v3,v4}

E={e1, e2, e3, e4, e5}

dada por

(e1)= (e5)={v1,v2}

(e2)={v3,v4} ,

(e3)={v1,v3}

(e4)={v2,v4} ,

(e6)={v2, v2}

Datos Representación de G

e1

e2

e3e4

e5v1

v3

v2

v4

DEFINICIONES

8

• Grado de un vértice: número de aristas que inciden en él.

• Notación: g(v): grado del vértice v

• Propiedad: g(v)=2|E|

• Observaciones: La suma de los grados es par. La cantidad de

vertices de grado impar es par

• Bucle o lazo: arista de un vértice a sí mismo. Contribuye en dos

unidades al grado del vértice

• Vértice aislado: es un vértice de grado 0

• Lados paralelos: Dos lados que inciden en los mismos vértices

• Grafo Simple: Aquel que no tiene lazos ni lados paralelos

9

MAS DEFINICIONES• Un camino o trayectoria en G es una sucesión finita

de vértices de G, cada uno adyacente al

siguiente y una elección de una arista entre de tal

modo que ninguna arista es elegida más de una vez.

• La longitud de un camino es el número de aristas que hay en él.

• En caso de un grafo con lados paralelos , la secuencia debe indicar las aristas

• Un circuito es un camino que comienza y termina en el

mismo vértice

• Un camino simple es el camino donde todos los vértices

son distintos

• Un circuito simple o ciclo es aquel circuito que no repite

vértices

k21 vvv : ,...,,k1 v-v

1ii vy v

EJERCICIO PARA EL ALUMNO

10

Vértice Grado

v1

v2

v3

v4

v5

Dado el siguiente grafoCompletar la siguiente tabla

v2 v1

v3

v5

v4


11

Encontrar

Camino v2-v3 de longitud 2

Camino v2-v3 de longitud 3

Circuito v1-v1 de long 4

Circuito v2-v2 de long3

Ciclo v2-v2 de long 2

Ciclo v3-v3 de long 3

Circuito v5-v5 de longitud 4

Circuito v4-v4 de longitud 1

Dado el siguiente grafo

v2 v1

v3

v5

v4

GRAFO CONEXO

12

Sea G = (V,E, ). Decimos que G es conexo si existe

una trayectoria entre cualesquiera par de vértices

distintos de G.

Un grafo que no es conexo se dice disconexo y

sus diversas partes conexas son las componentes

conexas del grafo.

Ejemplo de grafo conexo

a

d

b

c

ef

FAMILIAS ESPECIALES DE GRAFOS1. Grafo Discreto: Sea nN, se llama Grafo

Discreto a todo grafo con n vértices y sin aristas. Se denota con Dn

D2 D5

2. Grafo Completo: Sea nN, llamamos Grafo

Completo a todo grafo con n vértices y con una

arista {vi, vj} para cada i, j (distintos). Se denota

Kn

K3

K4

13

v1 v2

v3v4

v1

v2

v3

3. Grafo Regular: Es una grafo donde todos los

vértices tienen el mismo grado.

Ejemplos: Todos los Kn y Dn para todo n 1 son

grafos regulares

Observación: Hay grafos regulares que son

completos y otros que no lo son.

14

v1

v2

v3

v4

v5

a

bc

d

3. Grafo Lineal: nN , se llama Grafo Lineal a Ln ,

grafo con n vértices y aristas {vi, vi+1} para 1 ≤ i <

n.

Ejemplos:

L2 L4

15

v1 v4v2 v3

v2v1

SUBGRAFOS Sea G = (V,E, ). Sean E1 E, V1 V, tales que V1 contenga al

menos todos los extremos de las aristas de E1.

Entonces H= (V1,E1, 1) se dice subgrafo de G , donde 1 es

restringida a las aristas en E1

Ejemplo:

H G

H es subgrafo de G

16

a b

cd

e f

gh

e f

gh

cd


17

Determinar cual de los siguientes grafos es subgrafo de G

b

c

d

e

f

a

g

b

c

d

e

f

a

gb

c

d

e

f

a

b

c

d

e

f

a

gb

h

a

H1

G

H2

H3 H4

GRAFO COCIENTE

Sean G = (V,E, ) y sea R una relación de

equivalencia sobre V. El grafo cociente GR es tal

que sus vértices son las clases de equivalencia

de V producidas por R y las aristas son tales que

si [v] y [w] son las clases de equivalencia de v y

w de G, entonces existe una arista en GR de [v] a

[w] si algún vértice en [v] está conectado con

algún vértice en [w] en la gráfica G. 18

Sea G = (V,E, ):

y sea R la relación de equivalencia sobre V que

determina la partición V/R={{a,e,i},{b,f,j},{c,g,k},

{d,h,l}}, entonces GR:

19

a

l

I J

k

b

g

c

h

d

e f

[b]

[d]

[a]

[c]


20

a) V/R={{a,b,c,d},{e,f,g,h}, {i,j,k,l}}

b) V/R={{a,e},{b,f},{g,c},{h,d},{i,j,k,l}}

Partición determinada por R Realizar las Gráficas GR

Dada una gráfica G, se dice que posee una

trayectoria de Euler si posee una trayectoria que

incluye todas las aristas sólo una vez.

Ejemplo: E, D, B, A, C, D

Dada una gráfica G, se dice que posee un Circuito

de Euler si posee una trayectoria de Euler que es a

la vez un circuito, o sea, comienza y termina en el

mismo vértice.

Ejemplo: 5, 3, 2, 1, 3, 4, 5 21

E

D

BA

C

51

23

4

GRAFOS CON TRAYECTORIA DE EULER

GRAFOS CON CIRCUITO DE EULER

Dada una gráfica conexa G

a) G posee al menos un circuito de Euler si y solo si

todos los vértices de grado par.

b) G posee al menos una trayectoria de Euler si y solo

si posee exactamente dos vértices de grado, los

que serán el inicio y fin de cualquier trayectoria

22

TEOREMAS


23

La figura muestra el mapa de las calles de un barrio. Los responsables de recoger todo material de reciclado deben iniciar y terminar su viaje en la planta de reciclado. Ellos deben planear su ruta de modo que cubra todo el barrio y que cada calle sea recorrida una sola vez. ¿Cuál podría ser el grafo que modela esta situación problemática?¿Qué se buscaría en el grafo?¿Existe una ruta que cumpla los requisitos del problema?

ALGORITMO DE FLEURY

La búsqueda de algún circuito de Euler puede ser

complejo en el caso de grafos grandes. El algoritmo

de Fleury permite obtener un circuito de Euler, en

los casos que exista, en grafos de cualquier tamaño

Definición previa:

Una arista {vi, vj} es un puente en un grafo conexo

G si al eliminar {vi, vj} se crea un grafo disconexa.

Ejemplo: {B, E} es un puente en24

A

D

C

B

E

• Algoritmo de Fleury: Sea G = (V,E, ) un grafo conexo con

todos sus vértices de grado par:

– Paso 1. Se elige un miembro v V como vértice inicial para el

circuito. Sea : v el inicio de la trayectoria a construir

– Paso 2. Suponga que ya se construyó : v, u, …..,w. Si en w

sólo existe una arista {w,z}, se extiende : v, u, …..,w, z. Se

elimina {w,z} de E y w de V . Si en w existen varias aristas,

se elige una arista {w, z}que no sea un puente. Extienda

a : v, u, …..,w, z y elimine {w,z} de E.

– Paso 3. Repita el Paso 2 hasta que no sobren aristas en E.

– Fin del algoritmo. La trayectoria lograda es un Circuito

de Euler para el grafo G25

El siguiente grafo, posee circuito de Euler?

En caso afirmativo aplique el Algoritmo de Fleury para obtener un

circuito Euleriano que comience en i


26

eb

c

d

a

f

gh

i

TRAYECTORIAS Y CICLOS DE HAMILTON

27

Este tipo de trayectoria recibe

el nombre del matemático

William Hamilton, quien

desarrollo y comercializo un

juego que consistía en una

cuerpo de madera en forma de

dodecaedro regular, con las

instrucciones para encontrar

dicho circuito. Se llamaba:

Juego de la vuelta del mundo

12

56

78

910

11

12

13

14

15

1617

1819

20

3

4

Una solución posible

TRAYECTORIAS Y CIRCUITOS HAMILTONIANOS

Una trayectoria Hamiltoniana para un grafo G es

aquella que contiene todos los vértices de G una

vez.

Un circuito Hamiltoniano para un grafo G es un

circuito que contiene todos los vértices de G una vez.

28

G1 G2 G3

G1 y G2 poseen circuito de Hamilton pero G3 solo posee trayectoria hamiltoniana

TEOREMAS Sea G un grafo con n vértices, n>2, sin bucles ni aristas

paralelas

Teorema1:

G posee un circuito hamiltoniano si para cualesquiera dos

vértices u y v de G que no sean adyacentes, el grado de u más

el grado de v es

mayor o igual que n.

Corolario

G tiene circuito hamiltoniano si cada vértice tiene grado mayor

o igual que n/2

Teorema 2

Sea m el número de aristas de G. Entonces G tiene un circuito

hamiltoniano si m 1/2(n2-3n+6)


30

Encuentre, si existe, al menos un circuito Hamiltoniano de cada uno de los siguientes grafos

6

ENLACES INTERESANTES

http://eisc.univalle.edu.co/materias/Matematicas_Discretas_2/pdf/euler_hamilton_grafos_05.pdf

http://www.authorstream.com/Presentation/aSGuest39615-339336-Circuitos-de-Euler-Hamilton-circuitoseulerh-Science-Technology-ppt-powerpoint/

http://www.slideshare.net/gugaslide/grafos-presentation

http://www.slideshare.net/aguzman2002/teoria-de-grafos-introduccin

31










D

B

C

AA

E

F

APLICACIÓN: GRAFO COCIENTE

El grafo dado representa a seis pueblos unidos por carreteras. EntoncesV = { A,B,C,D,E,F} y

Sea la relacion R dada porXRY X e Y pertenecen al mismo municipioSe puede ver que R es de equivalencia

Supongamos que la partición determinada por R sea :V/R={{A,B},{F},{C,D},{E}}

Encontrar el grafo cociente GR y decir cual es su interpretación?

E = {{A,B},{A,C},{A,F},{B,F},{C,D},{C,E},{D,E}}

C

GR INTERPRETACION- Existen rutas entre los

municipios de : A y F A y C

C y E- No existe ruta entre los

municipios de:A y E

F y EF y C

E

[A][F]

[E] [C]

Lic. Gladys Mónica RomanoMatemática Discreta – UTN - FRT

Documents

Grafos