capítulo 7: grafos capítulo 7: grafos capítulo 7: grafos capítulo 7: grafos autor: josé alfredo...

45
Capítulo 7: Grafos Capítulo 7: Grafos Autor: José Alfredo Jiménez Murillo

Upload: bernardo-iglesias-gallego

Post on 25-Jan-2016

397 views

Category:

Documents


11 download

TRANSCRIPT

Page 1: Capítulo 7: Grafos Capítulo 7: Grafos Capítulo 7: Grafos Capítulo 7: Grafos Autor: José Alfredo Jiménez Murillo

Capítulo 7: GrafosCapítulo 7: GrafosCapítulo 7: GrafosCapítulo 7: Grafos

Autor: José Alfredo Jiménez Murillo

Page 2: Capítulo 7: Grafos Capítulo 7: Grafos Capítulo 7: Grafos Capítulo 7: Grafos Autor: José Alfredo Jiménez Murillo

Objetivos

-

-

-

Aplicar la teoría de grafos a la solución de problemas factibles de ser resueltos con esta metodología.

Aprender la simbología y nomenclatura propia de la teoría de grafos y distinguir las características de los grafos.

Conocer las condiciones que debe cumplir un grafo que se considera que tiene circuitos importantes como Euler y Hamilton.

Usar la técnica de coloración de grafos para iluminar un mapa con la cantidad mínima de colores sin que se junten dos colores iguales.

-

Page 3: Capítulo 7: Grafos Capítulo 7: Grafos Capítulo 7: Grafos Capítulo 7: Grafos Autor: José Alfredo Jiménez Murillo

Introducción

Uno de los primeros trabajos de teoría de grafos que se llevó a cabo fue el que realizó Leonhard Euler en el siglo XVIII sobre los puentes de Königsberg (en la ciudad Rusa de Kaliningrado), en el cual pretendía hacer un recorrido a través de 7 puentes que conectaban a 4 porciones de tierra como se muestra en la figura

RíoA B

D

C

El objetivo era salir de un punto específico y regresar al punto de partida después de haber cruzado los 7 puentes, pero pasando solamente una vez por cada uno de ellos. Euler representó al problema por medio de una figura como la siguiente.

Page 4: Capítulo 7: Grafos Capítulo 7: Grafos Capítulo 7: Grafos Capítulo 7: Grafos Autor: José Alfredo Jiménez Murillo

C

BA

D

A esta figura Euler la llamó “Grafo”, a las porciones de tierra representadas por un punto las llamó “Vértices”, a los puentes representados por líneas les dio el nombre de “Aristas” y a las líneas que salen o entran a un vértice los llamó “Orden del vértice”, más tarde al orden de un vértice se le llamó valencia.

Después de analizar el problema, Euler llegó a la conclusión de que es imposible obtener un itinerario que saliera de un vértice y regresara a él, pasando por todas las aristas solamente una vez.

Euler mencionaba que si el vértice donde se inicia y termina el recorrido es el mismo, entonces dicho vértice debe tener valencia par ya que por un puente sale y por otro diferente debe regresar. Lo mismo ocurre con todos los demás vértices ya que debe estar contemplada la entrada y salida, por lo tanto Euler estableció que “En un grafo solamente se puede establecer un ciclo que pase por todas las aristas de un grafo solamente una vez, si todos los vértices tienen valencia par”.

Introducción

Page 5: Capítulo 7: Grafos Capítulo 7: Grafos Capítulo 7: Grafos Capítulo 7: Grafos Autor: José Alfredo Jiménez Murillo

Partes de un grafo

Un grafo (G) es un diagrama que consta de un conjunto de vértices (V) y un conjunto de lados (L). Sea el siguiente grafo.

6

5

32

41

c

da

b Vértices (Nodos). Se indican por medio de un pequeño círculo y se les asigna un número o letra. En la figura anterior V={a, b, c, d}.

Lados (ramas o aristas). Son las líneas que unen un vértice con otro. Se les asigna una letra, número o combinación de ambos: L={1, 2, 3, 4, 5, 6}.Lados paralelos . Son aquellas

aristas que tienen relación con un mismo par de vértices: P={2, 3}.

Lazo. Es aquella arista que sale de un vértice y regresa al mismo vértice. En la figura anterior A={6}.

Valencia de un vértice. Es el número de lados que salen o entran a un vértice. En la figura anterior las valencias de los vértices son: Valencia (a) = 2

Valencia (b) = 4Valencia (c) = 2Valencia (d) = 3

Page 6: Capítulo 7: Grafos Capítulo 7: Grafos Capítulo 7: Grafos Capítulo 7: Grafos Autor: José Alfredo Jiménez Murillo

Tipos de grafos

Grafos simples. Son aquellos grafos que no tienen lazos ni lados paralelos. Ejemplo.

9

8

73

21

gf

e

d

c

b

a

6

5

4

