rafac - matemática discreta - ucm 07/08 1 tema 5: grafos

RafaC - Matemática Discreta - UCM 07/08 1

Tema 5: GrafosTema 5: Grafos

2RafaC - Matemática Discreta - UCM

07/08

IndiceIndice1.1. Tipos de grafosTipos de grafos2.2. Conceptos BásicosConceptos Básicos3.3. Representación de grafosRepresentación de grafos4.4. Subgrafos. Grafos complementariosSubgrafos. Grafos complementarios5.5. Caminos y conectividadCaminos y conectividad6.6. Grafos BipartitosGrafos Bipartitos7.7. Recorridos, eulerianos o Recorridos, eulerianos o

hamiltonianoshamiltonianos8.8. Isomorfismo de grafosIsomorfismo de grafos9.9. ÁrbolesÁrboles


07/08

Tipos de GrafosTipos de Grafos

Un grafo Un grafo GG es un par es un par (V,E)(V,E) donde: donde: V ={vV ={v11,…,v,…,vnn}} es un conjunto de vértices es un conjunto de vértices

E = {eE = {e11,…,e,…,emm}} es un conjunto de aristas, es un conjunto de aristas,

con cada con cada eekk {v {vii, v, vjj}}, con , con vvii, v, vj j V V, , vvii ≠ v ≠ vjj

Los vértices se representan como puntos y las Los vértices se representan como puntos y las aristas como líneas entre vérticesaristas como líneas entre vértices

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


07/08


Ejemplo: red de ordenadoresEjemplo: red de ordenadores


07/08

Tipos de grafosTipos de grafos Es importante recordar que un mismo grafo Es importante recordar que un mismo grafo

puede tener diferentes representaciones gráficaspuede tener diferentes representaciones gráficas EjemploEjemplo::

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

{c,d},{e,d},{d,f}}){c,d},{e,d},{d,f}})


07/08


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

En este caso a las aristas se les llama En este caso a las aristas se les llama arcosarcos y y se representan como pares para indicar el se representan como pares para indicar el orden:orden: V = { a,b,c,d,e}V = { a,b,c,d,e} A ={(e,a), (a,b), (b,a), (d,a), (c,d), (d,c),(b,c),A ={(e,a), (a,b), (b,a), (d,a), (c,d), (d,c),(b,c),

(c,b) }(c,b) }


07/08


Si se permite que haya más de una Si se permite que haya más de una arista se habla de arista se habla de multigrafosmultigrafos::


07/08

Tipos de GrafosTipos de Grafos Cuando las aristas tienen un valor numérico Cuando las aristas tienen un valor numérico

asociado se llama de asociado se llama de grafos valoradosgrafos valorados::

Al valor numérico asociado se le llama Al valor numérico asociado se le llama costecoste de la de la aristaarista


07/08


Los tipos anteriores pueden Los tipos anteriores pueden combinarse, dando lugar por combinarse, dando lugar por ejemplo a ejemplo a multigrafos valoradosmultigrafos valorados, o , o grafos dirigidos valoradosgrafos dirigidos valorados, etc., etc.

En el resto del tema cuando no se En el resto del tema cuando no se diga lo contrario diga lo contrario GG representará un representará un grafo o multigrafo no dirigidografo o multigrafo no dirigido


07/08

Conceptos BásicosConceptos Básicos

Dos vértices se dicen Dos vértices se dicen adyacentesadyacentes si si existe una arista que los uneexiste una arista que los une

Los vértices que forman una arista Los vértices que forman una arista son los son los extremosextremos de la arista de la arista

Si Si vv es un extremo de una arista es un extremo de una arista aa, se , se dice que dice que aa es es incidenteincidente con con vv

El grado de un vértice El grado de un vértice vv, , gr(v)gr(v) es el es el número de aristas incidentes en número de aristas incidentes en v. v. Si Si hace falta indicar el grafo en el que hace falta indicar el grafo en el que está está vv escribiremos escribiremos gr(G,v)gr(G,v)


07/08


EjemploEjemplo::

gr(6)= _______gr(6)= _______ gr(1) = ________ gr(1) = ________


07/08


TeoremaTeorema (de los “apretones de (de los “apretones de manos”)manos”)

Sea G=(V,A) un grafo. Entonces: Sea G=(V,A) un grafo. Entonces: ∑ ∑ gr(v) = 2|A|gr(v) = 2|A|

