GrafosIII
Páginas: 14 (3421 palabras)
Publicado: 17 de julio de 2015
Conceptos sobre grafos
9
9
9
9
Tema 9: GRAFOS
Tercera Parte
Estructuras de Datos y Algoritmos
Curso 2002/03
Subgrafos
Conectividad
Árboles
Árboles de recubrimiento
Problema ARCM: dado un grafo no dirigido y ponderado,
encontrar un árbol de recubrimiento de coste mínimo
Soluciones:
Algoritmo de Kruskal
Algoritmo de Prim
MFSET: estructura de
conjuntos disjuntos
Grafos. EDA. Curso 2002/03Subgrafos
2
Conectividad de un grafo
9 Un Grafo G’=(V’,E’) es un subgrafo de G=(V,E) si:
• V’ V
• E’ E
9
Un gnd es conexo si cualquier par de vértices están conectados por un
camino
9 Las componentes conexas de un Grafo son las clases de equivalencia en
9 Dado un conjunto V’ V, el subgrafo de G inducido por V’ es
V definidas por la relación R = “es alcanzable desde”
G’=(V’,E’) : E’ = {(u,v) E : u,v V’ }
Ejemplo: las componentes conexas del Grafo son ...
Ejemplo: el subgrafo inducido por V’ = {1, 2, 3, 6 } es …
1
2
3
4
5
6
1
2
3
6
Grafos. EDA. Curso 2002/03
3
1
2
3
4
5
6
Grafos. EDA. Curso 2002/03
4
Árboles
9
Árboles
9 TEOREMA: sea G=(V,E) un gnd. Las siguientes afirmaciones son equivalentes:
• G es un Árbol (libre)
• cualquier par de Vértices en Gestán conectados por un único camino
simple
• G es conexo y |E| = |V| - 1
• G es acíclico pero si añadimos una Arista a E, el Grafo resultante
contiene un ciclo
Un Grafo no dirigido Acíclico y conexo es un Árbol (libre)
9 Un Grafo no dirigido Acíclico
es un Bosque
Demostración en Cormen, págs. 1085-1087
9 Un Árbol con raíz es un Árbol (libre) con un Vértice distinguido
denominado raíz
ÁrbolGrafo
Bosque
(libre)
Grafos. EDA. Curso 2002/03
Grafos. EDA. Curso 2002/03
5
Árbol de recubrimiento (Spanning Tree) de un gnd
9 Un Árbol de recubrimiento del Grafo G=(V,E) es un Árbol Libre T=(V’,E’)
tal que:
• V ’ V
• E’ E
Árbol de recubrimiento (Spanning Tree) de un gnd
Ejemplo: interconectar N pin’s con N - 1 cables, cada uno de los
cuales conecta 2 pin’s, utilizando la menor cantidad decable posible
Ejemplo: interconectar N pin’s con N - 1 cables, cada uno de los
cuales conecta 2 pin’s, utilizando la menor cantidad de cable posible
4
aa
8
8
b
11
7
h
2
i
1
7
c
d
2
f
aa
e
11
8
10
Grafos. EDA. Curso 2002/03
V’ =V,13|V’|=N=9
•• |E|
• E’ E, |E’|=N-1=8
con
conPeso
Pesomínimo
mínimo
7
8
7
h
11
7
h
2
i
1
8
b
4
aa
8
b
4
• |V| =con:
N=9
T=(V’,E’)
9
14
4g
G=(V,E) ponderado con:
6
2
i
1
7
cc
G=(V,E) ponderado con:
d
14
4
g
2
7
c
g
e
f
10
d
9
14
4
2
f
• |V| =con:
N=9
T=(V’,E’)
9
V’ =V,13|V’|=N=9
•• |E|
• E’ E, |E’|=N-1=8
con
conPeso
Pesomínimo
mínimo
e
10
Grafos. EDA. Curso 2002/03
8
Árbol de recubrimiento (Spanning Tree) de un gnd
Ejemplo: interconectar N pin’s con N - 1 cables, cada uno de los
cuales conecta 2 pin’s,utilizando la menor cantidad de cable posible
b
b
4
11
aa
8
8
7
h
7
cc
2
i
1
dd
2
• |V| =con:
N=9
T=(V’,E’)
9
14
4
gg
G=(V,E) ponderado con:
e
e
V’ =V,13|V’|=N=9
•• |E|
• E’ E, |E’|=N-1=8
con
conPeso
Pesomínimo
mínimo
10
f
E’= { a,b), b,c), c,i), c,f), f,g), g,h), c,d), d,e) }
Grafos. EDA. Curso 2002/03
9
Problema ARCM
2
5
6
6
c
4
e
1
d
3
b
4
2
5
66
c
4
Grafos. EDA. Curso 2002/03
Encontrar T E:
• G’=(V,T) es un subgrafo conexo y acíclico de (V,E)
• la suma de los pesos de los arcos de T sea mínima
•T es acíclico, conexo y no dirigido, entonces es un árbol
•Se debe extender por todos los vértices
•La suma de los pesos de sus arcos debe ser mínima
Grafos. EDA. Curso 2002/03
10
Algoritmo de Kruskal: Idea Voraz
] Árbol RCM Dado un gndG=(V,E), un AEM es un árbol libre
T=(V’,E’) tal que V’=V y E’E.
] Definición del problema: Dado un gnd ponderado
G=(V,E,p), encontrar un AEM de G, T=(V’,E’) , tal que la
suma de los pesos de las |V|-1 aristas de T sea mínimo.
8 a
9
8 a
9
4
Dado un grafo no dirigido y conexo G=(V,E), y
ponderado con p:EoR+
Árbol de extensión de coste mínimo
con Peso mínimo 37
b
Problema ARCM
e
]...
9
9
9
9
Tema 9: GRAFOS
Tercera Parte
Estructuras de Datos y Algoritmos
Curso 2002/03
Subgrafos
Conectividad
Árboles
Árboles de recubrimiento
Problema ARCM: dado un grafo no dirigido y ponderado,
encontrar un árbol de recubrimiento de coste mínimo
Soluciones:
Algoritmo de Kruskal
Algoritmo de Prim
MFSET: estructura de
conjuntos disjuntos
Grafos. EDA. Curso 2002/03Subgrafos
2
Conectividad de un grafo
9 Un Grafo G’=(V’,E’) es un subgrafo de G=(V,E) si:
• V’ V
• E’ E
9
Un gnd es conexo si cualquier par de vértices están conectados por un
camino
9 Las componentes conexas de un Grafo son las clases de equivalencia en
9 Dado un conjunto V’ V, el subgrafo de G inducido por V’ es
V definidas por la relación R = “es alcanzable desde”
G’=(V’,E’) : E’ = {(u,v) E : u,v V’ }
Ejemplo: las componentes conexas del Grafo son ...
Ejemplo: el subgrafo inducido por V’ = {1, 2, 3, 6 } es …
1
2
3
4
5
6
1
2
3
6
Grafos. EDA. Curso 2002/03
3
1
2
3
4
5
6
Grafos. EDA. Curso 2002/03
4
Árboles
9
Árboles
9 TEOREMA: sea G=(V,E) un gnd. Las siguientes afirmaciones son equivalentes:
• G es un Árbol (libre)
• cualquier par de Vértices en Gestán conectados por un único camino
simple
• G es conexo y |E| = |V| - 1
• G es acíclico pero si añadimos una Arista a E, el Grafo resultante
contiene un ciclo
Un Grafo no dirigido Acíclico y conexo es un Árbol (libre)
9 Un Grafo no dirigido Acíclico
es un Bosque
Demostración en Cormen, págs. 1085-1087
9 Un Árbol con raíz es un Árbol (libre) con un Vértice distinguido
denominado raíz
ÁrbolGrafo
Bosque
(libre)
Grafos. EDA. Curso 2002/03
Grafos. EDA. Curso 2002/03
5
Árbol de recubrimiento (Spanning Tree) de un gnd
9 Un Árbol de recubrimiento del Grafo G=(V,E) es un Árbol Libre T=(V’,E’)
tal que:
• V ’ V
• E’ E
Árbol de recubrimiento (Spanning Tree) de un gnd
Ejemplo: interconectar N pin’s con N - 1 cables, cada uno de los
cuales conecta 2 pin’s, utilizando la menor cantidad decable posible
Ejemplo: interconectar N pin’s con N - 1 cables, cada uno de los
cuales conecta 2 pin’s, utilizando la menor cantidad de cable posible
4
aa
8
8
b
11
7
h
2
i
1
7
c
d
2
f
aa
e
11
8
10
Grafos. EDA. Curso 2002/03
V’ =V,13|V’|=N=9
•• |E|
• E’ E, |E’|=N-1=8
con
conPeso
Pesomínimo
mínimo
7
8
7
h
11
7
h
2
i
1
8
b
4
aa
8
b
4
• |V| =con:
N=9
T=(V’,E’)
9
14
4g
G=(V,E) ponderado con:
6
2
i
1
7
cc
G=(V,E) ponderado con:
d
14
4
g
2
7
c
g
e
f
10
d
9
14
4
2
f
• |V| =con:
N=9
T=(V’,E’)
9
V’ =V,13|V’|=N=9
•• |E|
• E’ E, |E’|=N-1=8
con
conPeso
Pesomínimo
mínimo
e
10
Grafos. EDA. Curso 2002/03
8
Árbol de recubrimiento (Spanning Tree) de un gnd
Ejemplo: interconectar N pin’s con N - 1 cables, cada uno de los
cuales conecta 2 pin’s,utilizando la menor cantidad de cable posible
b
b
4
11
aa
8
8
7
h
7
cc
2
i
1
dd
2
• |V| =con:
N=9
T=(V’,E’)
9
14
4
gg
G=(V,E) ponderado con:
e
e
V’ =V,13|V’|=N=9
•• |E|
• E’ E, |E’|=N-1=8
con
conPeso
Pesomínimo
mínimo
10
f
E’= { a,b), b,c), c,i), c,f), f,g), g,h), c,d), d,e) }
Grafos. EDA. Curso 2002/03
9
Problema ARCM
2
5
6
6
c
4
e
1
d
3
b
4
2
5
66
c
4
Grafos. EDA. Curso 2002/03
Encontrar T E:
• G’=(V,T) es un subgrafo conexo y acíclico de (V,E)
• la suma de los pesos de los arcos de T sea mínima
•T es acíclico, conexo y no dirigido, entonces es un árbol
•Se debe extender por todos los vértices
•La suma de los pesos de sus arcos debe ser mínima
Grafos. EDA. Curso 2002/03
10
Algoritmo de Kruskal: Idea Voraz
] Árbol RCM Dado un gndG=(V,E), un AEM es un árbol libre
T=(V’,E’) tal que V’=V y E’E.
] Definición del problema: Dado un gnd ponderado
G=(V,E,p), encontrar un AEM de G, T=(V’,E’) , tal que la
suma de los pesos de las |V|-1 aristas de T sea mínimo.
8 a
9
8 a
9
4
Dado un grafo no dirigido y conexo G=(V,E), y
ponderado con p:EoR+
Árbol de extensión de coste mínimo
con Peso mínimo 37
b
Problema ARCM
e
]...
Leer documento completo
Regístrate para leer el documento completo.