SourceForge Logo
Public Implementation of a Graph Algorithm
Library and Editor

H. de Fraysseix      P. Ossona de Mendez

Todo List

File netcut.h
Eigenspaces dimensions optimization. Optimize eigenspaces dimensions over the distances defined on the cellular algebra $ \mathfrak{A} $ generated by the adjacency matrix $ A $

File netcut.h
Q distance. Test the distance

\[ d^2(i,j)=\begin{cases} 0,&\text{if $i=j$}\\ 1,&\text{if $i$ and $j$ are non adjacent}\\ 1-\frac{1}{\sqrt{d(i)d(j)}},&\text{otherwise} \end{cases}\]

Remark that the matrix $ \left(\frac{A_{i,j}}{\sqrt{d(i)d(j)}}\right)_{i,j} $ is symmetric, stochastic and hence have real eigenvalues, the largest one being equal to $ 1$. Nevertheless, a multigraph is not reconstructible from this distance as replacing every edge by $ k $ parallel edges does not affect the distances between the vertices.

Generated on Thu Jan 31 16:51:36 2008 for Pigale by  doxygen 1.5.4