tema5 grafos y arboles

Tema 5: Grafos

RafaC - Matemtica Discreta - UCM 07/08

1

Indice1. 2. 3. 4. 5. 6. 7. 8. 9.

Tipos de grafos Conceptos Bsicos Representacin de grafos Subgrafos. Grafos complementarios Caminos y conectividad Grafos Bipartitos Recorridos, eulerianos o hamiltonianos Isomorfismo de grafos rbolesRafaC - Matemtica Discreta - UCM 07/08 2

Tipos de Grafos

Un grafo G es un par (V,E) donde: V ={v1,,vn} es un conjunto de vrtices E = {e1,,em} es un conjunto de aristas, con cada ek {vi, vj}, con vi, vj V, vi vj Los vrtices se representan como puntos y las aristas como lneas entre vrtices Ejemplo:

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


3

Tipos de Grafos

Ejemplo: red de ordenadores


Tipos de grafos

Es importante recordar que un mismo grafo puede tener diferentes representaciones grficas Ejemplo: Ejemplo:

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


5

Tipos de Grafos

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

En este caso a las aristas se les llama arcos y se representan como pares para indicar el orden:

V = { a,b,c,d,e} A ={(e,a), (a,b), (b,a), (d,a), (c,d), (d,c),(b,c),(c,b) }RafaC - Matemtica Discreta - UCM 07/08 6

Tipos de Grafos

Si se permite que haya ms de una arista se habla de multigrafos: multigrafos:


7

Tipos de Grafos

Cuando las aristas tienen un valor numrico asociado se llama de grafos valorados: valorados:

Al valor numrico asociado se le llama coste de la aristaRafaC - Matemtica Discreta - UCM 07/08 8

Tipos de Grafos

Los tipos anteriores pueden combinarse, dando lugar por ejemplo a multigrafos valorados, o valorados, grafos dirigidos valorados, etc. valorados, En el resto del tema cuando no se diga lo contrario G representar un grafo o multigrafo no dirigido


9

Conceptos Bsicos

Dos vrtices se dicen adyacentes si existe una arista que los une Los vrtices que forman una arista son los extremos de la arista Si v es un extremo de una arista a, se dice que a es incidente con v El grado de un vrtice v, gr(v) es el nmero de aristas incidentes en v. Si hace falta indicar el grafo en el que est v escribiremos gr(G,v)RafaC - Matemtica Discreta - UCM 07/08 10

Conceptos Bsicos

Ejemplo: Ejemplo:

gr(6)= _______

gr(1) = ________11


Conceptos BsicosTeorema (de los apretones de manos) Sea G=(V,A) un grafo. Entonces: gr(v) = 2|A|

v V

Significado: la suma de los grados de todos los vrtices es igual a 2 veces el nmero de aristas Explicacin: Explicacin:


12

Conceptos Bsicos

Ejemplo: Ejemplo:

gr(a)+gr(b)+gr(c)+gr(d)+gr(e)+gr(f) = 3+4+5+2+4+4 = 22 2|A| = 2 ____ = _____RafaC - Matemtica Discreta - UCM 07/08 13

Conceptos Bsicos

Para cada n1 se llama grafo completo de orden n, y se Kn, representa por Kn, al grafo de n vrtices conectados de todas las formas posibles:

Pregunta: Pregunta: Cuntas aristas tiene en general Kn? Kn?RafaC - Matemtica Discreta - UCM 07/08 14

Conceptos Bsicos

Se llama ciclo de grado n, y se denota Cn, a Cn, G=({v1,,vn}, {{v1, v2}, {v2, v3},, {vn-1, vn}, {vn, v1}} )

Nota: A menudo slo se consideran ciclos para n3 Nota: n3RafaC - Matemtica Discreta - UCM 07/08

15

Representacin de Grafos

Para representar los grafos a menudo se utiliza la llamada matriz de adyacencia Se construye imaginando que en las filas y las columnas corresponden a los vrtices. Se pone un 0 para indicar que 2 vrtices no son adyacentes, y un 1 para indicar que s lo son:1 2 3 4

1 2 3 4 5 6

G

5 6 Matriz de Adyacencia de G

Para representarla en un ordenador se utilizan matriz de valores lgicos (booleanos). True hay arista, False no hay arista booleanos).RafaC - Matemtica Discreta - UCM 07/08