Grafo completo de n vértices (Kn). Es aquel grafo en donde cada vértice está relacionado con todos los demás, sin lazos ni lados paralelos. Se indica como Kn, en donde n es el número de vértices del grafo.

65

4c

d

1

1

2

3

ba

c

baba

1

2

3

K2 K3K4

La valencia en cada uno de los vértices es (n-1) y el número de lados

está dado por la expresión:

( 1)

2

n n No. de vértices

=

Page 7: Capítulo 7: Grafos Capítulo 7: Grafos Capítulo 7: Grafos Capítulo 7: Grafos Autor: José Alfredo Jiménez Murillo

Complemento de un grafo (G’). Es aquél grafo que le falta al grafo G, para entre ambos formar un grafo completo de n vértices. Dicho grafo no tiene lazos ni ramas paralelas. Ejemplo:

9

8 7

3

1

f

e

d

c

b

a6

5

4

G

e

b

15

12

11

10

f

d

c

a

1413

G’

2

Valencia de cada vértice = (n-1)=(6-1) = 5

No. de lados =( 1)

2

n n = 2

)16(6 = 15

Tipos de grafos

Page 8: Capítulo 7: Grafos Capítulo 7: Grafos Capítulo 7: Grafos Capítulo 7: Grafos Autor: José Alfredo Jiménez Murillo

Grafo Bipartido. Es aquel que está compuesto por dos conjuntos de vértices. Uno de ellos A = {a1, a2, a3, ... , an} y otro B = { b1, b2, ..., bm}, además de que los vértices del conjunto A se relacionan con los del B, pero entre los vértices de un mismo conjunto no existe arista que los una. Ejemplo:

3

6

4

5

12

7

3

67

45

1

2

A

B

A={5,6,7} y B={1,2,3,4}A={1,3,4,6} y B={2,5,7}

Tipos de grafos

Page 9: Capítulo 7: Grafos Capítulo 7: Grafos Capítulo 7: Grafos Capítulo 7: Grafos Autor: José Alfredo Jiménez Murillo

Grafo bipartido completo (Kn,m). Es aquél grafo que está compuesto por dos conjuntos de vértices. Uno de ellos A = {a1, a2, a3, ..., an} y otro B = { b1, b2, ..., bm}, en donde cada vértice de A está unido con todos los vértices de B pero entre los vértices de un mismo conjunto no existe arista que los una. El grafo bipartido completo se indica como Kn,m. Ejemplo:

321

ba

4

K4,2

A={1,2,3,4}

B={a,b}

1

2

3b

a

K2,3

A={1,2,3}

B={a,b}

1

2

3

4

56

1

3

6 5

4

2No es grafo bipartido completo porque no cumple con la condición, como se observa en el grafo equivalente de al lado

Tipos de grafos

Page 10: Capítulo 7: Grafos Capítulo 7: Grafos Capítulo 7: Grafos Capítulo 7: Grafos Autor: José Alfredo Jiménez Murillo

Representación matricial

Matriz de adyacencia (Ma). Es una matriz cuadrada en la cual los vértices del grafo se indican como filas, pero también como columnas de la matriz

a b c d e

a 1 1 1 0 1

b 1 0 1 1 0

Ma = c 1 1 1 1 0

d 0 1 1 0 1

e 1 0 0 1 0

d

b

a

e

cx1

x2

x3

x4

x5x6

x7

x8

x9

x10 x11

e

Matriz de incidencia (Mi). En esta matriz se colocan los vértices del grafo como filas y las aristas como columnas.

x1 x2 x3 x4 x5 x6 x7 x8 x9 x10 x11

a 0 0 0 1 1 1 0 0 1 1 0 5

b 1 1 0 1 0 0 1 0 0 0 0 4

Mi = c 0 0 1 0 0 1 1 1 0 0 0 4

d 1 1 1 0 0 0 0 0 0 0 1 4

e 0 0 0 0 0 0 0 0 1 1 1 3

2 2 2 2 1 2 2 1 2 2 2

2 son aristas

1 lazos

Valencias

Page 11: Capítulo 7: Grafos Capítulo 7: Grafos Capítulo 7: Grafos Capítulo 7: Grafos Autor: José Alfredo Jiménez Murillo

Caminos y circuitos

En un grafo se puede recorrer la información de diferente manera, lo que implica seguir distintas rutas para llegar de un nodo del grafo a otro.

Camino. Es una sucesión de lados que van de un vértice x a un vértice w (dichos lados se pueden repetir).

Circuito (Ciclo). Es un camino del vértice w al vértice w. Esto es, un camino que regresa al mismo vértice de donde salió.

Camino simple de longitud n. Es una sucesión de lados que van de un vértice x a un vértice w, en donde los lados que componen dicho camino son distintos e iguales a n.

Circuito simple de longitud n. Es aquél camino del vértice w al vértice w que solamente tiene un ciclo en la ruta que sigue.

Page 12: Capítulo 7: Grafos Capítulo 7: Grafos Capítulo 7: Grafos Capítulo 7: Grafos Autor: José Alfredo Jiménez Murillo

f

h g

db

a

e

c

Ejemplo

Recorrido Camino Camino simple Circuito Circuito simple

{a,c,d,f} * *

{c,b,a,h,a} *

{b,c,d,e,e,c,b} * *

{c,e,d,c} * * *

{e,e} * * *

{a,c,e,e,g,e,d,c,a} * *

{h,a,c,e,d,b} * *

En la tabla siguiente se muestran distintos recorridos del grafo que se encuentra al lado.

Page 13: Capítulo 7: Grafos Capítulo 7: Grafos Capítulo 7: Grafos Capítulo 7: Grafos Autor: José Alfredo Jiménez Murillo

Grafo conexo. Es aquél en el que para cualquier par de vértices w, x, distintos entre sí, existe un trayecto para ir de w a x. Ejemplo:

c

b

a

f

ed

d

b

a

ec

Grafo conexo

Grafo no conexo

f

En el grafo conexo (conectado) siempre existe un camino para ir de un vértice a otro.

Ejemplo

Page 14: Capítulo 7: Grafos Capítulo 7: Grafos Capítulo 7: Grafos Capítulo 7: Grafos Autor: José Alfredo Jiménez Murillo

f

h

g

db

a

e

c

Camino de Euler. Es el camino que recorre todos los vértices pasando por todas las ramas solamente una vez.

Una característica del camino de Euler es que el recorrido sale de un vértice de valencia impar y termina también en un vértice de valencia impar.

Camino de Euler es {a, b, e, h, g, e, d, a, c, f, d, g, f, h}

Ejemplo

Page 15: Capítulo 7: Grafos Capítulo 7: Grafos Capítulo 7: Grafos Capítulo 7: Grafos Autor: José Alfredo Jiménez Murillo

Circuito de Euler. Es aquel ciclo que recorre todos los vértices pasando por todos los lados solamente una vez.

“La firma del diablo” es un juego que consiste en dibujar una figura sin levantar el lápiz del papel, partiendo de un punto y regresando nuevamente a él, sin pasar dos veces por una misma arista. Este problema se puede resolver por medio del circuito de Euler.

El algoritmo Fleury permite determinar un circuito de Euler

Si todos los vértices del grafo ya están desconectados, ya se tiene el circuito de Euler y finalizar. De otra manera continuar con el paso 3.

Verificar que el grafo sea conexo y que todos los vértices tengan valencia par. Si no cumple con estas condiciones entonces el grafo no tiene circuito de Euler y finalizar.

Si cumple con la condición anterior seleccionar un vértice arbitrario para iniciar el recorrido.

Escoger una arista a partir del vértice actual. Esa arista seleccionada no debe ser Lado puente* a menos que no exista otra alternativa.

Desconectar los vértices que están unidos por la arista seleccionada.

1)