vv V V

Significado: la suma de los grados de Significado: la suma de los grados de todos los vértices es igual a 2 veces el todos los vértices es igual a 2 veces el número de aristasnúmero de aristas

ExplicaciónExplicación::


07/08


EjemploEjemplo::

gr(a)+gr(b)+gr(c)+gr(d)+gr(e)gr(a)+gr(b)+gr(c)+gr(d)+gr(e)+gr(f) = 3+4+5+2+4+4 = +gr(f) = 3+4+5+2+4+4 = 2222

2|A| = 2 ____ = _____2|A| = 2 ____ = _____


07/08

Conceptos BásicosConceptos Básicos Para cada Para cada nn≥1≥1 se llama se llama grafo completografo completo de orden n, y se de orden n, y se

representa por representa por KnKn, al grafo de n vértices conectados de todas , al grafo de n vértices conectados de todas las formas posibles:las formas posibles:

PreguntaPregunta: ¿Cuántas aristas tiene en general : ¿Cuántas aristas tiene en general KnKn??


07/08


Se llama Se llama ciclociclo de grado n, y se denota de grado n, y se denota CnCn, a , a G=({vG=({v11,…,v,…,vnn}, },

{{v{{v11, v, v22}, {v}, {v22, v, v33},…, {v},…, {vn-1n-1, v, vnn}, {v}, {vnn, v, v11}} )}} )

NotaNota: A menudo sólo se consideran ciclos : A menudo sólo se consideran ciclos para npara n≥3≥3


07/08

Representación de Representación de GrafosGrafos

Para representar los grafos a menudo se utiliza la llamada Para representar los grafos a menudo se utiliza la llamada matriz de adyacenciamatriz de adyacencia

Se construye imaginando que en las filas y las columnas Se construye imaginando que en las filas y las columnas corresponden a los vértices. Se pone un 0 para indicar que 2 corresponden a los vértices. Se pone un 0 para indicar que 2 vértices no son adyacentes, y un 1 para indicar que sí lo son:vértices no son adyacentes, y un 1 para indicar que sí lo son:

Para representarla en un ordenador se utilizan matriz de Para representarla en un ordenador se utilizan matriz de valores lógicos (valores lógicos (booleanosbooleanos). True ). True hay arista, False hay arista, False no no hay aristahay arista

1

2

3

4

5

6

1 2 3 4 5 6

G

Matriz de Adyacencia de G


07/08


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

Se supone que la Se supone que la filafila representa el representa el vértice vértice origenorigen, y la , y la columnacolumna el vértice el vértice destinodestino del arco del arco


07/08


La matriz de adyacencia también permite La matriz de adyacencia también permite representar representar grafos valoradosgrafos valorados

El valor guardado es el El valor guardado es el costecoste de la arista/arco de la arista/arco En lugar de En lugar de 00, a menudo se emplea un valor , a menudo se emplea un valor

especial especial para indicar que dos vértices no para indicar que dos vértices no están conectadosestán conectados


07/08


En informática a menudo en lugar En informática a menudo en lugar de la matriz se usa la de la matriz se usa la lista de lista de adyacenciaadyacencia

A cada vértice le corresponde una A cada vértice le corresponde una lista con sus adyacentes:lista con sus adyacentes:

G

Lista de Adyacencia de G


07/08

SubgrafosSubgrafos

Sea Sea G=(V,A)G=(V,A). . G’=(V’,A’)G’=(V’,A’) se dice se dice subgrafosubgrafo de de GG si: si:

1.1. V’ V’ V V

2.2. A’ A’ A A

3.3. (V’,A’) (V’,A’) es un grafoes un grafo Resultado fácil de comprobar:Resultado fácil de comprobar:

Si Si G’=(V’,A’)G’=(V’,A’) es subgrafo de G, para es subgrafo de G, para todo todo v v G G se cumple se cumple gr(G’,v)≤ gr(G’,v)≤ gr(G,v)gr(G,v)


07/08

SubgrafosSubgrafos

EjemploEjemplo::

G1 y G2 son subgrafos de GG1 y G2 son subgrafos de G


07/08

SubgrafosSubgrafos Un grafo se dice cíclico cuando contiene Un grafo se dice cíclico cuando contiene

algún ciclo como subgrafoalgún ciclo como subgrafo Ejemplo:Ejemplo:

Contiene dos ciclos de long. 3: {a,e,f,a} y {_, Contiene dos ciclos de long. 3: {a,e,f,a} y {_, _, _, _}_, _, _}

Contiene un ciclo de longitud 6: Contiene un ciclo de longitud 6: {_,_,_,_,_,_,_}{_,_,_,_,_,_,_}

¿Contiene algún ciclo más? ___¿Contiene algún ciclo más? ___


07/08

Grafo ComplementarioGrafo Complementario

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

Una forma de construirlo:Una forma de construirlo: Dibujar el corresp. grafo completo Dibujar el corresp. grafo completo KnKn, ,

con con n=|V|n=|V| Eliminar de Eliminar de KnKn las aristas las aristas {u,v} {u,v} G G


07/08

Grafo complementarioGrafo complementario

EjemploEjemplo : Complementario de : Complementario de

1º Representar K6

2º Marcar las aristas de G

3º Eliminarlas


07/08

Caminos y conectividadCaminos y conectividad Un Un recorridorecorrido en un grafo en un grafo G = (V,A)G = (V,A)

es una sucesión de vértices es una sucesión de vértices vv00, v, v11, …, , …, vvkk tal que tal que {v{vii,v,vi+1i+1}} A A para todo para todo 0 ≤i 0 ≤i < k< k

La La longitudlongitud de un recorrido de un recorrido vv00, v, v11, , …, v…, vkk es es kk

EjemploEjemplo::

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


07/08

Caminos y conectividadCaminos y conectividad

ObservaciónObservación: Un recorrido puede : Un recorrido puede repetir vértices, y puede comenzar y repetir vértices, y puede comenzar y acabar en vértices diferentesacabar en vértices diferentes

Un Un caminocamino es un recorrido es un recorrido vv00, v, v11, …, , …, vvkk en el que en el que vvii ≠ v ≠ vjj para para 0 ≤i,j ≤ k, 0 ≤i,j ≤ k, con con i ≠0i ≠0 o o j ≠kj ≠k

Es decir en un camino todos los Es decir en un camino todos los vértices son vértices son distintosdistintos entre sí, entre sí, excepto quizás el primero y el últimoexcepto quizás el primero y el último


07/08


Ejemplo:Ejemplo:

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


07/08

Caminos y conectividadCaminos y conectividad Si existe un camino entre dos vértices se Si existe un camino entre dos vértices se

dice que están dice que están conectadosconectados Sea Sea G=(V,A)G=(V,A) un grafo. La relación un grafo. La relación

xRy xRy x e y están conectados x e y están conectados es de equivalencia (R es de equivalencia (R ___) ___) Si para todo par de vértices de un grafo Si para todo par de vértices de un grafo

están conectados se dice que el grafo es están conectados se dice que el grafo es conexoconexo g g

Las Las componentes conexascomponentes conexas de un grafo G de un grafo G son los mayores subgrafos conexos de Gson los mayores subgrafos conexos de G


07/08


EjemploEjemplo. Consideramos el grafo:. Consideramos el grafo:

Se tiene que:Se tiene que: G no es conexo: no hay camino entre a y b, por G no es conexo: no hay camino entre a y b, por

ejemplo.ejemplo. [a] = {a,c,e} [c] = {a,c,e} [e]={a,c,e} [a] = {a,c,e} [c] = {a,c,e} [e]={a,c,e}

[b]={b,d} [d]={b,d}[b]={b,d} [d]={b,d} G/R = {[a],[b]}G/R = {[a],[b]} G tiene dos componentes conexas:G tiene dos componentes conexas:


07/08


Un recorrido Un recorrido vv00, v, v11, …,v, …,vkk tal que tal que vv0 0 = v= vkk es es un un circuitocircuito

Un camino Un camino vv00, v, v11, …, v, …, vkk tal que tal que vv0 0 = v= vkk es es un un ciclociclo

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

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


07/08

Grafos BipartitosGrafos Bipartitos

Un problema interesante en un grafo Un problema interesante en un grafo es determinar su es determinar su número número cromáticocromático::

¿Cuántos colores son necesarios para ¿Cuántos colores son necesarios para pintar los vértices de forma que pintar los vértices de forma que cada arista una siempre colores cada arista una siempre colores distintos?distintos?

EjemploEjemplo: Grafo con número : Grafo con número cromático 4cromático 4


