le graphe adjoint

Salut,
Je suis en train d'écrire un programme :
pour ce moment j'ai réussi à :
- la lecture du graph directe à partir d'un fichier
- création une matrice
- vérifier: si mon graphe est le adjoint

ici je voudrais transforme mon graphe adjoint dans le graphe d'origine
Qu'est-ce que ça veut dire?
wiki : Chaque sommet du line graph ( cas du graphe adjoint mais pour moi c'est assez) est étiqueté avec les extrémités de l'arrête correspondant dans le graphe d'origine.

http://1.bp.blogspot.com/-ABfm118Lb6...1600/graf2.jpg
le graphe d'origine à gauche et le adjoint à droite

Est-ce il est possible de le faire sans étiquetage?
J'utilise une matrice d'adjacence.