2)

3)

4)

5)

Ejemplo

Page 16: Capítulo 7: Grafos Capítulo 7: Grafos Capítulo 7: Grafos Capítulo 7: Grafos Autor: José Alfredo Jiménez Murillo

Ejemplo

A partir del siguiente grafo, determinar un circuito de Euler

h gf

d

ba

ec

Usando el algoritmo de Fleury

Se observa que es conexo y todos los vértices tienen valencia par, por lo tanto tiene circuito de Euler.

1)

Seleccionar un vértice arbitrario, por ejemplo {b} y llamarlo vértice actual.

2)

Escoger una arista que no sea puente a partir del vértice actual. (Arista punteada {b,d})

3)

h gf

d

ba

ec

Eliminar la arista seleccionada. El vértice actual ahora es (d).

4)

h gf

d

ba

ec

Si todos los vértices del grafo ya fueron eliminados, ya se tiene el circuito de Euler, en caso contrario regresar al paso 3.

5)

Escoger una arista que no sea puente a partir del vértice actual. {b,d,e)

3.1)

f

ba

h g

d ec

Eliminar la arista seleccionada. El vértice actual ahora es (e)

4.1)

h gf

d

ba

ec

Page 17: Capítulo 7: Grafos Capítulo 7: Grafos Capítulo 7: Grafos Capítulo 7: Grafos Autor: José Alfredo Jiménez Murillo

Escoger una arista que no sea puente a partir del vértice actual. {b,d,e,b)

3.2)

ba

fh g

d ec

Eliminar la arista seleccionada. El vértice actual ahora es (b).

4.2)

ba

fh g

d ec

Escoger una arista que no sea puente a partir del vértice actual. {b,d,e,b,c)

3.3)

ba

fh g

d ec

Eliminar la arista seleccionada. El vértice actual ahora es (c).

4.3)

h f

ba

g

d ec

Escoger una arista que no sea puente a partir del vértice actual. {b,d,e,b,c,h). Observar cómo en este caso no puede ser la arista (c,a) ya que es puente y el grafo ya no sería conexo.

3.4)

f

ba

h g

d ec

