Tema 1-Introduccion-2dpp.pdf

1P.Reyes

Tema 1: Introduccin a la Teora de Grafos

Nociones bsicas

temticaD

iscreta

Formas de definir un grafo

Subgrafos. Operaciones con grafos

Ma

Isomorfismo de grafos

MatemticaDiscreta

afos

P.Reyes Nociones bsicas:

Grafo: G = (V,A)V conjunto de vrtices

A conjunto de aristas

n a

la T

eora

de

Gra

E

D

A

F

B

vrticesG = (V,A)

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

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

Intro

ducc

i

Tema 1: 2

D

C

B

aristas

2MatemticaDiscreta

afos


Grafo: G = (V,A)V = {1,2,3,4,5,6}

A = {{1,2},{1,3},{1,5},{1,6},{2,4},{2,6},{3,4},{3,5}}

n a

la T

eora

de

Gra 1 2

36

1 2

3 4

5

6

Intro

ducc

i

Tema 1: 3

45

Representacin grfica Inmersin

Grafo plano

MatemticaDiscreta

afos

P.Reyes Nociones bsicas: Variantes de grafos:

{2,4} arista mltiple

n a

la T

eora

de

Gra

1

2

34

multigrafo

Intro

ducc

i

Tema 1: 4

3MatemticaDiscreta

afos


{2,4} arista mltiple

n a

la T

eora

de

Gra

1

2

34

Intro

ducc

i

Tema 1: 5

{3,3} lazo o bucle

seudografo

grafo simple (no admite aristas mltiples ni lazos)

MatemticaDiscreta

afos


1 2

3

grafo dirigido o digrafo(las aristas son pares ordenados de vrtices)

n a

la T

eora

de

Gra

45

de vrtices)

(1,2) es arista, pero (2,1) no lo es

digrafo mltiple o multigrafo dirigido (digrafo con aristas mltiples)

Intro

ducc

i

Tema 1: 6

seudo digrafo o seudografo dirigido(digrafo con aristas mltiples y/o lazos)

4MatemticaDiscreta

afos


grafo ponderado(las aristas llevan asignadas un peso)

n a

la T

eora

de

Gra

H

SE

CO

GR94

187

256

138166

JA104

99

Intro

ducc

i

Tema 1: 7

H

CA

AL

MA

125219

265

129166

256

219

MatemticaDiscreta

afos


vrtices adyacentes

v1, v2 V, v1 ~ v2 e ={v1 , v2} Aaristas incidentes

n a

la T

eora

de

Gra

1 2

36

valencia o grado de un vrtice v (v)

v1 y v2 inciden en la arista e

: V N

Intro

ducc

i

Tema 1: 8

45

(1)=4, (2)=3, (3)=3, (4)=2, (5)=2, (6)=2

vrtices pares e impares vrtice aislado

5MatemticaDiscreta

afos


Propiedades de la valencia: G = (V,A) n=|V|

1 2

36

n a

la T

eora

de

Gra

451) 0 (v) n-1

2) Un grafo no puede tener simultneamente vrtices de valencia 0 y de valencia n-1

3) La suma de las valencias de los vrtices es

Intro

ducc

i

Tema 1: 9

igual al doble del nmero de aristas:

vV

(v) = 2 |A|

(lema del apretn de manos)

MatemticaDiscreta

afos


Adyacencia en digrafos

valencia o grado de entrada( )

valencia o grado de salida( )

n a

la T

eora

de

Gra e(v)

e(1)=2, s(1)=2, e(2)=1, s(2)=1, (3)=1 (3)=2

1 2

3

s(v)

Intro

ducc

i

Tema 1: 10

e(3)=1, s(3)=2, e(4)=2, s(4)=2, e(5)=1, s(5)=0

3

45

6MatemticaDiscreta

afos

P.Reyes Nociones bsicas: Algunos grafos especiales

Grafo regular: T d l ti ( ) k ( V)

Grafo trivial: No tiene ninguna arista.

n a

la T

eora

de

Gra Grafo regular: Todos los vrtices

tienen la misma valencia.(v)=k (vV)

