P.I.G.A.L.E.
1.3.9
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

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

1.5.4