Eliminar la arista seleccionada. El vértice actual ahora es (h).

4.4)

f

ba

h g

d ec

Continuar hasta que todos los vértices estén desconectados para obtener el circuito de Euler.

Ejemplo

Page 18: Capítulo 7: Grafos Capítulo 7: Grafos Capítulo 7: Grafos Capítulo 7: Grafos Autor: José Alfredo Jiménez Murillo

h

Circuito de Hamilton. Es un problema similar al circuito de Euler, pero en lugar de pasar por todos los lados del grafo solamente una vez como lo hace el circuito de Euler, en el circuito de Hamilton se pasa por cada vértice solamente una vez.

En un grafo se sabe de antemano que tiene un circuito de Euler, si es conexo y todos sus vértices tienen valencia par, pero no hay forma de saber con anticipación si tiene o no un circuito de Hamilton.

Encontrar (si es posible) un circuito de Hamilton en el siguiente grafo.

j

i

f

h

g

d

b

a

ec

Ejemplo:

j

i

f

g

d

b

a

ec

RespuestaObservar como no es necesario que se pase por todas las aristas.

Circuito de Hamilton: {a,b,h,g,e,j,i,f,d,c,a}

Ejemplo

Page 19: Capítulo 7: Grafos Capítulo 7: Grafos Capítulo 7: Grafos Capítulo 7: Grafos Autor: José Alfredo Jiménez Murillo

Isomorfismo

Se dice que dos grafos G1 y G2 son isomorfos cuando, teniendo apariencia diferente, realmente son iguales porque coinciden en:

• Mismo número de lados.• Mismo número de vértices.• Mismo conjunto de valencias.• Ambos son o no conexos.• Ambos tienen el mismo número de circuitos de longitud n.• Ambos tienen o no circuito de Euler.

Esto implica que todos los vértices de G1 tienen un vértice equivalente en G2 y que todas las aristas del grafo G1 tienen una arista equivalente en G2.

Por otro lado, se sabe que dos grafos G1 y G2 son isomorfos si y sólo si para alguna ordenación de vértices y sus aristas, sus matrices de incidencia son iguales.

Page 20: Capítulo 7: Grafos Capítulo 7: Grafos Capítulo 7: Grafos Capítulo 7: Grafos Autor: José Alfredo Jiménez Murillo

Determinar si los grafos siguientes G1 y G2 son isomorfos, haciendo coincidir sus matrices de incidencia, manteniendo una matriz estática y realizando intercambios de filas y/o columnas en la otra matriz.

Ejemplo

x10

r9

r8

r7

r3

r5

r4

r6

r2

r1

x10

x9

x8

x7

x6

x5

x4

x3

x1

x2

5

6

4

3

f

2

1d

b

a

ec

G1G2

Page 21: Capítulo 7: Grafos Capítulo 7: Grafos Capítulo 7: Grafos Capítulo 7: Grafos Autor: José Alfredo Jiménez Murillo

Las matrices de incidencia son:

 

 

 

 

1001000000f

1110001000e

0100110100d

0011100001c=MG1

0000001111b

0000010010a

x10x9x8x7x6x5x4x3x2x1

10101000016

01011001005

10000111004

00010000103=MG2

00000100012 

01100010101

r10r9r8r7r6r5r4r3r2r1

Ejemplo

Page 22: Capítulo 7: Grafos Capítulo 7: Grafos Capítulo 7: Grafos Capítulo 7: Grafos Autor: José Alfredo Jiménez Murillo

1001000000300010000103

0101100100501011001005

0010100011610101000016

00000111104=10000111004=MG2

1110001000101100010101

0000010001200000100012

r2r9r8r7r6r5r4r3r10r1r10r9r8r7r6r5r4r3r2r1

Solución: Se deben hacer intercambios de filas por columnas hasta hacer que MG2=MG1

1001000000310010000003

1110001000511100010005

0100110100601001101006

00000011011=00111000101=MG2

0011100011400000011114

0000010010200000100012

r7r6r9r2r8r1r3r10r5r4r7r6r9r2r8r1r3r10r4r5

Aquí faltan más intercambios hasta llegar a...

Ejemplo

Page 23: Capítulo 7: Grafos Capítulo 7: Grafos Capítulo 7: Grafos Capítulo 7: Grafos Autor: José Alfredo Jiménez Murillo

Demostrar que dos grafos son isomorfos haciendo intercambios de filas y/o columnas, hasta que las matrices de incidencia coincidan, es muy complicado y a medida que aumenta el número de vértices y aristas es aún más complicado.

En lugar de hacer coincidir las matrices lo que se realiza es una comparación de las propiedades principales de los grafos; si coinciden en todas ellas se concluye que son isomorfos, pero si existe alguna diferencia ya sea en el número de vértices, en el conjunto de valencias, o si uno de ellos es conexo y el otro no, o si uno tiene circuito de Euler y el otro no, o si uno de ellos tiene más circuitos de longitud n que el otro, eso es causa suficiente para determinar que los grafos no son isomorfos.