grafo k-valente o k-regular

Si k=n-1 se llama grafo completo (Kn)

K

K3 K4

Intro

ducc

i

Tema 1: 11

K2 K5grafo ciclo

C5

grafo camino

P3

MatemticaDiscreta

afos

P.Reyes

V1

Nociones bsicas: Algunos grafos especiales

Grafo bipartito:

n a

la T

eora

de

Gra

V2V = V1 V2 e A : e = {v1,v2} , v1 V1 , v2 V2

G = (V,A)

Grafo bipartito completo: (Kn,m)

Intro

ducc

i

Tema 1: 12

K4,2 K3,3

7MatemticaDiscreta

afos

P.Reyes Formas de definir un grafo:

G = (V,A)V={1,2,3,4,5,6}A={{1,2},{1,3},{1,5},{1,6},

{2,4},{2,6},{3,4},{3,5}}

n a

la T

eora

de

Gra

1 2

36

1 2

5

6

Intro

ducc

i

Tema 1: 13

45 3 4

MatemticaDiscreta

afos


G = (V,A)V={1,2,3,4,5,6}A={{1,2},{1,3},{1,5},{1,6},

{2,4},{2,6},{3,4},{3,5}}

1 2

3

45

6

nv vrtices, na aristas

n a

la T

eora

de

Gra 45

Lista de adyacencias o lista de listas

Lista formada por nv listas.

{{2,3,5,6},{1,4,6},{1,4,5},{2,3},{1,3},{1,2}}

Intro

ducc

i

Tema 1: 14

8MatemticaDiscreta

afos


G = (V,A)V={1,2,3,4,5,6}A={{1,2},{1,3},{1,5},{1,6},

{2,4},{2,6},{3,4},{3,5}}

1 2

3

45

6


n a

la T

eora

de

Gra 45

Matriz de adyacencia

Ad: Matriz de orden nv nv

aij = 1 si vi es adyacente a vj

0 en caso contrario

0 1 1 0 1 11 0 0 1 0 11 0 0 1 1 00 1 1 0 0 01 0 1 0 0 01 1 0 0 0 0

Ad =

Intro

ducc

i

Tema 1: 15

0 en caso contrario 1 1 0 0 0 0

MatemticaDiscreta

afos


G = (V,A)V={1,2,3,4,5,6}A={{1,2},{1,3},{1,5},{1,6},

{2,4},{2,6},{3,4},{3,5}}

1 2

3

45

6


n a

la T

eora

de

Gra 45

Matriz de adyacencia

Propiedades:

0 1 1 0 1 11 0 0 1 0 11 0 0 1 1 00 1 1 0 0 01 0 1 0 0 01 1 0 0 0 0

Ad =Es cuadrada y simtrica

La suma de cada fila (o columna) es

Intro

ducc

i

Tema 1: 16

1 1 0 0 0 0La suma de cada fila (o columna) es el grado del vrtice correspondiente

La diagonal es nula

9MatemticaDiscreta

afos


G = (V,A)V={1,2,3,4,5,6}A={{1,2},{1,3},{1,5},{1,6},

{2,4},{2,6},{3,4},{3,5}}

1 2

3

45

6


n a

la T

eora

de

Gra 45

Matriz de incidencia

In: Matriz de orden nv na

bij = 1 si vi es vrtice de la arista aj

0 en caso contrario

1 1 1 1 0 0 0 01 0 0 0 1 1 0 00 1 0 0 0 0 1 10 0 0 0 1 0 1 00 0 1 0 0 0 0 1

In =

Intro

ducc

i

Tema 1: 17

0 en caso contrario0 0 0 1 0 1 0 0

MatemticaDiscreta

afos


G = (V,A)V={1,2,3,4,5,6}A={{1,2},{1,3},{1,5},{1,6},

{2,4},{2,6},{3,4},{3,5}}

1 2

3

45

6


n a

la T

eora

de

Gra 45

Matriz de incidencia

Propiedades:

No tiene por qu ser ni cuadrada ni simtrica

