  We define a number of natural (from geometric and combinatorial points of
view) deformation spaces of valuations on finite graphs, and study functions
over these deformation spaces. These functions include both direct metric
invariants (girth, diameter), and spectral invariants (the determinant of the
Laplace operator, or complexity; bottom non-zero eigenvalue of the Laplace
operator). We show that almost all of these functions are, surprisingly,
convex, and we characterize the valuations extremizing these invariant
