grafos y aplicaciones

7/30/2019 Grafos y aplicaciones

1/41

ALGEBRA Y MATEMTICA DISCRETA

FACULTAD DE INFORMTICA

ULPGC

Profesor: Jos M. Pacheco Castelao

Curso 2009-2010

Parte 3: Grafos y Aplicaciones

AyMD 09-10 Grafos yAplicaciones

11


2/41

Qu es un GRAFO?

Un GRAFO es la abstraccin matemtica de uncableado que conecta diversos aparatos, o deun recorrido con diferentes estaciones.

Para definir un grafo se necesitan: un conjunto

Vde objetos (los vrtices del grafo), y unsubconjunto arbitrario de todas las posiblescombinaciones binarias sin repeticin de losvrtices. Cada pareja de vrtices que hayamos

elegido recibe el nombre de arista del grafo. Elconjunto de todas las aristas se denota porE.

Orden del grafo:

Nmero mximo posible de aristas en un grafo:2

Si , el grafo es completo. El grafo2

completo con vrtices se escriben

V n

n

nE

n K

=

=

Por tanto, un grafo se define como el par deconjuntos G = (V,E). El nmero de vrtices es

el orden del grafo. Si el grafo contiene todaslas aristas posibles, decimos que es completo.Puesto en frmulas, tendremos:


22


3/41

Cmo representar un grafo? (1)

El modo ms simple y habitual es dibujar un conjunto de puntos (los vrtices), yrepresentar mediante segmentos de recta o arcos de curva las aristas:

He aqu un grafo con 6 vrtices y 5 aristas. No es un grafo

completo. Si definimos un grafo conexo como aqul dondehay por lo menos un camino entre cada dos vrtices[veremos la definicin de camino un poco ms adelante],observamos que ste no lo es: Hay un grupo de slo dosvrtices unidos por una arista, pero aislado del resto delgrafo. Diremos que se trata de un grafo no conexo.

5Este otro s es un grafo completo, pues n=5 y E 10 .

2

Adems, como es completo, automticamente es conexo.

= =

NOTA: La definicin que usamos es la de grafo simple: Cada dos vrtices definen como mximouna arista, y no hay arista alguna cuyo principio y final sea un mismo vrtice.

33AyMD 09-10 Grafos yAplicaciones


4/41


La representacin numrica de un grafo necesita nombrar los vrtices de alguna manera.Lo habitual es numerarlos, con lo que se puede conseguiruna descripcin matricial delgrafo, adecuada para su tratamiento algebraico o informtico.

Cuando dos vrtices est conectados por una arista, se lesllama adyacentes. Por ejemplo, en el grafo adjunto, 1 y 3 sonadyacentes, pero 1 y 2 no lo son. Podemos representar enuna tabla la adyacencia entre los vrtices

La tabla sugiere definir la MATRIZ DE ADYACENCIAdel grafo de la siguiente forma: Es una matriz

1 si los vrtices , son adyacentes

0 si no lo son

0 0 1 00 0 1 1

En el ejemplo:1 1 0 1

0 1 1 0

ij

n n

i jA a

A

= =

=

1

2

4

3


44

ady1 2 3 4

1 0 0 1 0

2

0 0 1 13 1 1 0 1

4 0 1 1 0

Tabla / matriz de adyacencia:Simtrica y 0s en la diagonal


5/41


Si tambin se asignan nombres a las aristas se obtiene otra descripcin matricial del grafo.

La relacin de incidencia: Un vrtice y una arista sonincidentes cuando el vrtice es alguno de los extremos de la

arista. Por ejemplo, en el grafo adjunto, 1 y e son incidentes,pero 1 y b no lo son. Podemos representar en una tabla laincidencia entre los vrtices y las aristas:

1

4

3d

c b

a

e

2

La tabla sugiere definir la MATRIZ DE INCIDENCIA

del grafo de la siguiente forma: Es una matriz1 si el vrtice , y la arista son incidentes

0 si no lo son

0 0 1 0 1

1 0 0 1 0En el ejemplo:

1

ij

n m

i jB b

B

= =

=1 1 0 0

0 1 0 1 1

inc a b c d e

1 0 0 1 0 1

2 1 0 0 1 0

3 1 1 1 0 0

4 0 1 0 1 1

Tabla / matriz de incidencia



6/41

El ancho de banda de la matriz de adyacenciaLa matriz de adyacencia de un grafo depende de la numeracin de los vrtices (el orden enque se consideran) . Ello tiene importancia a la hora de almacenar la descripcin del grafo enun fichero. La idea bsica es que cuanto ms se parezca una matriz a una matriz diagonal,menos espacio se necesitar para guardarla.

010010

101100

010101

011010

100101001010

:esadyacenciadematrizla