1 1 1 1 0 0 0 01 0 0 0 1 1 0 00 1 0 0 0 0 1 10 0 0 0 1 0 1 00 0 1 0 0 0 0 1

In =

Intro

ducc

i

Tema 1: 18

La suma de cada fila es el grado del vrtice correspondiente

La suma de cada columna vale 2

0 0 0 1 0 1 0 0

10

MatemticaDiscreta

afos


Matriz de adyacencia de un digrafo

G = (V,A)V={1,2,3,4,5}A={(1,2),(1,4),(2,3),(3,1),

1 2

3

n a

la T

eora

de

Gra (3,4),(4,1),(4,5)}

3

45

0 1 0 1 00 0 1 0 01 0 0 1 0

Ad


aij = 1 si (vi , vj) es una arista

0 en caso contrario

Intro

ducc

i

Tema 1: 19

1 0 0 0 10 0 0 0 0

Ad =0 en caso contrario

MatemticaDiscreta

afos


Matriz de adyacencia de un digrafo

G = (V,A)V={1,2,3,4,5}A={(1,2),(1,4),(2,3),(3,1),

1 2

3

n a

la T

eora

de

Gra (3,4),(4,1),(4,5)}

3

45

0 1 0 1 00 0 1 0 01 0 0 1 0

Ad

Propiedades:

Es cuadrada pero no tiene por qu ser simtrica

Intro

ducc

i

Tema 1: 20

1 0 0 0 10 0 0 0 0

Ad =La suma de cada fila es el grado de salida del vrtice correspondiente

La diagonal es nula

La suma de cada columna es el grado de entrada del vrtice correspondiente

11

MatemticaDiscreta

afos


Matriz de adyacencia de un seudografo

G = (V,A)V={1,2,3,4}A={{1,2},{1,3},{2,4},{2,4}, 1

2

n a

la T

eora

de

Gra


aij = nmero de veces que aparece la arista {vi ,vj} d bl d l d

ij

{3,3},{3,3},{3,4},{4,4}}

3

4

Intro

ducc

i

Tema 1: 21

0 1 1 01 0 0 21 0 4 10 2 1 2

Ad =

doble del nmero de veces que aparece el lazo {vi,vi}

i=j

MatemticaDiscreta

afos


Matriz de adyacencia de un seudografo

G = (V,A)V={1,2,3,4}A={{1,2},{1,3},{2,4},{2,4}, 1

2

n a

la T

eora

de

Gra {3,3},{3,3},{3,4},{4,4}}

3

4

Propiedades:

Es cuadrada y simtrica

La suma de cada fila (o columna) es

Intro

ducc

i

Tema 1: 22

0 1 1 01 0 0 21 0 4 10 2 1 2

Ad =

La suma de cada fila (o columna) es el grado del vrtice correspondiente

La diagonal no tiene por qu ser nula

12

MatemticaDiscreta

afos


Matriz de adyacencia de un grafo ponderado

Ad: Matriz de orden nv nv1 2

67 8

n a

la T

eora

de

Gra

aij = peso de la arista {vi, vj}

0 7 3 0 9 77 0 0 5 0 83 0 0 3 7 0

Ad =

3 4

57

5

3

7

9

3

Intro

ducc

i

Tema 1: 23

0 5 3 0 0 09 0 7 0 0 07 8 0 0 0 0

Ad =

MatemticaDiscreta

afos

P.Reyes Subgrafos. Operaciones con grafos:

G es subgrafo de GG = (V,A) y G=(V ,A)

V V

n a

la T

eora

de

Gra G G A A

Intro

ducc

i

Tema 1: 24G G

13

MatemticaDiscreta

afos


G(S): subgrafo inducido por SG = (V,A) y S V

n a

la T

eora

de

Gra

S

Intro

ducc

i

Tema 1: 25G G(S)

MatemticaDiscreta

afos


G subgrafo recubridor de G si V =V

G = (V,A) y G =(V,A) un subgrafo de G

n a

la T

eora

de

Gra G subgrafo recubridor de G si V V

Intro

ducc

i

Tema 1: 26G G

14

MatemticaDiscreta

afos