Ejemplo

Page 24: Capítulo 7: Grafos Capítulo 7: Grafos Capítulo 7: Grafos Capítulo 7: Grafos Autor: José Alfredo Jiménez Murillo

La siguiente tabla muestra las propiedades en donde debe haber coincidencia entre G1 y G2 anteriores para que se consideren isomorfos.

Propiedad G1 G2 Observación

No. de vértices 6 6

No. de lados 10 10

Valencias 2,4,4,4,4,2 4,2,2,4,4,4 Coinciden en el mismo número de vértices de valencia 2 y de valencia 4

Conexo Si Si Ya que para cualquier par de vértices se puede encontrar un camino.

Camino de Euler No No Ya que todos los vértices tienen valencia par

Circuito de Euler Si Si Ya que todos los vértices tienen valencia par y se trata de grafos conexos.

Circuitos de longitud n (En este caso de longitud 3)

6a,b,d,ab,e,c,bb,d,c,bb,d,e,bc,d,e,cc,e,f,c

61,3,5,11,6,4,11,4,5,11,5,6,12,4,6,24,5,6,4

En lugar de tener longitud 3, se pudo ver cuántos circuitos tienen longitud 4. Pero en cualquier caso debe coincidir.

Ejemplo

Page 25: Capítulo 7: Grafos Capítulo 7: Grafos Capítulo 7: Grafos Capítulo 7: Grafos Autor: José Alfredo Jiménez Murillo

Grafos planos. Un grafo plano es aquél que se puede dibujar en un solo plano y cuyas aristas no se cruzan entre sí. Ejemplo:

f

db

a

e

c

Euler establece que la ecuación A = L – V +2 es válida para un grafo plano y conexo. En donde A: Numero de áreas, L: Número de lados y V: Número de vértices.

f

db

a

e

c

1 2

34 5

6

A = L – V +26 = 10 – 6 +2

Observar cómo la parte que rodea al grafo también se cuenta como área.

Ejemplo

Page 26: Capítulo 7: Grafos Capítulo 7: Grafos Capítulo 7: Grafos Capítulo 7: Grafos Autor: José Alfredo Jiménez Murillo

Existen grafos importantes que se vieron anteriormente, por ejemplo K4 es un grafo plano ya que se puede dibujar en forma plana sin que sus aristas se crucen. Pero K5 es un grafo no plano ya que no hay forma en que por lo menos un par de aristas se deje de cruzar.

K5

e

dc

a

b

c

b a

d

K4

Otro grafo importante que no es plano, es el grafo bipartido completo K3,3.

fe

d

ba cTanto K5 como K3,3 se utilizan como patrones para demostrar que otros grafos más grandes no son planos.

Ejemplo

Page 27: Capítulo 7: Grafos Capítulo 7: Grafos Capítulo 7: Grafos Capítulo 7: Grafos Autor: José Alfredo Jiménez Murillo

Solución

Por más que se trate de dibujar el grafo en forma plana no va a ser posible, ya que tiene dentro de él un grafo no plano K3,3.

7

5

6

4

1

3

8

2

9

De esta forma si se eliminan las aristas punteadas, los vértices de

valencia dos y los nodos que queden desconectados se descubrirá un grafo K3,3.

Dibujar en forma plana el siguiente grafo, o bien demostrar que no es plano encontrando dentro de él un grafo K3,3 o K5. En caso de ser plano probar que se cumple la ecuación de Euler A=L-V+2.

7

5

6

4

1

3

8

2

9

10

Ejemplo

Page 28: Capítulo 7: Grafos Capítulo 7: Grafos Capítulo 7: Grafos Capítulo 7: Grafos Autor: José Alfredo Jiménez Murillo

Dibujar en forma plana el siguiente grafo o bien demostrar que no es plano encontrando dentro de él un grafo K3,3 o K5. En caso de ser plano probar que se cumple la ecuación de Euler A=L-V+2.

Tampoco este grafo es plano ya que dentro de él se puede encontrar:

7

56

4

1

3

8

2

9

Eliminando los lados de línea punteada y los vértices {1, 3, 5, 8, 10 y 11} se encuentra que hay un grafo K5 y que por lo tanto este grafo no es plano.

7

56

4

1

3

8

2

91011

Ejemplo

Page 29: Capítulo 7: Grafos Capítulo 7: Grafos Capítulo 7: Grafos Capítulo 7: Grafos Autor: José Alfredo Jiménez Murillo

Dibujar en forma plana el siguiente grafo o bien demostrar que no es plano encontrando dentro de él un grafo K3,3 o K5. En caso de ser plano probar que se cumple la ecuación de Euler A=L-V+2.

Solución

En este caso se trata de un grafo plano como se muestra:

En éste se cumple la Ecuación de Euler:

A = L – V + 2

11 = 19 – 10 + 2

7

5 64

13

8

2

9

10

11

7

5