numeracinestaconejemplo,Por

1

4

5

3


66

2

6

6

4

3

001001

001101

110100

011010

000101110010

:esmatrizla

otra,estaconPero

La primera matriz es ms diagonal que lasegunda. Su ancho de banda

5El problema de numerar losvrtices de un grafo paraminimizar el ancho de bandaes MUY complicado

1

2

es 4, frente 5 en laotra. El ancho de banda es la mayor distancia de ladiagonal a la que podemos encontrar un 1, medidaen vertical u horizontal.


7/41

El grado de los vrtices

El nmero de aristas que concurren en un vrtice se llamagrado del vrtice y lo

escribiremos comog(v). Si un vrtice est aislado, se define su grado como 0.La suma de los elementos de cada una de las filas o columnas de la matriz deadyacencia del grafo es el grado del vrtice cuyo nmero es el de la fila o columna. Enla matriz de incidencia, los grados de los vrtices son las sumas por filas. El primer

resultado sobre grados es el siguiente:TEOREMA: La suma de los grados de todos los vrtices de un grafo es igual aldoble del nmero de aristasLa DEMOSTRACIN es simple: Elijamos un vrtice cualquiera y apuntemos su

grado. Pasemos a otro vrtice. Si es adyacente al anterior, al apuntar su grado yahabremos contado dos veces la arista de conexin con el primero, si no, continuamos:El resultado se obtiene repitiendo el proceso hasta haber pasado por todos los vrtices yhaber contado, por tanto, dos veces cada arista..Corolario (un corolario es un resultado que se deduce con facilidad de un teorema):

El nmero de vrtices de grado impar en un grafo es parPara verlo basta con observar que la suma de todos los grados es par, y que se componede la suma de los grados de los vrtices de orden par (que es par) y de la suma de losgrados de los vrtices de orden impar. Como esta ltima cantidad tiene que ser par, el

nmero de vrtices de orden impar es obligatoriamente par.77AyMD 09-10 Grafos y

Aplicaciones


8/41

Grafos bi- y multipartitos

En problemas relacionados con el emparejamiento de objetos aparece el concepto degrafo bipartito. Se llama as a aquellos grafos cuyo conjunto de vrtices sedescompone en dos subconjuntos disjuntos, de forma que los dos extremos decualquier arista se hallen en distinto subconjunto.

,( , )

V A B A Buv E u A v B

= =

La primera figura muestra un grafo bipartito.A={1,4} yB={2,3}. Un grafo bipartito no puede ser completo en elsentido habitual de la palabra, excepto si slo tiene dosvrtices y una arista.

1

4

3,

Si y , el nmero mximo de aristas de ungrafo bipartito es . A los grafos bipartitos con todas

las aristas posibles se les llama

y se escriben n m

A n B mnm

bipartitos completos

K

= =

2

En la segunda figura tenemos un grafo tripartito, conA={1,4}, B={2,3} y C={5,6} Qu ms hace falta paradefinir exactamente un grafo tripartito, adems de los tresconjuntos disjuntos de vrtices?

1

4

32

5

6 88AyMD 09-10 Grafos yAplicaciones


9/41

Caminos y circuitos en un grafo

Cuando se trabaja con grafos, un problema tpico es intentar recorrer de modoordenado un conjunto de aristas o de vrtices. Para formalizar esta idea necesitamosalgunas definiciones.Un CAMINO es una sucesin de vrtices, todos diferentes, tales que cada dosconsecutivos determinan una arista del grafo. Si permitimos que el ltimo vrtice

coincida con el primero, tenemos un CIRCUITO, o camino cerrado. La longitud de uncamino es el nmero de sus aristas.

{ }

{ }

sC

vvvvCsW

EvvvvvW

s

iis

=

==