Eliminacin de vrtice G =(V,A), vV

n a

la T

eora

de

Gra

v

Intro

ducc

i

Tema 1: 27

G

MatemticaDiscreta

afos


Eliminacin de vrtice

G-v = G(V-{v})

G =(V,A), vV

n a

la T

eora

de

Gra G v G(V {v})

Intro

ducc

i

Tema 1: 28

G-v

15

MatemticaDiscreta

afos


Eliminacin de arista G =(V,A), eA

n a

la T

eora

de

Gra

e

Intro

ducc

i

Tema 1: 29

G

MatemticaDiscreta

afos


Eliminacin de arista

G-e = (V,A-{e})

G =(V,A), eA

n a

la T

eora

de

Gra G e (V,A {e})

Intro

ducc

i

Tema 1: 30

G-e

16

MatemticaDiscreta

afos


G = (V,A) Grafo complementario G = (V, A )

e Ae A

n a

la T

eora

de

Gra

Intro

ducc

i

Tema 1: 31

G G

Kn = G G

MatemticaDiscreta

afos


G = (V,A)

G = (V A)

Unin de grafosG G = (V V,A A)

n a

la T

eora

de

Gra

a b b

G (V ,A )

ba

Interseccin de grafosG G = (V V, A A)

b

Intro

ducc

i

Tema 1: 32

de

G

de

c

G

de

c

G Gde

G G

17

MatemticaDiscreta

afos


G = (V,A) y G = (V,A) disjuntos (V V= )Vrtices: V V

n a

la T

eora

de

Gra Suma de grafos: Aristas:

A A {{v,v} / vV, v V}

Intro

ducc

i

Tema 1: 33

G G G + G

MatemticaDiscreta

afos


Grafo rueda Wn = K1 + Cn

n a

la T

eora

de

Gra

+ C12 =

Intro

ducc

i

Tema 1: 34

K1

W12

18

MatemticaDiscreta

afos

P.Reyes Operaciones con grafos: Grafo de lnea

Dado G = (V,A)V = {v1, v2, , vn}

A = {a1, a2, , am}

L(G) = (L(V) L(A))L(V) = A = {a1, a2, , am}

n a

la T

eora

de

Gra

{ai,aj}L(A) si, en el grafo G, las aristas ai y aj son incidentes en un vrtice.

L(G) = (L(V), L(A))L(A)

Ga7

a1a2

L(G)a1

a2a11

Intro

ducc

i

Tema 1: 35

a9a10

a3

a4

a11

a8

a5

a6

a7

a9

a10 a3

a4

a8 a5a6

MatemticaDiscreta

afos

P.Reyes Isomorfismo de grafos

G = (V,A) y G=(V ,A) son isomorfos (G G)

f : V V biyectiva | {u,v} A {f(u),f(v)} A

n a

la T

eora

de

Gra

1

25 c

b

f : V V biyectiva | {u,v} A {f(u),f(v)} A

f(1) = c

f(2) = e

f(3) = a

Intro

ducc

i

Tema 1: 36

34e a

df(4) = d

f(5) = b

19

MatemticaDiscreta

afos


Invariantes: Si G y G son isomorfos (G G) deben tener en comn:

n a

la T

eora

de

Gra nmero de vrtices

nmero de aristas

grados de los vrtices

nmero de ciclos de igual longitud

Intro

ducc

i

Tema 1: 37

e o de c c os de gu o g ud

nmero de componentes conexas

etc.

MatemticaDiscreta

afos


Grafo autocomplementario: Si G G1

2h

n a

la T

eora

de

Gra 2

3

46

8

7

e

b

ga

c

f

Intro

ducc

i

Tema 1: 38

G5

gd

Gf(1)=a, f(2)=b, . f(8)=h

20

MatemticaDiscreta

afos


Lista de grados de un grafo

1

n a

la T

eora

de

Gra

25

Relacin de adyacencias

{2,4,3,3,4}

(1)=2, (2)=4, (3)=3, (4)=3, (5)=4

Intro

ducc

i

Tema 1: 39

34

Lista de grados (4,4,3,3,2)