6 4

13

8

2

9 10

11

Ejemplo

Page 30: Capítulo 7: Grafos Capítulo 7: Grafos Capítulo 7: Grafos Capítulo 7: Grafos Autor: José Alfredo Jiménez Murillo

Los grafos de similaridad permiten agrupar información con características semejantes. Esto implica formar subgrafos en donde los vértices de un subgrafo están relacionados entre sí pero no tienen relación con los vértices del otro subgrafo, ya que no son similares. Una utilidad de este tipo de grafos es en reconocimiento de patrones, en donde se agrupa información con propiedades muy parecidas.

Grafos de similaridad

En este tipo de grafo se debe definir una función que permita determinar la similaridad que existe entre los vértices, principalmente la distancia entre sus características. Una función muy usada para determinar la distancia es

S(Px-Py) = Px,i-Py,i=Px,1-Py,1+Px,2-Py,2+………+Px,n-Py,m

en donde Px,n es la propiedad n del punto Px, y Py,m es la propiedad m del punto Py.

Page 31: Capítulo 7: Grafos Capítulo 7: Grafos Capítulo 7: Grafos Capítulo 7: Grafos Autor: José Alfredo Jiménez Murillo

Con la función anterior es posible encontrar la distancia que existe entre las propiedades de los vértices x y y. Un valor grande de S(Px-Py) indica que no existe similaridad entre los vértices x y y, mientras que un valor pequeño significa que son muy parecidos o similares.

Pero además de la función anterior, es necesario un valor referencial para discriminar la información que en este caso se llamará coeficiente de inferencia “C”. El valor de C se puede seleccionar de acuerdo a la experiencia que se tenga en el campo o bien por medio de prueba piloto. Si C es grande la similaridad es poco exacta, sin embargo para un valor de C pequeño la similaridad es muy fuerte.

Una vez que se tiene S(Px-Py) para todos los puntos (vértices) en cuestión, se forman los grafos similares por medio del siguiente criterio:

Si S(Px-Py) C se traza una arista entre los vértices Px y Py, y se dice que Px y Py son similares. Los grafos similares forman un subgrafo y los no similares otro distinto.

Grafos de similaridad

Page 32: Capítulo 7: Grafos Capítulo 7: Grafos Capítulo 7: Grafos Capítulo 7: Grafos Autor: José Alfredo Jiménez Murillo

La siguiente tabla muestra las características que tienen las diferentes partes de tejido de igual sección transversal de un análisis de mama, de acuerdo a “temperatura”, “Intensidad de color” e “inflamación”.

949395

541364

847403

642372

748391

Inflamación (I)

Color (Co)

Temperatura (T)

Parte (P)

Determinar los grafos de similaridad para un coeficiente de inferencia C=5.

Ejemplo

Page 33: Capítulo 7: Grafos Capítulo 7: Grafos Capítulo 7: Grafos Capítulo 7: Grafos Autor: José Alfredo Jiménez Murillo

Respuesta

Lo primero que se debe hacer es encontrar la distancia entre los puntos Px y Py por medio de la siguiente función:

S(Px-Py) = Px,i-Py,i=Px,1-Py,1+Px,2-Py,2+………+Px,n-Py,m

Si x = y.

S(P1-P1) = P1,1-P1,1+P1,2-P1,2+P1,3-P1,3 = 39 - 39+48 - 48+7 - 7=0

Si x ≠ y.

S(P1-P2) = P1,1-P2,1+P1,2-P2,2+P1,3-P2,3 = 39 - 37+48 - 42+7 - 6= 9

S(P1-P3) = P1,1-P3,1+P1,2-P3,2+P1,3-P3,3 = 39 - 40+48 - 47+7 - 8=

S(P1-P4) = P1,1-P4,1+P1,2-P4,2+P1,3-P4,3 = 39 - 36+48 - 41+7 - 5= 12

S(P1-P5) = P1,1-P5,1+P1,2-P5,2+P1,3-P5,3 = 39 - 39+48 - 49+7 - 9=

3

3

Page 34: Capítulo 7: Grafos Capítulo 7: Grafos Capítulo 7: Grafos Capítulo 7: Grafos Autor: José Alfredo Jiménez Murillo

S(P2-P3) = P2,1-P3,1+P2,2-P3,2+P2,3-P3,3 = 37 - 40+42 - 47+6 - 8= 10

S(P2-P4) = 37 - 36+42 - 41+6 - 5 =

S(P2-P5) = 37 - 39+42 - 49+6 - 9 = 12

S(P3-P4) = 40 - 36+47 - 41+8 - 5 = 13

S(P3-P5) = 40 - 39+47 - 49+8 - 9 =

S(P4-P5) = 36 - 39+41 - 49+5 - 9 = 15

Si se considera que dos puntos son similares si S(Px-Py) C, en este caso S(Px-Py) 5 (valores con fondo azul) con lo cual se puede decir que el grafo está dividido en dos partes como se muestra a continuación.