= +

)(long

,,...,,:Circuito1)(long

,,...,,:Camino

121

121

{1,3,4,2} es un camino, de longitud 3, y {1,3,4,1} uncircuito, tambin de longitud 3.1

4

3

d

c b

a

e

299AyMD 09-10 Grafos y

Aplicaciones


10/41

LosHipercubosEl hipercubo de dimensin kes un grafo cuyos vrtices son las variaciones con repeticin

de los dos elementos {0,1} tomados de ken k. Las aristas estn definidas por pares devrtices cuyas descripciones slo se diferencien en un dgito binario. Por ejemplo, en elhipercubo de orden 3 los vrtices 110 y 000 no estn conectados por una arista. As pues:

H(1): V= {0, 1},E={0-1}H(2): V= {00,01,10,11},E={00-01, 00-10, 01-11, 10-11}H(3): V= {000,001,010,100,110,101,011,111},

H(3)

Vrtice con n impar de 1s

Vrtice con n par de 1s

2

1

El grado de los vrtices de ( ) es siempre .

El nmero de vrtices de ( ) es = 2 .

El nmero de aristas es 2 , pues:

2 ( ) 2 .

k

kk

k

v V

H k k

H k VR

k

E g v k V k

= = =

H(2)

H(1)



11/41

Distancias en un GrafoSi u y v son dos vrtices de un grafo, llamaremos distancia entre ellos a la menor de las

longitudes de los posibles caminos que los conecten. Si no se pueden conectar por uncamino, diremos que la distancia entre ellos es infinita.El dimetro de un grafo es la mayor de las posibles distancias entre sus vrtices. Si elgrafo no es conexo, su dimetro es infinito.


1111

El dimetro de ( ) esH k k

Dos vrtices a distancia 1



Dos vrtices infinitamente lejanos


12/41

Teorema de caracterizacin de grafos bipartitos (1)

Qu es un teorema de caracterizacin?

Por regla general, en Matemticas un teorema es un frase del tipo siA,entoncesB , AB.

La parteA se denomina hiptesis, y laB, tesis.

El proceso mental por el cual nos convencemos de la verdad de la frase sellama demostracin del teorema.

Si un teorema AB es verdadero, entonces decimos queA es condicin

suficiente paraB, y queB es una condicin necesaria deA.

La expresinAB es la recproca deAB. Lo habitual es que slo una de lasdos expresiones sea verdadera, pero cuando ambas lo son, lo cual escribimos AB,entonces tenemos un teorema de caracterizacin. Estos teoremas se suelen formular de lamanera A es condicin necesaria y suficiente deB, o A si y slo siB, y una vezdemostrados permiten utilizar las propiedadesA yB de forma intercambiable endeducciones posteriores.



13/41

Teorema de caracterizacin de grafos bipartitos (2)Un grafo es bipartito si y slo si todos los posibles circuitos que hay en l son de longitud

par [Ntese la estructuraAB].Habr que demostrar que bipartito ciclos de longitud par, y despus, que ciclos delongitud par bipartito

La primera demostracin es sencilla: Si un circuito comienza y acaba en un vrtice de unade las componentes del conjunto total de vrtices V, las aristas que lo forman conectan lasdos componentes consecutivamente. Por tanto su longitud es par.

La segunda es algo ms complicada. La idea de la demostracin es que tomemos un

vrtice cualquiera v, y encontraremos las dos componentes de Vas:{ }

{ }

, donde vrtices a distancia impar de , y

vrtices a distancia par de .

V I P I v

P v

= =

=

H(3) es un grafo bipartito:P= {rombos},I= {crculos}

NOTA: Todos losH(k) son bipartitos

v



14/41

Otro teorema de caracterizacin de grafos bipartitosColorear un grafo consiste en adjudicar un color a cada vrtice, con la condicin de que

no haya nunca dos vrtices adyacentes del mismo color. Se plantea el siguienteproblema: Cul es el nmero mnimo de colores necesario para colorear un grafo?Ese nmero se llama nmero cromtico del grafo.

1

4

3G

1

2

4

3

G

5

2

1, 4: Rojo. 2, 3: Negro

Nmero cromtico 2

Rombos: Rojo. Crculos: Negro

Nmero cromtico 2

1, 3: Rojo. 2, 4: Negro. 5: Azul

Nmero cromtico 3


TEOREMA: Un grafo es bipartito si y slo si su nmero cromtico es 2 [Ntese denuevo la estructuraAB].

Habr que demostrar que bipartito nmero cromtico 2, y despus, que nmero

cromtico 2 bipartito: Son un par de ejercicios.1414


15/41

Subgr

afos

Dado un grafo ( , ), otro grafo ' ( ', ') es un subgrafo de si

' y ' , de forma que las aristas en ' sean compatibles con

la eleccin de los vrtices que forman '. Si ' es el conjunto de to

G V E G V E G

V V E E E

V E

= =

das lasaristas que haba en entre los vrtices de ', se dice que ' es un subgrafo

inducido.

G V G

1

4

3G

1

4

3

1 4

3 222

Otro subgrafo GUn subgrafo G

1

4

3

1

4

3

1

32 2

Un subgrafo inducido ste no es un subgrafo ste tampoco1515AyMD 09-10 Grafos y

Aplicaciones


16/41

Grafos isomorfos (1)(del griego iso = igual + morphos = forma)

Dados dos grafos ( , ) y ' ( ', '), y ' son isomorfos si se puede

establecer una correspondencia biunvoca : ' que asocie los vrtices de

con los de ' y conserve las relaciones de incidencia

G V E G V E G G

f G G

V V

= =

. En frmulas:' , ' , y si es una arista en , entonces ( ) ( ) lo es en '.V V E E uv G f u f v G= =


1616

1

2 3

4

G

5

f(2)G

f(3)

f(5)f

f(1)

f(4)

Dos grafos isomorfos y el isomorfismo f entre ellos


17/41

Grafos isomorfos (2)Dados dos grafos isomorfos ( , ) y ' ( ', '), de las relaciones

' , ' , "si es una arista en , entonces ( ) ( ) lo es en '",se deduce inmediatamente que para todo , el grado de es ig

G V E G V E

V V E E uv G f u f v G

v V v

= =

= = ual al de

( ). Por tanto, tambin se conservan

Pertenecen a la clase de las de los gPropieda rdes Topolgica os,s af

:f v ciertas relaciones espaciales


1717

1

2 3

G

5

4

f(1)

f(4)

f(5)

f(2)

G

f(3)

f

En estos dos grafos isomorfos se observa que 5 yf(5) tienen grado 4, y que tanto 5comof(5) tienen dos vrtices de grado 2 y otros dos de grado 3 a distancia 1.


18/41

rboles (1)Un grafo ( , ) que sea conexo y no contenga circuitos se llama .

Si ( , ) es un grafo cualquiera, y ' ( ', ') un subgrafo tal que '

y adems es un rbol, diremos que '

G V E rbol

G V E G V E V V

G es un rbol generado

=

= = =

.r de G


1818

Posibles rboles con 1, 2, 3, 4 y 5 vrtices. Comprobar que estn todos. Cuntos hay con 6?

Los rboles son la base terica de los algoritmos de bsqueda, de ah suimportancia en Informtica.

Teoremas de caracterizacin de rboles:

I. G es un rbol si y slo si entre cada dos vrtices existe slo un camino (sin aristasrepetidas, claro)

II. G es un rbol si y slo si es conexo y el nmero de aristas es igual al de vrticesmenos 1


19/41

rboles (2)Un corolario del Teorema II es: "Si ( , ) es un rbol, entonces ( ) 2 2".

Teorema de existencia: "Si ( , ) es un grafo conexo, entonces posee un rbol generador".v V

G V E g v V

G V E

= =

=

La demostracin del Teorema de existencia consiste en el diseo de un algoritmoadecuado:

I. Inicializacin: Partimos de un vrtice cualquiera siguiendo un camino.

II. Recurrencia.

1. Si conseguimos pasar por todos los vrtices sin repetir ninguno, ya tenemos el rbol.

2. En caso contrario, quedar al menos un vrtice fuera del camino, pero por serconexo el grafo, existir alguna arista que conecte un vrtice del camino con aqul.Este es el principio de una rama del rbol. Si siguindola (sin repetir ningn vrtice)se acaban los vrtices del grafo, hemos terminado. Si no, volvemos 1.

Un problema difcil es saber cuntos rboles generadores puede tener un grafo. Para el casode un grafo completo tenemos el siguiente Teorema:

2"El nmero de rboles generadores de un grafo completo con vrtices es ".nn n


1919


20/41

rboles (3): buscando rboles generadores


2020

1

2 3

G

4

5

1

2 3

5

Un caso fcil 4

vv

G

Un caso menos fcil

Camino Rama 1 Rama 2


21/41

Algoritmos de bsqueda (1)Motivacin: Imaginemos buscar una palabra en un diccionario (de los de papel).

Comenzamos por la primera letra, despus miramos la primera ms la segunda, y as hastahallar finalmente la palabra completa. Acabamos de ver un ejemplo de algoritmo debsqueda. El diccionario se puede equiparar a un grafo con un primer grupo de 26 (27) vrtices numerados desde A1 hasta Z1. De cada uno de esos vrtices parten otras tantas

aristas hacia vrtices que volvemos a numerar desde A2 hasta Z2 y as sucesivamente. Elgrafo obtenido es un rbol. Hallar una palabra consiste en recorrer la rama adecuadadel rbol.

Diccionario

A1 B1 Y1 Z1

B2 Y2 Z2

E3 Y3 Z3

A2

A3

Bsqueda de la palabra bye


2121


22/41

Algoritmos de bsqueda (2)El ejemplo anterior era un caso sencillo de bsqueda de un vrtice en un grafo. Result fcil

porque el diccionario ya era un rbol. Si el grafo tiene una estructura ms complicada, labsqueda comienza por encontrar subgrafos que sean rboles. Hay dos estrategiasprincipales para ello: La primera es la bsqueda horizontal o a lo ancho, y la segunda, labsqueda vertical o en profundidad. Presentemos ambas sobre un mismo ejemplo.

a

b

c f

h En el algoritmo a lo ancho comenzamos en a yconstruimos una primera capa con todos losvrtices que se hallan a distancia 1 de l. A

continuacin hacemos lo mismo a partir de cada unode los vrtices de esta capa, y as sucesivamente,hasta agotar el grafo. El resultado es:

g

a

b d h

g

ed


2222

c e

f

Dist. 1

Dist. 2

Dist. 3


23/41

Algoritmos de bsqueda (3)

En el algoritmo en profundidad, comencemos tambin en a y construyamos una primerarama con vrtices sucesivos que se hallen a distancia 1, 2, 3, etc., de l. Acabada esta rama,

por orden y a partir de cada uno de los vrtices de ella procederemos de igual modo, hastaagotar el grafo. El resultado es:

aa

f

h

b geb

gc c

ed fd h

NOTAS:

1. Para ser estricto, habra que probar la correccin de los algoritmos.

2. El algoritmo puede no ser nico. Entonces se plantea el problema de hallar el algoritmo ptimo.

3. Obsrvese que el algoritmo en profundidad sigue exactamente la demostracin de existencia de

rboles generadores.AyMD 09-10 Grafos y

Aplicaciones2323


24/41

Grafos orientados o dirigidosDado un grafo cualquiera G, se puede considerar que la arista uv que conecta dos vrtices

ha sido dotada de un sentido concreto: Puede recorrerse de u v, al revs. Una vezseleccionado un sentido en todas las aristas, el grafo Gpasa a ser un grafo orientado odirigido (ver NOTA abajo).

( , ) : grafo; ( , ) : grafo orientado

Orden del grafo orientado:

Nmero mximo de aristas del grafo:2

Las aristas de un grafo dirigido son

variaciones binarias de sus vrtices, pero

slo

G V E G V E

V n

n

n

=

G G

son posibles la mitad de ellas como

mximo, pues cada arista tiene un nico

sentido.


2424

1

2 3

5

4

GG

NOTA LINGSTICA: La expresin grafo dirigido es equvoca en castellano. Locorrecto es decir grafo orientado o con sentidos en las aristas. En una lnea (recta)hay una sola direccin, pero dos sentidos u orientaciones.

G d i f i d ( )


25/41

Grados y matrices en grafos orientados (1)En un grafo ordinario, el grado de un vrtice es el nmero de aristas que concurren en l.

Al dotar de sentidos a las aristas, algunas de las que concurren en el vrtice apuntarn hacial, y las restantes al contrario. El nmero de aristas que apuntan hacia el vrtice es el gradode entrada, y el nmero de las que salen de l, el grado de salida del vrtice. En frmulas:


2525

Grado de entrada de : ( )Grado de salida de : ( )

Grado ordinario de : ( ) ( ) ( )

Si ( ) ( ), es un vrtice

Si ( ) ( ), es un vrtice

v g vv g v

v g v g v g v

g v g v v sumidero

g v g v v fuente

+

+

+

= +

=

=

1

2 3

5

4

GG

En el grafo de la figura, el 1 es un sumidero y el 4 una fuente

La matriz de adyacencia,A, de un grafo orientado es la matriz del grafo sin tener encuenta los sentidos de las aristas. Sin embargo, la matriz de incidencia,B, s ha de tener encuenta los sentidos de las aristas.


26/41

Grados y matrices en grafos orientados (2)

La suma por columnas es siempre 0. El nmerode elementos no nulos de cada fila es el grado

(ordinario) del vrtice que define la fila.

La MATRIZ DE INCIDENCIA de un grafo orientado

se define de la siguiente forma:

Es una matriz de orden donde:

1 si la arista apunta hacia el vrtice0 si la arista no incide con elij

B n m

j i

b j

+ = vrtice

1 si la arista sale del vrtice

1 1 0 0 0 0 00 1 1 0 0 1 0

En el ejemplo: 0 0 1 1 0 0 1

0 0 0 1 1 0 0

1 0 0 0 1 1 1

i

j i

B

=

1

2 3

4

5

G

G

a

b

c

e

fg

Si es la m atriz definida por:

( ) si

0 si

En tonces se cumple la ecuacin:

(permite deducir de )

ij

i

ij

t

ij

g

g v i jg

i j

BB A g

A B

==

+ =

d


2626


27/41

Caminos y circuitos en grafos orientadosLas definiciones de camino y circuito se trasladan directamente a los grafos orientados.

Slo hay que exigir que en los vrtices del camino sean compatibles los sentidos de lasaristas: Si una entra, la otra sale. En los extremos del camino, si no es un circuito, unasale y la otra entra. En la figura, 4321 es un camino dirigido ente 4 y 1. Sin embargo, enese grafo no hay circuitos orientados.

Un grafo orientado se llama acclico si en l no hay circuitos orientados. El de la figuraes acclico.

Un grafo orientado se llamafuertemente conexo si en l existe un camino orientadoentre cualquier par de puntos. Si es fuertemente conexo, es tambin conexo. El de lafigura no es fuertemente conexo (pero s conexo), pues desde el vrtice 1 no se puedellegar a ningn otro siguiendo un camino orientado


2727

1

2 3

5

GG

a

b

c

e

fg

TEOREMA sobre grafos acclicos: En un grafoacclico siempre hay al menos un vrtice fuente y uno

sumidero

Demostracin: Intntenla!

Los grafos acclicos son modelos apropiados para

problemas de transporte y distribucin

4

d

M lti f (1)


28/41

Multigrafos (1)Hasta ahora slo se han estudiado grafos en los que slo se permite una nica arista

entre vrtices adyacentes, orientada o no. Tampoco se han permitido circuitos formadospor una nica arista.

Un multigrafo es un grafo G(V,E) en el que se permite la existencia de ms de una aristaentre vrtices adyacentes y ciclos consistente en una sola arista.

La definicin de multigrafo orientado es inmediata: Todas las aristas tienen adjudicadauna orientacin.

Un multigrafo (izq) y un multigrafo orientado (dcha)


2828

M lti f (2) G d t i


29/41

Multigrafos (2): Grados y matrices

La matriz de adyacencia de un multigrafo se define como en el caso de un grafo simple,

pero en lugar de un 1 se pondr el nmero de aristas paralelas si hay ms de una entrevrtices incidentes. Los circuitos que constan de una sola arista cuentan como dosaristas.

1

5


2929

23

4

1

0 2 0 0 02 0 1 0 0

0 1 0 2 1

0 0 2 0 0

20 0 1 0

A

=

a

cd

e

f

g

1

1 1 0 0 0 0 0

1 1 1 0 0 0 0

0 0 1 1 1 1 0

0 0 0 1 1 0 0

0 0 1 20 0 0

B

=

b

2

0 2 0 0 0

2 0 1 0 0

0 1 0 3 1

0 0 3 0 0

20 0 1 0

A

= b

c

d

f g

h

i

2

1 1 0 0 0 0 0 0

1 1 1 0 0 0 0 00 0 1 1 1 1 1 0

0 0 0 1 1 1 0 0

0 0 0 0 0 0 1 0

B

=

a

El problema del laberinto (1)


30/41

El problema del laberinto (1)Se trata de un ejercicio sobre multigrafos orientados. Resolver un laberinto es hacer un

recorrido por un grafo, que comience y acabe en un mismo vrtice, pasando por todoslos vrtices (las veces que haga falta) y donde todas las aristas han de recorrerseexactamente una vez en cada uno de los dos sentidos posibles.


3030

El grafo de la izquierda puede recorrerse de un solo trazo, sin levantar el lpiz del papel, tal

como se muestra, sin repetir arista alguna. Sin embargo, no se sale por el punto de entrada.Para conseguirlo y as resolver el laberinto, hay que aadirle el recorrido sealado en la figuradel centro. Es inmediato comprobar que el recorrido combinado resuelve el laberinto: Seentra y sale por la esquina inferior izquierda, y todas las aristas se recorren una vez en cada

sentido (observar las flechas).

entrada

primer paso, flecha gruesa

salida entrada

= laberinto completo+

salida

primer paso, flecha gruesa, segundo y tercero , flechas de puntos

El problema del laberinto (2)


31/41

El problema del laberinto (2)Algoritmo de resolucin del problema del laberinto:

1. Tomar un vrtice de partida u.

2. Al recorrer una arista uv y llegar a un vrtice v, anotar la arista.

3. Slo se podr recorrer la arista vu (la misma del paso 2 en sentido contrario) tras

haber pasado por todas las dems aristas que confluyen en v.

Teorema: El algoritmo es correcto. En efecto, por definicin en todo vrtice del laberintoel grado de entrada ha de ser igual al grado de salida. En particular, ello se consigue si todas

las aristas que confluyen en un vrtice aparecen en l en los dos sentidos: llamemosadecuados a los vrtices que cumplen esta propiedad (observacin: los grados de entrada ysalida de un vrtice tambin seran iguales si elegido un par de aristas, una fuese de entrada,otra de salida y las restantes con ambos sentidos). Si en el laberinto hay vrtices no

adecuados, sea v el primero que encontramos en el recorrido y sea uv la arista por la quellegamos a v y que no aparece recorrida en sentido contrario. Por tanto el vrtice u tampocoes adecuado, pero ello es imposible porque v era el primero del recorrido con esa propiedad:contradiccin! Luego todos los vrtices del laberinto son adecuados y el algoritmo escorrecto.


3131

Grafos ponderados y optimizacin


32/41

Grafos ponderados y optimizacin

Un problema tpico de optimizacin sobre grafos se puede formular como hallar el

camino mnimo entre dos vrtices, donde la palabra mnimo puede tener diversossignificados. Por ejemplo, si las aristas representan carreteras y los vrtices ciudades, se

puede considerar mnimo como el de menor kilometraje, o aqul donde el gasto decombustible es menor, o por dnde menos semforos existen, etc. En cualquier caso,

el modelo matemtico es un grafo en el cual a cada arista se le dota de una ponderacino peso que representa el gasto de recorrerla. Ello puede hacerse en grafos de cualquiertipo de los vistos hasta ahora.

{ }1 21

11

En frmulas, un grafo ( , ) es ponderado

cuando hay una aplicacin : que

asocia a cada arista su "peso" ( ).

Si , , ..., es un camino, el "peso"

del camino es ( ) ( ). Si t

k

k

i i

i

G V E

p E

uv p uv

P v v v

p P p v v

+

+=

=

=

\

odos

los pesos son iguales 1, el peso del camino

coincide con su longitud.

1

3

12

3

4

1


3232

El l it d Dijk t (1)


33/41

El algoritmo de Dijkstra (1)

El problema de obtener el camino de peso mnimo entre dos vrtices cualesquiera u y vse puede resolver mediante un algoritmo debido al matemtico holands Dijkstra.

Idea del algoritmo: A partir del grafo ponderado ( , ) vamos generando subgrafos (caminos)

a partir de un vrtice inicial, aadiendo de uno en uno vrtices y aristas, eligiendo el paso siguientetras

G V E

{ }0 0 0 0

calcular el peso de los caminos que han ido apareciendo y quedarnos con el menor.

Algoritmo:

I. Inicializacin. Vrtice inicial: . Subgrafo inicial ( , ), con ( ) 0.

II. Recurrencia. Si hemos ll

v G v p v =

{ } { }0 1 1 2egado al subgrafo (camino) ( , ,..., , , ,..., ), puedenpasar dos cosas:

1. 1. Entonces, el problema est resuelto.

2. En caso contrario, para cada par de vrtices ( , ), con y

j j j j

i

V G v v v e e e

j V

v w v V w V

=

=

0

, calculemos la expresin( ) ( ) ( ), donde ( ) es el peso del tramo del camino entre y . Elijamos *

y *de manera que ( * *) sea el menor posible, y aadamos al camino el nuevo v

i

j

j

F vw p v p vw p v V v v v

w F u w G

= +

1

rtice

* . Despus, volvemos al paso 1.jw v +=


3333



34/41


Consideremos un par de ejemplos, con un mismo grafo, para ilustrar el algoritmo de

Dijkstra: Notemos que el algoritmo construye un rbol generador, a lo largo de cuyasramas se van obteniendo los caminos mnimos desde el vrtice inicial hasta cualquierotro.


3434

331

1

4

34

2

1caminos mnimos

1

331

1

4

34

2

inicio

2

5inicio

2

5



35/41

El algoritmo de Dijkstra (3)Vamos a demostrar que este algoritmo construye el camino mnimo. La idea es ver que

si encontramos un camino mnimo por cualquier otro mtodo, ste ser ms pesado queel dado por el algoritmo. La demostracin es como sigue:

0

0

Consideremos la construccin indicada en la etapa 2 del algoritmo, y sea [( ,..., *)] el

peso del camino hallado. Sea ahora otro camino mnimo entre y *, que contenga por

lo menos un vrtice

p v w

P v w

w

0

. Por tanto, existir un que ser el ltimo antes de que el

camino se desve hacia . As pues, se compone de tres tramos: El camino ( ,..., ),

la arista y el camino ( ,..., *), donde lo

j jV v V

w P v v

vw w w

0

s dos subcaminos son tambin mnimos.

Luego su peso ser (ver la figura adjunta):( ) ( ) ( ) [( ,..., *)] ( ) [( ,..., *)] ( * *) [( ,..., *)]

Esto es, es tan pesado o ms que el camino de

p P p v p vw p w w F vw p w w F v w p v w

P

= + + = + =

Dijkstra.

0v 1v v v *w

w


3535

Caminos circuitos y grafos Eulerianos y Hamiltonianos (1)


36/41

Caminos, circuitos y grafos Eulerianos y Hamiltonianos (1)En un grafo tiene importancia saber si determinados recorridos son posibles o no, o si

poseen alguna propiedad especial. Veamos algunas definiciones:Un camino euleriano es aqul que recorre todas las aristas del grafo sin repetir ninguna.Si el camino es un circuito, ser un circuito euleriano. Los grafos que poseen algncircuito euleriano son grafos eulerianos.

Un camino hamiltoniano es aqul que recorre todos los vrtices del grafo sin repetirninguno. Si el camino es un circuito, ser un circuito hamiltoniano. Los grafos que

poseen algn circuito hamiltoniano son grafos hamiltonianos.


3636

fin

inicio iniciofin


Camino EULERIANO


Camino HAMILTONIANO

Grafos Eulerianos (1)


37/41


Hay problemas cuya solucin consiste en encontrar un circuito euleriano. Por supuesto,

no siempre es posible resolverlos, como se ve en la figura:

Para cerrar el circuito en la figura podemos aadir el

tramo fin inicio, pero en tal caso habremos repetidouna arista: No tenemos un circuito euleriano.

Como se ha visto antes, si permitimos que todas las aristassean reversibles esto es, pensamos el grafo como un

multigrafo- entonces s podemos encontrar un circuitoeuleriano. Se plantea, por tanto, si el problema tendrsiempre solucin en multigrafos.

Tenemos el siguiente Teorema de caracterizacin:

fininicio


ultimo, de puntos

NO ES UN CIRCUITOEULERIANO


3737



38/41

Un multigrafo es eulerianosi y slo si es conexo y todos susvrtices son de grado par

Desde luego, si en un grafo hay un circuito que pasa por todas las aristas, es conexo. El

camino, al atravesar un vrtice, entra por un lado y sale por otro, luego el grado de todos

los vrtices es par. Esto demuestra la parte A B del teorema.

Para ver la parte A B, sea un grafo conexo y con todos sus vrtices de grado par, yconsideremos un circuito [siempre hay circuitos: demostrarlo] que poseaP

el mayor nmero

posible de aristas. Si , ya est demostrado. Si no, podemos formar un subgrafo '

constituido por todos los vrtices del grafo original y las aristas que no estn en , observando

P V G

P

=

que por ser conexo habr un vrtice comn y ' cuyo grado (en ') es positivo y par. Ello

