1. Educación

Matem´
atica Aplicada a Tecnolog´ıas de la Informaci´
on
Curso 2014/2015
Dimensi´
on m´
etrica de grafos
1. Calcula la dimensi´
on m´etrica de los siguientes grafos:
K4
K2 + K2
K 1 + P4
W1,5
G1
G2
G3
G4
G5
G6
G7
G8
G9
G10
2. Calcula la dimensi´
on m´etrica del siguiente ´
arbol:
a
b
e
c
d
j
g
f
h
i
3. Calcula dim(K3,3 ) y dim(K3,4 ). Prueba que dim(Kn,m ) = n + m − 2, con n, m ≥ 2.
4. Calcula la dimensi´
on m´etrica del grafo grid 2-dimensional de tama˜
no n × m.
5. Calcula dim(W1,4 ) y dim(W1,5 ).
6. Demuestra que 2k − 1 ≤ dim(W1,n ) ≤ 2k para n = 5k y k ≥ 1, 2, . . ..
7. Demuestra que un grafo G con dim(G) = 2 no puede tener K5 como un subgrafo.