07/08


Aplicación: coloreado de mapasAplicación: coloreado de mapas ¿Cuántos colores se necesitan para ¿Cuántos colores se necesitan para

colorear un mapa de forma que no colorear un mapa de forma que no haya dos regiones con frontera con haya dos regiones con frontera con el mismo color?el mismo color?


07/08


IdeaIdea: Transformar el mapa en un : Transformar el mapa en un grafo, donde cada vértice representa grafo, donde cada vértice representa una región y cada arista un límite una región y cada arista un límite entre regiones:entre regiones:

¿Cuántos colores se necesitan? ¿número cromático de este grafo?


07/08

Grafos BipartitosGrafos Bipartitos ResultadoResultado: Todos los mapas se pueden : Todos los mapas se pueden

colorear con un máximo de 4 colorescolorear con un máximo de 4 colores Solución propuesta en 1879, probada en Solución propuesta en 1879, probada en

1976 por K. Appel y W. Haken con la por K. Appel y W. Haken con la ayuda de un ordenador.ayuda de un ordenador.


07/08


Nosotros vamos a interesarnos en un Nosotros vamos a interesarnos en un caso particular: aquellos grafos que se caso particular: aquellos grafos que se pueden colorear en pueden colorear en dosdos colores colores grafos grafos bipartitosbipartitos

DefiniciónDefinición: Sea : Sea G=(V,A)G=(V,A). Se dice que . Se dice que GG es bipartito si existen es bipartito si existen VV11, , VV22 tales que: tales que:

1.1. VV11 VV22= V= V

2.2. VV11 ∩∩ VV22= = ØØ

3.3. Para toda Para toda {v{vii,v,vjj}} A A se cumple se cumple vvi i V V1, 1, vvj j V V22


07/08


Ejemplos:Ejemplos:

¿Es bipartito ?

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


07/08


IdeaIdea de cómo pintarlo: de cómo pintarlo: Empezar por un vértice cualquiera, de Empezar por un vértice cualquiera, de

color C1color C1 Dibujar todos los adyacentes de color Dibujar todos los adyacentes de color

C2C2 Seguir este proceso hasta haber Seguir este proceso hasta haber

terminadoterminado

Parece que No es bipartito, pero …

¿cómo estar seguros?


07/08


TeoremaTeorema: Una grafo es bipartito si y : Una grafo es bipartito si y sólo si no tiene ciclos de longitud sólo si no tiene ciclos de longitud imparimpar

Ejemplo anteriorEjemplo anterior: : No bipartitoNo bipartito; ; contiene ciclos de longitud impar (en contiene ciclos de longitud impar (en la figura aparece marcado uno de la figura aparece marcado uno de long. 3)long. 3)


07/08

Ciudad de Könisberg, en XVIII:Ciudad de Könisberg, en XVIII:

Pregunta: ¿sería posible dar un paseo pasando por cada uno de los siete puentes, sin repetir ninguno, comenzando y acabando en el mismo punto?

Recorridos eulerianosRecorridos eulerianos


07/08


Representación propuesta por Representación propuesta por Leonard Euler en 1736:Leonard Euler en 1736:

¿Existe un circuito que pase por ¿Existe un circuito que pase por todas las aristas una sola vez?todas las aristas una sola vez?


07/08

Recorridos eulerianosRecorridos eulerianos A estos circuitos se les llama A estos circuitos se les llama circuitos circuitos

eulerianoseulerianos, y a los grafos que los contienen , y a los grafos que los contienen grafos eulerianosgrafos eulerianos

Grafo o multigrafo eulerianoGrafo o multigrafo euleriano: admite un : admite un recorrido que pasa por todas las aristas una recorrido que pasa por todas las aristas una sola vez, empezando y terminando en el sola vez, empezando y terminando en el mismo vértice. Los vértices sí se pueden mismo vértice. Los vértices sí se pueden repetirrepetir

EjemploEjemplo: Grafo euleriano. : Grafo euleriano.

Circuito euleariano: Circuito euleariano: a,b,c,d,b,f,d,e,a,c,e,f,aa,b,c,d,b,f,d,e,a,c,e,f,a


07/08

Recorridos eulerianosRecorridos eulerianos EjemploEjemplo: Grafo euleriano. : Grafo euleriano.

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

Encuentra un circuito euleriano: Encuentra un circuito euleriano:


07/08


¿Cómo saber si un grafo (o multigrafo) es ¿Cómo saber si un grafo (o multigrafo) es euleriano?euleriano?

Teorema de EulerTeorema de Euler: Un grafo conexo es : Un grafo conexo es euleriano euleriano no tiene vértices de grado no tiene vértices de grado imparimpar

EjemploEjemplo::

AA tiene grado 3 tiene grado 3el grafo de los puentes no es el grafo de los puentes no es euleriano.euleriano.


07/08


Si el grafo/multigrafo tiene sólo dos Si el grafo/multigrafo tiene sólo dos vértices de grado impar se llama vértices de grado impar se llama semi-eulerianosemi-euleriano. Se puede convertir . Se puede convertir en euleriano añadiéndole una arista:en euleriano añadiéndole una arista:

Semi-euleriano

(__,__ grado impar)

Euleriano


07/08

Recorridos Recorridos hamiltonianoshamiltonianos

Un grafo se dice Un grafo se dice hamiltonianohamiltoniano si si existe un ciclo que recorre todos sus existe un ciclo que recorre todos sus vértices. Al ciclo se le llama vértices. Al ciclo se le llama ciclo ciclo hamiltonianohamiltoniano

Ejemplos:Ejemplos:


07/08

Recorridos Recorridos hamiltonianoshamiltonianos

No existeNo existe un método sencillo para un método sencillo para saber si un grafo es no hamiltoniano saber si un grafo es no hamiltoniano problema muy complejo problema muy complejo

EjemploEjemplo: Este grafo es hamiltoniano: Este grafo es hamiltoniano

...pero este no ¡difícil de probar!...pero este no ¡difícil de probar!


07/08

Isomorfismo de grafosIsomorfismo de grafos IdeaIdea: En ocasiones dos grafos con diferentes : En ocasiones dos grafos con diferentes

vértices presentan la misma estructura:vértices presentan la misma estructura:

¿Cómo probarlo?¿Cómo probarlo? Buscando una función biyectiva Buscando una función biyectiva que convierta los vértices de uno en otro, que convierta los vértices de uno en otro, preservando la estructura de las aristaspreservando la estructura de las aristas

DefiniciónDefinición: Dos grafos : Dos grafos G=(V,A)G=(V,A), , G’=(V’,A’)G’=(V’,A’) son son isomorfosisomorfos si existe una función biyectiva si existe una función biyectiva f:Vf:VV’V’ tal que tal que {a,b}{a,b}A A {f(a),f(b)} {f(a),f(b)}A’A’


07/08

Isomorfismo de grafosIsomorfismo de grafos Ejemplo:Ejemplo:

Los dos grafos son isomorfos. Los dos grafos son isomorfos. DemostraciónDemostración: : Construimos f como se indica al lado de la figura. Se Construimos f como se indica al lado de la figura. Se tiene que:tiene que:

{1,2}{1,2}ff{a,f} {a,f} {6,8}{6,8}ff{b,c} {b,c} {1,6}{1,6}ff{a,b} {a,b} {2,8} {2,8}ff{f,c} {f,c} {4,3}{4,3}ff{h,g} {h,g} {1,4}{1,4}ff{a,h} {2,3}{a,h} {2,3}ff{f,g} {f,g} {5,7}{5,7}ff{d,e}{d,e}{4,5}{4,5}ff{h,d} {3,7}{h,d} {3,7}ff{g,e} {g,e} {6,5}{6,5}ff{b,d} {b,d} {8,7}{8,7}ff{c,e}{c,e}

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


07/08

Isomorfismo de grafosIsomorfismo de grafos ¿Y como saber si dos grafos ¿Y como saber si dos grafos no son no son

isomorfosisomorfos?? Hay que buscar alguna característica que Hay que buscar alguna característica que

diferencie la estructura de los dos grafos, diferencie la estructura de los dos grafos, como por ejemplo:como por ejemplo: Distinto número de vértices o de aristasDistinto número de vértices o de aristas Distinto número de ciclos de una longitud dadaDistinto número de ciclos de una longitud dada Distinto número de vértices con un mismo Distinto número de vértices con un mismo

grado ngrado n Aristas conectando vértices con dos grados Aristas conectando vértices con dos grados

tales que no existan aristas de las mismas tales que no existan aristas de las mismas características en el otro grafocaracterísticas en el otro grafo