quiere decir que dentro de ' existe algn circuito ' basado en ese vrtice comn. Pero entonces

podemos

P G G

G P

conectar los circuitos y ' para formar uno ms largo que . Como era de longitud

mxima, obtenemos una contradiccin y el teorema queda probado.

P P P P

Escolio (forma matemtica de decir comentario): La demostracin del teorema sepuede adaptar al caso de un camino euleriano que no se cierre: Basta con permitir queslo haya dos vrtices de grado impar (principio y final del camino).


3838



39/41

G a os u e a os (3)

Algoritmo para encontrar un camino euleriano

Para la construccin necesitamos el concepto de arista puente: Se llama as a las aristastales que al borrarlas del grafo, ste pasa a ser no conexo.

{ }

0

0 1

I. InicializacinElegimos un vrtice cualquiera para comenzar.

II. Recurrencia

Supongamos construido un camino , ,..., y sea ' el subgrafo citado en el teorema,cuyos vrtices son todos los

i i i

v

V v v v G=del grafo y las aristas las que no estn en el camino. Puede ocurrir:

1. Que en estn ya todas las aristas del grafo: Entonces, fin del problema.2. En caso contrario, busquemos una arista incidenteiV

1con que nos lleve a un nuevo vrtice ,

teniendo cuidado de que esta arista no sea una "arista puente". Despus, volvamos al paso 1.i iv v +