MatemticaDiscreta

afos


Lista de grados de un grafoDos grafos pueden tener la misma lista de grados y no ser isomorfos.

n a

la T

eora

de

Gra

1

6 3

2

f c

ba

Intro

ducc

i

Tema 1: 40

5 4 e d

Listas de grados (3,3,3,3,3,3)

No son isomorfos. El primer grafo contiene 3-ciclos y el segundo no.

21

MatemticaDiscreta

afos


Lista de grados de un grafoNo siempre una secuencia numrica decreciente representa una lista de grados de un grafo. Cuando esto ocurre se dice que la secuencia numrica

n a

la T

eora

de

Gra

g dos de u g o. Cu do es o ocu e se d ce que secue c u ces una secuencia grfica.

La secuencia numrica decreciente (a1,a2,...,ap) (con a1>0,p>1) es una secuencia grfica si, y slo si, tambin lo es la que resulta de efectuar las siguientes operaciones:

1) Eliminar el primer elemento (a1) de la lista.Teorema de Havel-Hakimi

Intro

ducc

i

Tema 1: 41

2) Restar una unidad a los primeros a1 elementos de la nueva lista.

3) Ordenar en sentido decreciente la nueva lista.

MatemticaDiscreta

afos


Lista de grados de un grafoUna secuencia numrica decreciente representa una lista de grados de un grafo si el siguiente algoritmo devuelve una lista de ceros:

n a

la T

eora

de

Gra

g o s e s gu e e go o devue ve u s de ce os:

Algoritmo de Havel-Hakimi

P.1 Leer la lista decreciente (a1,a2,...,ap).

P.2 Mientras el primer elemento sea a1>0

P.3 Eliminar el elemento a1 de la lista.

Intro

ducc

i

Tema 1: 42

P.4 Restar 1 a los primeros a1 elementos de la nueva lista.

P.5 Ordenar (decreciente) la nueva lista.

P.6 Retornar la lista (a1,a2,...).

22

MatemticaDiscreta

afos

P.Reyes Isomorfismo de grafosAlgoritmo de Havel-Hakimi



P 3 Eli i l l t d l li t

(5,4,4,4,2,1)

(4,4,4,2,1)

(3,3,3,1,0)

(3 3 1 0)

P.3

P.4

P.3

n a

la T

eora

de

Gra





(3,3,1,0)

(2,2,0,0)

(2,0,0)

(1,-1,0)

P.4

P.3

P.4

P.5

Intro

ducc

i

Tema 1: 43

(-1,-1)P.4

(5,4,4,4,2,1) no es una secuencia grfica

(1,0,-1)P.5

(0,-1)P.3

MatemticaDiscreta

afos


(1,2,2,3,4)

(4,3,2,2,1)





n a

la T

eora

de

Gra

(3,2,2,1)

(2,1,1,0)

(1,1,0)

P.3

P.4

P.3

P 4(1,2,2,3,4) es una secuencia grfica





Intro

ducc

i

Tema 1: 44

(0,0,0)

P.4

23

MatemticaDiscreta

afos


(1,2,2,3,4)

(4,3,2,2,1)





n a

la T

eora

de

Gra

(3,2,2,1)

(2,1,1,0)

(1,1,0)

P.3

P.4

P.3

P 4





Intro

ducc

i

Tema 1: 45

(0,0,0)

P.4

MatemticaDiscreta

afos


(1,2,2,3,4)

(4,3,2,2,1)





n a

la T

eora

de

Gra

(3,2,2,1)

(2,1,1,0)

(1,1,0)

P.3

P.4

P.3

P 4





Intro

ducc

i

Tema 1: 46

(0,0,0)

P.4

24

MatemticaDiscreta

afos


(1,2,2,3,4)

(4,3,2,2,1)





n a

la T

eora

de

Gra

(3,2,2,1)

(2,1,1,0)

(1,1,0)

P.3

P.4

P.3

P 4





Intro

ducc

i

Tema 1: 47

(0,0,0)

P.4

Documents

Tema 1-Introduccion-2dpp.pdf