P3P5

P1

P4

P2

Los lazos en cada uno de los vértices significan la similaridad entre ellos mismos. Con los grafos anteriores se puede considerar que las partes de tejido P1, P3, P5 son similares y las partes P2 y P4 también lo son.

3

4

Respuesta

Page 35: Capítulo 7: Grafos Capítulo 7: Grafos Capítulo 7: Grafos Capítulo 7: Grafos Autor: José Alfredo Jiménez Murillo

Grafos ponderados

En un grafo ponderado a las aristas se les asigna un valor. A ese valor se le llama ponderación y podría representar la distancia que hay de un nodo a otro, o bien el costo de transportarse de una ciudad a otra.

Determinar la ruta más corta es un problema típico de la teoría de grafos y consiste en encontrar el camino más corto para ir de una ciudad origen (w) a una ciudad destino (x). Pueden existir distintas rutas para ir de un nodo a otro, pero el objetivo es encontrar el más corto o bien el más económico si es que la ponderación representa un costo.

Algoritmo de Dijkstra

Seleccionar la ciudad origen (a).1.-

Page 36: Capítulo 7: Grafos Capítulo 7: Grafos Capítulo 7: Grafos Capítulo 7: Grafos Autor: José Alfredo Jiménez Murillo

seleccionadosactual…. d c b aIteración

Colocar en la matriz la distancia que existe de la ciudad origen a ella misma. (Cuando se trata de encontrar la distancia de una ciudad a ella misma considerar que es 0). A todas las demás columnas se les coloca ∞ como distancia.

3.-

….∞∞∞00

seleccionadosactual…. d c b aIteración

Usar una matriz que tenga como columnas el número de iteración, una columna para cada nodo (a,b,c,d,….), la columna actual que se utilizará para indicar el vértice que se seleccione en cada iteración y una columna seleccionados para registrar a los vértices que se van seleccionado en el proceso, como se muestra en la siguiente tabla.

2.-

Grafos ponderados

Page 37: Capítulo 7: Grafos Capítulo 7: Grafos Capítulo 7: Grafos Capítulo 7: Grafos Autor: José Alfredo Jiménez Murillo

Iteración a b c d …. actual seleccionados

0 0 ∞ ∞ ∞ …. a a

Colocar en la columna actual el vértice que tenga la distancia más corta de entre todos los nodos. (Es obvio que en esta primera iteración es el nodo origen.) En la columna seleccionados registrar dicho nodo escogido para ya no volverlo a elegir. (En nuestro caso le colocamos a esta distancia en negrita y subrayado.)

4.-

Registrar en la columna de cada uno de los nodos la distancia más corta que resulta de sumar la distancia registrada en el nodo actual + distancia a los vértices adyacentes a él y seleccionar la distancia más corta cuyo nodo aún no esté seleccionado de esa fila de la matriz. Suponer que d1 > d2, por lo tanto la matriz será:

5.-

Iteración a b c d …. actual seleccionados

0 0 ∞ ∞ ∞ …. a a

1 0 d1 d2 ∞ ….

Grafos ponderados

Page 38: Capítulo 7: Grafos Capítulo 7: Grafos Capítulo 7: Grafos Capítulo 7: Grafos Autor: José Alfredo Jiménez Murillo

Si el nodo seleccionado tiene una distancia diferente de ∞ que es menor o igual a la que se obtiene de sumar la distancia registrada en la columna del nodo actual + la distancia de ese nodo actual a los nodos adyacentes a él dejarla tal como está, en caso contrario cambiarla por la nueva suma.

Registrar en la columna actual el vértice que tenga la distancia más corta de entre todos los nodos y que no haya sido seleccionado hasta ahora. Además de anotar en la columna seleccionados dicho nodo para ya no volverlo a elegir.

6.-

Iteración a b c d …. actual seleccionados

0 0 ∞ ∞ ∞ …. a a

1 0 d1 d2 ∞ …. c a,c

Si ya están todos los vértices seleccionados finalizar. En caso contrario regresar al paso 5.

7.-

Grafos ponderados

Page 39: Capítulo 7: Grafos Capítulo 7: Grafos Capítulo 7: Grafos Capítulo 7: Grafos Autor: José Alfredo Jiménez Murillo

k

f1

4

4

3

3

1

21

42

2 d

b

ae

c

g h i j

2

4

21

223

2

Encontrar la ruta más corta para ir de la ciudad origen (a) a las ciudades restantes.

Ejemplo

Ite a b c d e f g h i j k act seleccionados

0 0 ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ a a

1 0 4 ∞ ∞ 1 ∞ 3 ∞ ∞ ∞ ∞ e a,e

2 0 3 4 ∞ 1 5 3 3 ∞ ∞ ∞ b a,e,b

3 0 3 4 ∞ 1 5 3 3 ∞ ∞ ∞ g a,e,b,g

4 0 3 4 ∞ 1 5 3 3 ∞ ∞ ∞ h a,e,b,g,h

