On considère le graphe simple orienté G défini sur l'ensemble S = {A, B, C, D}.
                                                      (m11 m12 m13 m14)
                                                      (m21 m22 m23 m24)
Pour les points A, B, C, D dans cet ordre, on note M =(m31 m32 m33 m34)
                                                      (m41 m42 m43 m44)
(m11, ... et m44 {0 ; 1}) la matrice adjacente à G et la matrice de sa fermeture transitive .
On suppose que :
. G est un graphe sans boucle ;
                     (1 1 1 1)
                     (0 0 0 1)
.=(1 1 1 1)
                     (0 0 0 0)


1.En interprétant les lignes 2 et 4 de la matrice , et considérant le fait que G est sans boucle, montrer que la matrice adjacente M est nécessairement de la forme
(0 m13 m13 m14)
(0   0   0   0)
(m31 m32 0 m34)
(0   0   0   0)
où m12, m13, m14, m31 et m34 {O ; 1}.

2.Calculer la matrice M².

3.Sachant qu'il n'existe que 6 chemins de longueur 2 : 1 allant de A à A, 2 allant de A à D, 1 allant de C à B, 1 allant de C à C et 1 allant de C à D :
a) Déterminer la valeur de m12, m13, m14, m31, m32 et m34.
b) Définir G en extension et donner sa représentation sagittale.

4.a) Combien existe-t-il de chemins de longueur 3 ?
b) Existe-t-il des chemins hamiltoniens ?