07/08

Isomorfismo de grafosIsomorfismo de grafos EjemploEjemplo: ¿son isomorfos estos dos : ¿son isomorfos estos dos

grafos?grafos?

RespuestaRespuesta: no; G’ tiene un ciclo de : no; G’ tiene un ciclo de longitud 3 (b,d,c,b) y G no tiene ninguno longitud 3 (b,d,c,b) y G no tiene ninguno de longitud 3de longitud 3


07/08

Isomorfismo de grafosIsomorfismo de grafos

¿Son isomorfos? ___¿Son isomorfos? ___

¿por qué? _________________________-¿por qué? _________________________-


07/08

ÁrbolesÁrboles ÁrbolÁrbol: Grafo conexo y sin ciclos: Grafo conexo y sin ciclos EjemploEjemplo::

A menudo se selecciona un nodo especial al que A menudo se selecciona un nodo especial al que se llama se llama raízraíz, y se dibuja con la raíz en la parte , y se dibuja con la raíz en la parte superior, sus adyacentes más abajo y así superior, sus adyacentes más abajo y así sucesivamente:sucesivamente:


07/08

ÁrbolesÁrboles

Ejemplo: árbolEjemplo: árbol


07/08

EjemploEjemplo: Una estructura de : Una estructura de carpetas y ficheros es un árbolcarpetas y ficheros es un árbol

ÁrbolesÁrboles


07/08

ÁrbolesÁrboles

EjemplosEjemplos::

Análisis de expresiones

Árboles de búsqueda


07/08

ÁrbolesÁrboles

Un poco de Un poco de terminologíaterminología Los vértices de un árbol se llaman Los vértices de un árbol se llaman nodosnodos Los nodos descendientes inmediatos de un Los nodos descendientes inmediatos de un

nodo son sus nodo son sus hijoshijos, y el nodo superior es el , y el nodo superior es el padrepadre

A una secuencia descendente de nodos se A una secuencia descendente de nodos se le llama le llama ramarama

Los nodos sin hijos se llaman Los nodos sin hijos se llaman hojashojas, y los , y los que sí tienen hijos que sí tienen hijos nodos internosnodos internos

Un conjunto de árboles es un Un conjunto de árboles es un bosquebosque


07/08

ÁrbolesÁrboles

Algunas Algunas propiedadespropiedades..

Sea Sea G =(V,A)G =(V,A) un árbol. Entonces: un árbol. Entonces: Entre cada par de vértices x,y hay un Entre cada par de vértices x,y hay un

único caminoúnico camino Al quitar de A cualquier arista resulta Al quitar de A cualquier arista resulta

un bosque con 2 árbolesun bosque con 2 árboles Al añadir una arista nueva siempre se Al añadir una arista nueva siempre se

obtiene un cicloobtiene un ciclo |A| = |V| -1|A| = |V| -1


07/08

Árboles recubridoresÁrboles recubridores

Dado un grafo conexo Dado un grafo conexo G =(V,A)G =(V,A)

decimos que un árbol decimos que un árbol T T =(V’,A’)=(V’,A’) es un es un árbol recubridorárbol recubridor de de G G si si V=V’V=V’, y , y A A A’A’..

En el caso de grafos valorados interesa En el caso de grafos valorados interesa que la suma de pesos de las aristas del que la suma de pesos de las aristas del árbol sea lo más pequeña posible: árbol sea lo más pequeña posible:

árbol de recubrimiento mínimoárbol de recubrimiento mínimo..


07/08

Árbol de recubrimiento Árbol de recubrimiento mínimomínimo


07/08

Algoritmo de PrimAlgoritmo de Prim Se usa para construir árboles recubridores:Se usa para construir árboles recubridores:

1.1. Se elige un vértice cualquiera del grafo como Se elige un vértice cualquiera del grafo como vértice inicial y se marca.vértice inicial y se marca.

2.2. Mientras que queden vértices no marcados Mientras que queden vértices no marcados elegimos un vértice no marcado que esté elegimos un vértice no marcado que esté conectado con alguno marcado. Marcamos tanto conectado con alguno marcado. Marcamos tanto el vértice como una de las aristas que lo unen con el vértice como una de las aristas que lo unen con los ya marcadoslos ya marcados

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

rafac - matemática discreta - ucm 07/08 1 tema 5: grafos

Documents