16


En el caso de un grafo no dirigido la matriz ser simtrica. No ocurre lo mismo para grafos dirigidos:

Se supone que la fila representa el vrtice origen, y la columna el vrtice destino del arco origen,RafaC - Matemtica Discreta - UCM 07/08 17


La matriz de adyacencia tambin permite representar grafos valorados

El valor guardado es el coste de la arista/arco En lugar de 0, a menudo se emplea un valor especial g para indicar que dos vrtices no estn conectadosRafaC - Matemtica Discreta - UCM 07/08 18


En informtica a menudo en lugar de la matriz se usa la lista de adyacencia A cada vrtice le corresponde una lista con sus adyacentes:

G Lista de Adyacencia de GRafaC - Matemtica Discreta - UCM 07/08

19

Subgrafos

Sea G=(V,A). G=(V,A) se dice subgrafo G=(V,A). de G si:1. 2. 3.

V V A A (V,A) es un grafo Si G=(V,A) es subgrafo de G, para todo v G se cumple gr(G,v) gr(G,v)RafaC - Matemtica Discreta - UCM 07/08 20

Resultado fcil de comprobar:

Subgrafos

Ejemplo: Ejemplo:

G1 y G2 son subgrafos de GRafaC - Matemtica Discreta - UCM 07/08 21

Subgrafos

Un grafo se dice cclico cuando contiene algn ciclo como subgrafo Ejemplo:

Contiene dos ciclos de long. 3: {a,e,f,a} y {_, _, _, _} Contiene un ciclo de longitud 6: {_,_,_,_,_,_,_} Contiene algn ciclo ms? ___RafaC - Matemtica Discreta - UCM 07/08 22

Grafo Complementario

El complementario G de un grafo G=(V,A) tiene:Los mismos vrtices que G Si {u,v} G, entonces {u,v} G Si {u,v} G, entonces {u,v} G

Una forma de construirlo:Dibujar el corresp. grafo completo Kn, con n=|V| Kn, Eliminar de Kn las aristas {u,v} G

RafaC - Matemtica Discreta - UCM 07/08 23

Grafo complementario

Ejemplo : Complementario de

1 Representar K6

2 Marcar las aristas de GRafaC - Matemtica Discreta - UCM 07/08

3 Eliminarlas

24

Caminos y conectividad

Un recorrido en un grafo G = (V,A) es una sucesin de vrtices v0, v1, , vk tal que {vi,vi+1} A para todo 0 i < k La longitud de un recorrido v0, v1, , vk es k Ejemplo: Ejemplo:

G

f,b,c,f,e,d es un recorrido de longitud 5 sobre G25



Observacin: Un recorrido puede repetir Observacin: vrtices, y puede comenzar y acabar en vrtices diferentes Un camino es un recorrido v0, v1, , vk en el que vi vj para 0 i,j k, con i 0 o j k Es decir en un camino todos los vrtices son distintos entre s, excepto quizs el primero y el ltimoRafaC - Matemtica Discreta - UCM 07/08 26


Ejemplo:

G

a,b,e,c,d es un camino


27


Si existe un camino entre dos vrtices se dice que estn conectados Sea G=(V,A) un grafo. La relacin xRy x e y estn conectados es de equivalencia (R ___) Si para todo par de vrtices de un grafo estn conectados se dice que el grafo es conexo g Las componentes conexas de un grafo G son los mayores subgrafos conexos de GRafaC - Matemtica Discreta - UCM 07/08 28


Ejemplo. Ejemplo. Consideramos el grafo: Se tiene que:

G no es conexo: no hay camino entre a y b, por ejemplo. [a] = {a,c,e} [c] = {a,c,e} [e]={a,c,e} [b]={b,d} [d]={b,d} G/R = {[a],[b]} G tiene dos componentes conexas:


29


Un recorrido v0, v1, ,vk tal que v0 = vk es un circuito Un camino v0, v1, , vk tal que v0 = vk es un ciclo

G

a,b,f,c,e,f,a es un circuito

f,c,b,e,f es un ciclo


30