5 0 3 4 ∞ 1 4 3 3 5 ∞ ∞ c a,e,b,g,h,c

6 0 3 4 5 1 4 3 3 5 ∞ ∞ f a,e,b,g,h,c,f

7 0 3 4 5 1 4 3 3 5 6 ∞ d a,e,b,g,h,c,f,d

8 0 3 4 5 1 4 3 3 5 6 8 i a,e,b,g,h,c,f,d,i

9 0 3 4 5 1 4 3 3 5 6 8 j a,e,b,g,h,c,f,d,i,j

10 0 3 4 5 1 4 3 3 5 6 8 k a,e,b,g,h,c,f,d,i,j,k

Ejemplo:

Para ir de a a j la distancia mínima es 6. Para ir de a a k la distancia es 8.

Page 40: Capítulo 7: Grafos Capítulo 7: Grafos Capítulo 7: Grafos Capítulo 7: Grafos Autor: José Alfredo Jiménez Murillo

Sea G(V,A) un grafo y sea C un conjunto de colores. La coloración de los vértices V del grafo usando un color del conjunto C se encuentra dada por la función.

Coloración

f: VC Si v1,v2 V adyacente entonces f(v1) ≠ f(v2)

Esto implica que cuando se lleva a cabo la coloración en vértices de un grafo, cada par de vértices adyacentes v1 y v2 del grafo deberán estar iluminados con un color diferente.

Número cromático

Es el número mínimo de colores con que se puede colorear un grafo G cuidando que los vértices adyacentes no tengan el mismo color. El número cromático se indica de la siguiente manera:

X (G)

Page 41: Capítulo 7: Grafos Capítulo 7: Grafos Capítulo 7: Grafos Capítulo 7: Grafos Autor: José Alfredo Jiménez Murillo

La coloración de grafos es un problema NP-Computable, esto significa que no hay procedimientos eficientes para llevar a cabo esta tarea, sin embargo existen métodos aproximados que pueden dar buenos resultados. Uno de ellos es:

Seleccionar el vértice de mayor valencia v e iluminarlo con un color cualquiera del conjunto C.

Colorear los vértices adyacentes al vértice v verificando que no existan vértices adyacentes del mismo color. En caso de ser necesario llevar a cabo intercambio de colores con la finalidad de usar la menor cantidad de ellos. Si ya están coloreados todos los vértices del grafo finalizar, en caso contrario continuar con el paso 3.

Seleccionar el vértice v de mayor valencia que ya esté coloreado y que todavía tenga vértices adyacentes sin colorear. Regresar a paso 2.

1)

2)

3)

Se recomienda colorear del mismo color tantos vértices como sea posible e iluminar al mismo tiempo los vértices que compartan nodos vecinos.

Coloración

Page 42: Capítulo 7: Grafos Capítulo 7: Grafos Capítulo 7: Grafos Capítulo 7: Grafos Autor: José Alfredo Jiménez Murillo

Encontrar el número cromático del siguiente grafo G.

Ejemplo

e

f

G

d

b

a

c

g

h

i

j

f

G

d

b

a

e

c

g

h,1

i

j

e

f,3

G

d,3

b

a

c,2

g,2

h,1

i

j,2

Paso 1:

Paso 2:

Paso 3:

f,3

G

d,3

b

a

c,2

g,2

h,1

i

j,2

Vértice seleccionado

e

f,3

G

d,3

b,3

a,1

c,2

g,2

h,1

i

j,2

Paso 2:e

Page 43: Capítulo 7: Grafos Capítulo 7: Grafos Capítulo 7: Grafos Capítulo 7: Grafos Autor: José Alfredo Jiménez Murillo

f,3

G

d,3

b,3

a,1

c,2

g,2

h,1

i,1

j,2

Paso 2:e,1

X(G) = 3

El número cromático es por lo tanto:

f,3

G

d,3

b,3

a,1

c,2

g,2

h,1

i

j,2

Paso 3:e

Vértice seleccionado

Ejemplo

Page 44: Capítulo 7: Grafos Capítulo 7: Grafos Capítulo 7: Grafos Capítulo 7: Grafos Autor: José Alfredo Jiménez Murillo

Características del número cromático

Un grafo G tiene número cromático X(G) = 1 si y sólo si no tiene aristas.

c,1Ya que un vértice sólo puede iluminarse de un solo color

1)

El número cromático para un camino o un ciclo de longitud 2 es X(G) = 2 ya que siempre se podrán alternar los colores.

2)

c,1 d,2

X (G) = 2

b,2a,1 c,1

Page 45: Capítulo 7: Grafos Capítulo 7: Grafos Capítulo 7: Grafos Capítulo 7: Grafos Autor: José Alfredo Jiménez Murillo

Aplicaciones de los grafos

- Redes (carreteras, telefónicas, eléctricas, de computadoras, etc.)

- Optimización de los recursos.

- Sistemas de información.

- Reconocimiento de patrones.