grafos
Páginas: 5 (1120 palabras)
Publicado: 17 de mayo de 2013
Grafos
Carlos Delgado Kloos
Adaptado por Raquel M. Crespo
Ingeniería Telemática
Universidad Carlos III de Madrid
Grafos: concepto
Grafos
copyright (c) cdk@it.uc3m.es
2
Grafos: definición formal
Un grafo G=(V,E) consiste en
un conjunto V de nodos (vértices) y
un conjunto E de arcos (aristas)
Cada arista es un par (v,w), con v,w∈V
grafo dirigido: si el par está ordenadoSe puede asociar a las aristas una tercera
componente: coste (peso)
Grafos
copyright (c) cdk@it.uc3m.es
3
Ejemplo: red de vuelos
Grafos
copyright (c) cdk@it.uc3m.es
4
Ejemplo: diagrama de flujo
!
Grafos
copyright (c) cdk@it.uc3m.es
"
5
Ejemplo: diagrama de flujo
Grafos
copyright (c) cdk@it.uc3m.es
6
Ejemplo: red de ordenadores
Grafoscopyright (c) cdk@it.uc3m.es
7
Ejemplo: red de ordenadores
Grafos
copyright (c) cdk@it.uc3m.es
8
Ejemplo: circuito eléctrico
Grafos
copyright (c) cdk@it.uc3m.es
9
Ejemplo: circuito eléctrico
Grafos
copyright (c) cdk@it.uc3m.es
10
Ejemplo: circuito eléctrico
Grafos
copyright (c) cdk@it.uc3m.es
11
Ejemplo: circuito eléctrico
Grafos
copyright (c)cdk@it.uc3m.es
12
Ejemplo
&
# % %%'
$ &%
# (% % % % %)( )(%)(%)(%)
$ &)( )( %&% %
%
%
'
Grafos
copyright (c) cdk@it.uc3m.es
13
Terminología
Grafos
copyright (c) cdk@it.uc3m.es
14
Terminología
&
&
&
&
&
Grafos
copyright (c) cdk@it.uc3m.es
15
Terminología
"
!
"
"
!
#
$"
Grafos
copyright (c) cdk@it.uc3m.es
16 Propiedades
Sea G un grafo no dirigido con n vértices y m
arcos, entonces
v∈Gdeg(v)
= 2*m
Siempre:
m (n*(n-1))/2
Si G conexo: m n-1
Si G árbol:
m = n-1
Si G bosque: m n-1
Grafos
copyright (c) cdk@it.uc3m.es
17
Implementación
Matriz de adyacencia
Listas de adyacencia
Grafos
copyright (c) cdk@it.uc3m.es
18
Implementación:
matriz de adyacencia
a
b
c
d
ea
Ø
1
1
1
Ø
b
1
Ø Ø Ø
1
c
1
Ø Ø
1
1
d
1
Ø
1
Ø
1
e
Ø
1
1
1
Ø
&
!
#
"
Grafos
copyright (c) cdk@it.uc3m.es
19
Implementación:
listas de adyacencia
$
&
*
!
+ !
+ !
&
(
)
'
,
-!
%
$
%
&
'
(
)
&
Grafos
$ & cdk@it.uc3m.es
$%
copyright (c)
()&'( %')
20
Spanning tree
Un spanning tree de un grafo G es un subgrafo G'
de G, tal que:
G' es un árbol
G' contiene todos los vértices de G
&
&
). 0 '1-)2. 02 '21
/
/
3
)2
)
⇔ 02 ⊆ 0 ∧ '2 ⊆ '
*
,
+
.
Grafos
,/
,/
0%
copyright (c) cdk@it.uc3m.es
21
Recorridos y búsquedas
1.
2.
Grafos
en profundidad (depth-first search)
en anchura(breadth-first search)
copyright (c) cdk@it.uc3m.es
22
Búsqueda en profundidad
$
%
'
(
)
4
6
8
5
7
9
Grafos
&
:
*
copyright (c) cdk@it.uc3m.es
23
Búsqueda en profundidad
$
'
(
)
4
6
8
5
Grafos
%
&
7
9
copyright (c) cdk@it.uc3m.es
:
*
24
Búsqueda en profundidad
$
%
'
(
)
4
6
85
7
9
Grafos
&
:
*
copyright (c) cdk@it.uc3m.es
25
Búsqueda en profundidad
$
%
&
'
(
)
4
6
8
5
7
9
:
;
Grafos
copyright (c) cdk@it.uc3m.es
*
26
Búsqueda en anchura
$
%
'
(
)
4
6
8
5
7
9
Grafos
&
:
*
copyright (c) cdk@it.uc3m.es
27
Búsqueda en anchura
$
'
()
4
6
8
5
Grafos
%
&
7
9
copyright (c) cdk@it.uc3m.es
:
*
28
Búsqueda en anchura
$
%
'
(
)
4
6
8
5
7
9
Grafos
&
:
*
copyright (c) cdk@it.uc3m.es
29
Búsqueda en anchura
$
'
(
)
4
6
8
5
Grafos
%
&
7
9
copyright (c) cdk@it.uc3m.es
:
*
30
Búsqueda en anchura...
Carlos Delgado Kloos
Adaptado por Raquel M. Crespo
Ingeniería Telemática
Universidad Carlos III de Madrid
Grafos: concepto
Grafos
copyright (c) cdk@it.uc3m.es
2
Grafos: definición formal
Un grafo G=(V,E) consiste en
un conjunto V de nodos (vértices) y
un conjunto E de arcos (aristas)
Cada arista es un par (v,w), con v,w∈V
grafo dirigido: si el par está ordenadoSe puede asociar a las aristas una tercera
componente: coste (peso)
Grafos
copyright (c) cdk@it.uc3m.es
3
Ejemplo: red de vuelos
Grafos
copyright (c) cdk@it.uc3m.es
4
Ejemplo: diagrama de flujo
!
Grafos
copyright (c) cdk@it.uc3m.es
"
5
Ejemplo: diagrama de flujo
Grafos
copyright (c) cdk@it.uc3m.es
6
Ejemplo: red de ordenadores
Grafoscopyright (c) cdk@it.uc3m.es
7
Ejemplo: red de ordenadores
Grafos
copyright (c) cdk@it.uc3m.es
8
Ejemplo: circuito eléctrico
Grafos
copyright (c) cdk@it.uc3m.es
9
Ejemplo: circuito eléctrico
Grafos
copyright (c) cdk@it.uc3m.es
10
Ejemplo: circuito eléctrico
Grafos
copyright (c) cdk@it.uc3m.es
11
Ejemplo: circuito eléctrico
Grafos
copyright (c)cdk@it.uc3m.es
12
Ejemplo
&
# % %%'
$ &%
# (% % % % %)( )(%)(%)(%)
$ &)( )( %&% %
%
%
'
Grafos
copyright (c) cdk@it.uc3m.es
13
Terminología
Grafos
copyright (c) cdk@it.uc3m.es
14
Terminología
&
&
&
&
&
Grafos
copyright (c) cdk@it.uc3m.es
15
Terminología
"
!
"
"
!
#
$"
Grafos
copyright (c) cdk@it.uc3m.es
16 Propiedades
Sea G un grafo no dirigido con n vértices y m
arcos, entonces
v∈Gdeg(v)
= 2*m
Siempre:
m (n*(n-1))/2
Si G conexo: m n-1
Si G árbol:
m = n-1
Si G bosque: m n-1
Grafos
copyright (c) cdk@it.uc3m.es
17
Implementación
Matriz de adyacencia
Listas de adyacencia
Grafos
copyright (c) cdk@it.uc3m.es
18
Implementación:
matriz de adyacencia
a
b
c
d
ea
Ø
1
1
1
Ø
b
1
Ø Ø Ø
1
c
1
Ø Ø
1
1
d
1
Ø
1
Ø
1
e
Ø
1
1
1
Ø
&
!
#
"
Grafos
copyright (c) cdk@it.uc3m.es
19
Implementación:
listas de adyacencia
$
&
*
!
+ !
+ !
&
(
)
'
,
-!
%
$
%
&
'
(
)
&
Grafos
$ & cdk@it.uc3m.es
$%
copyright (c)
()&'( %')
20
Spanning tree
Un spanning tree de un grafo G es un subgrafo G'
de G, tal que:
G' es un árbol
G' contiene todos los vértices de G
&
&
). 0 '1-)2. 02 '21
/
/
3
)2
)
⇔ 02 ⊆ 0 ∧ '2 ⊆ '
*
,
+
.
Grafos
,/
,/
0%
copyright (c) cdk@it.uc3m.es
21
Recorridos y búsquedas
1.
2.
Grafos
en profundidad (depth-first search)
en anchura(breadth-first search)
copyright (c) cdk@it.uc3m.es
22
Búsqueda en profundidad
$
%
'
(
)
4
6
8
5
7
9
Grafos
&
:
*
copyright (c) cdk@it.uc3m.es
23
Búsqueda en profundidad
$
'
(
)
4
6
8
5
Grafos
%
&
7
9
copyright (c) cdk@it.uc3m.es
:
*
24
Búsqueda en profundidad
$
%
'
(
)
4
6
85
7
9
Grafos
&
:
*
copyright (c) cdk@it.uc3m.es
25
Búsqueda en profundidad
$
%
&
'
(
)
4
6
8
5
7
9
:
;
Grafos
copyright (c) cdk@it.uc3m.es
*
26
Búsqueda en anchura
$
%
'
(
)
4
6
8
5
7
9
Grafos
&
:
*
copyright (c) cdk@it.uc3m.es
27
Búsqueda en anchura
$
'
()
4
6
8
5
Grafos
%
&
7
9
copyright (c) cdk@it.uc3m.es
:
*
28
Búsqueda en anchura
$
%
'
(
)
4
6
8
5
7
9
Grafos
&
:
*
copyright (c) cdk@it.uc3m.es
29
Búsqueda en anchura
$
'
(
)
4
6
8
5
Grafos
%
&
7
9
copyright (c) cdk@it.uc3m.es
:
*
30
Búsqueda en anchura...
Leer documento completo
Regístrate para leer el documento completo.