For your second question, if by *probability* you mean $$\lim_{n \to \infty} \frac{|S_n|}{|G_n|},$$ where $S_n$ is the set of all possible spectra of simple $n$-vertex graphs, and $G_n$ is the set of isomorphism classes of simple $n$-vertex graphs, then it is conjectured that the above probability is 1.  That is, almost all graphs are determined by their spectrum.  

See my answer to this [question](http://mathoverflow.net/questions/49226/classes-of-graphs-for-which-isospectrum-implies-isomorphism/49256#49256) for more information and references.