Grafos BipartitosUn problema interesante en un grafo es determinar su nmero cromtico: cromtico: Cuntos colores son necesarios para pintar los vrtices de forma que cada arista una siempre colores distintos? Ejemplo: Grafo con nmero cromtico 4 Ejemplo:


31

Grafos Bipartitos

Aplicacin: coloreado de mapas Cuntos colores se necesitan para colorear un mapa de forma que no haya dos regiones con frontera con el mismo color?


32

Grafos Bipartitos

Idea: Transformar el mapa en un grafo, donde Idea: cada vrtice representa una regin y cada arista un lmite entre regiones:

Cuntos colores se necesitan?

nmero cromtico de este grafo?33


Grafos Bipartitos

Resultado: Resultado: Todos los mapas se pueden colorear con un mximo de 4 colores Solucin propuesta en 1879, probada en 1976 por K. Appel y W. Haken con la ayuda de un ordenador.


34

Grafos Bipartitos

Nosotros vamos a interesarnos en un caso particular: aquellos grafos que se pueden colorear en dos colores grafos bipartitos Definicin: Definicin: Sea G=(V,A). Se dice que G es G=(V,A). bipartito si existen V1, V2 tales que:1. 2. 3.

V1 V2= V V1 V2= Para toda {vi,vj} A se cumple vi V1, vj V2RafaC - Matemtica Discreta - UCM 07/08 35

Grafos Bipartitos

Ejemplos:

Es bipartito ?

S; V1 = {2,5}, V2={0,1,3,4,6,7}


36

Grafos Bipartitos

Idea de cmo pintarlo:Empezar por un vrtice cualquiera, de color C1 Dibujar todos los adyacentes de color C2 Seguir este proceso hasta haber terminado

Parece que No es bipartito, pero cmo estar seguros?


37

Grafos Bipartitos

Teorema: Teorema: Una grafo es bipartito si y slo si no tiene ciclos de longitud impar Ejemplo anterior: No bipartito; contiene ciclos anterior: bipartito; de longitud impar (en la figura aparece marcado uno de long. 3)


38

Recorridos eulerianos

Ciudad de Knisberg, en XVIII:

Pregunta: sera posible dar un paseo pasando por cada uno de los siete puentes, sin repetir ninguno, comenzando y acabando en el mismo punto?RafaC - Matemtica Discreta - UCM 07/08 39


Representacin propuesta por Leonard Euler en 1736:

Existe un circuito que pase por todas las aristas una sola vez?RafaC - Matemtica Discreta - UCM 07/08 40


A estos circuitos se les llama circuitos eulerianos, y a eulerianos, los grafos que los contienen grafos eulerianos Grafo o multigrafo euleriano: admite un recorrido euleriano: que pasa por todas las aristas una sola vez, empezando y terminando en el mismo vrtice. Los vrtices s se pueden repetir Ejemplo: Ejemplo: Grafo euleriano.

Circuito euleariano: a,b,c,d,b,f,d,e,a,c,e,f,aRafaC - Matemtica Discreta - UCM 07/08 41


Ejemplo: Ejemplo: Grafo euleriano.

Circuito euleariano: a,b,c,d,b,f,d,e,a,c,e,f,a Ejemplo: El siguiente grafo es euleriano Ejemplo:

Encuentra un circuito euleriano:RafaC - Matemtica Discreta - UCM 07/08 42


Cmo saber si un grafo (o multigrafo) es euleriano? Teorema de Euler: Un grafo conexo es Euler: euleriano no tiene vrtices de grado impar Ejemplo: Ejemplo:

A tiene grado 3 el grafo de los puentes no es euleriano.RafaC - Matemtica Discreta - UCM 07/08 43


Si el grafo/multigrafo tiene slo dos vrtices de grado impar se llama semi-euleriano. Se puede semi-euleriano. convertir en euleriano aadindole una arista:

Semi-euleriano (__,__ grado impar)

Euleriano


44

Recorridos hamiltonianos

Un grafo se dice hamiltoniano si existe un ciclo que recorre todos sus vrtices. Al ciclo se le llama ciclo hamiltoniano Ejemplos:


45

Recorridos hamiltonianos

No existe un mtodo sencillo para saber si un grafo es no hamiltoniano problema muy complejo Ejemplo: Este grafo es hamiltoniano Ejemplo:

...pero este no difcil de probar!RafaC - Matemtica Discreta - UCM 07/08

46

Isomorfismo de grafos

Idea: Idea: En ocasiones dos grafos con diferentes vrtices presentan la misma estructura:

Cmo probarlo? Buscando una funcin biyectiva que convierta los vrtices de uno en otro, preservando la estructura de las aristas Definicin: Dos grafos G=(V,A), G=(V,A) son isomorfos si Definicin: G=(V,A), {a,b} existe una funcin biyectiva f:V V tal que {a,b}A {f(a),f(b)} {f(a),f(b)}ARafaC - Matemtica Discreta - UCM 07/08 47


Ejemplo: f(1) = a f(2) = f f(6) = b f(4) = h f(5) = d f(3) = g f(7) = e f(8) = c

Los dos grafos son isomorfos. Demostracin: Construimos f Demostracin: como se indica al lado de la figura. Se tiene que: {1,2} f {a,f} {6,8} f {b,c} {1,6} f {a,b} {2,8} f {f,c} {4,3} f {h,g} {1,4} f {a,h} {2,3} f {f,g} {5,7} f {d,e} {4,5} f {h,d} {3,7} f {g,e} {6,5} f {b,d} {8,7} f {c,e}RafaC - Matemtica Discreta - UCM 07/08 48


Y como saber si dos grafos no son isomorfos? isomorfos? Hay que buscar alguna caracterstica que diferencie la estructura de los dos grafos, como por ejemplo:Distinto nmero de vrtices o de aristas Distinto nmero de ciclos de una longitud dada Distinto nmero de vrtices con un mismo grado n Aristas conectando vrtices con dos grados tales que no existan aristas de las mismas caractersticas en el otro grafo



Ejemplo: son isomorfos estos dos grafos? Ejemplo:

Respuesta: no; G tiene un ciclo de longitud 3 Respuesta: (b,d,c,b) y G no tiene ninguno de longitud 3RafaC - Matemtica Discreta - UCM 07/08 50


Son isomorfos? ___

por qu? __________________________________________________RafaC - Matemtica Discreta - UCM 07/08 51

rboles

rbol: rbol: Grafo conexo y sin ciclos Ejemplo: Ejemplo:

A menudo se selecciona un nodo especial al que se llama raz, y raz, se dibuja con la raz en la parte superior, sus adyacentes ms abajo y as sucesivamente:


52

rboles

Ejemplo: rbol


53

rboles

Ejemplo: Una estructura de carpetas y ficheros Ejemplo: es un rbol


54

rboles

Ejemplos: Ejemplos:

Anlisis de expresiones

rboles de bsqueda


55

rboles

Un poco de terminologaLos vrtices de un rbol se llaman nodos Los nodos descendientes inmediatos de un nodo son hijos, sus hijos, y el nodo superior es el padre A una secuencia descendente de nodos se le llama rama Los nodos sin hijos se llaman hojas, y los que s hojas, tienen hijos nodos internos Un conjunto de rboles es un bosque


rboles

Algunas propiedades. propiedades. Sea G =(V,A) un rbol. Entonces:Entre cada par de vrtices x,y hay un nico camino Al quitar de A cualquier arista resulta un bosque con 2 rboles Al aadir una arista nueva siempre se obtiene un ciclo |A| = |V| -1


57

rboles recubridores

Dado un grafo conexo G =(V,A) decimos que un rbol T =(V,A) es un rbol recubridor de G si V=V, y A A. V=V, A. En el caso de grafos valorados interesa que la suma de pesos de las aristas del rbol sea lo ms pequea posible: rbol de recubrimiento

mnimo.RafaC - Matemtica Discreta - UCM 07/08 58

rbol de recubrimiento mnimo


59

Algoritmo de Prim

1. 2.

Se usa para construir rboles recubridores:Se elige un vrtice cualquiera del grafo como vrtice inicial y se marca. Mientras que queden vrtices no marcados elegimos un vrtice no marcado que est conectado con alguno marcado. Marcamos tanto el vrtice como una de las aristas que lo unen con los ya marcados

En el caso de grafos valorados en cada paso se toma la arista de menor peso que cumpla 2) y se obtiene un rbol de recubrimiento mnimo.


60

tema5 grafos y arboles

Documents