3939

Grafos Hamiltonianos


40/41

Definicin y comentarios.

Recordemos que en un grafo hamiltoniano existe al menos un circuito que pasa portodos los vrtices sin repetir ninguno. La construccin de estos circuitos es mucho mscomplicada que la de circuitos eulerianos: Ello significa que los algoritmos de clculotardan ms en ejecutarse, aunque puedan establecerse criterios de caracterizacin.La complejidad de los grafos hamiltonianos los deja fuera del nivel de este curso.

Dos ejemplos de grafos hamiltonianosAyMD 09-10 Grafos y

Aplicaciones4040

Fechas y curiosidades


41/41

ySe suele considerar que la teora de grafos se origin con el problema de los puentes de Knigsberg, resuelto

por el suizo Leonhard Euler (1707-1783). En l se muestra la imposibilidad de un circuito euleriano en undeterminado grafo (bsquenlo en la bibliografa o en Internet).

El primer libro conocido sobre Teora de Grafos, del matemtico hngaro Dnes Knig, fue publicado por laeditorial Teubner de Leipzig en 1935 con el ttulo Theorie der endlichen und unendlichen Graphen.

Los grafos hamiltonianos se llaman as en recuerdo de William Rowan Hamilton (1805-1865), matemtico,

fsico y poeta irlands quien lo propuso por primera vez para el caso de un docecaedro.

El algoritmo de Dijkstra (pronnciese distra) se debe al holands Edsger Dijkstra (1930-2002), quien loformul el ao 1959.

D. KnigL. Euler W. Hamilton E. Dijkstra


4141

grafos y aplicaciones

Documents