GRAPHE ORIENTE 2 BTS

   GRAPHE ORIENTE 2         SUITE DU COURS        BTS  1      NOV.08

 3. Successeurs , prédécesseurs.

          Pour l'arc orienté ( x i  , xj ) :

            x i   est un prédécesseur de x j .

             x j   est un successeur  de x i .

 4. Tableau des successeurs et des prédécesseurs.

       Soit le graphe orienté comportant les arcs orientés suivants:

          ( x1   ,  x1 ) , ( x1 , x2 ), ( x2  , x3 ), ( x1 ,  x3  ). 

PREDECESSEURS SOMMETS SUCCESSEURS
x1 x1 x1   x2   x3
x1 x2 x3
x1  x2 x3  

       5. Tableau permettant de construire la matrice d'adjacence ou adjacente M du graphe orienté.

            Soit le graphe orienté comportant les arcs orientés suivants:  

          ( x1   ,  x1 ) , ( x1 , x2 ), ( x2  , x3 ), ( x1 ,  x3  ). 

ORIGINE     \  EXTREMITE x1 x2 x3
x1 1 1 1
x2 0 0 1
x3 0 0 0

                      La matrice obtenue en ne conservant que les 0 et les 1  en rouge est

                      la matrice d'ADJACENCE du graphe orienté.

                     On écrit: 

                         Trmar1

             Le 1 situé à la deuxième ligne et à la troisième colonne signifie qu'il existe un arc ( x2  , x3  )

             dans le graphe orienté. 

             Le 0 situé à la troisième ligne et à la deuxième colonne signifie  qu'il n'existe pas

             d'arc  ( x3 , x 2 ) dans le graphe orienté.

           6. CHEMIN.

   C'est, dans un graphe orienté, des arcs "bout à bout" qui relient un sommet à un autre.

   Le nombre d'arcs orienté qui constituent un chemin est sa LONGUEUR.

    Par exemple pour le graphe orienté comportant les arcs orientés suivants:

     ( x1  ,  x1 ) , ( x1 , x2 ), ( x2  , x3 ), ( x1 ,  x3  ). 

            x1  x1  x2 x3  est un chemin de longueur 3.

      7. CIRCUIT.

         C'est un chemin qui retourne au sommet de départ.

     8. CHEMIN  HAMILTONIEN.

        C'est un chemin qui passe une et une seule fois par tous les sommets.

      9. RACINE d'un graphe orienté.

              La racine d'un graphe , quand elle existe, est un sommet à partir duquel

               on peut joindre tous les autres sommets à l'aide d'un chemin.

                Par exemple dans un arbre généalogique , un ancêtre commun .

                 Il y a bien d'autres cas sans arborescence.

          10. Question: Comment déterminer le nombre de chemins de longueur p 

         allant de xi à xj  pour un graphe orienté de matrice d'Adjacence M ?

                   Propriété admise.

                Soit p  un entier naturel non nul.

                       On considère la matrice    M ×M ×  ..... × M = Mp

                  • L'entier   aij   situé à la ligne i et la colonne j donne le nombre de

                   chemins  de longueur p allant de xi  à xj  .

                  •  La somme des termes de la colonne j donne le nombre

                     de chemins de longueur p allant à xj .

                  • La somme des termes de la ligne i donne le nombre de chemins

                    de longueur p partant de xi .

                   • La somme des termes de la matrice Mp  donne le nombre de chemins

                   de longueur p .

           11. MATRICE BOOLEENNE.

                 C'est une matrice ne comportant que des 0 ou 1 comme termes.

           12. Matrice M[p] .

                   C'est une matrice booléenne.

                 Elle s'obtient en remplaçant tous les termes non nuls de Mp , par 1 et en laissant les 0.

              Si le terme de  M[p]  situé à la ligne i et la colonne j est non nul ( c-à-d 1 )

              cela veut dire qu'il y a au moins un chemin de longueur  p de xi à xj  .

               ( Mais cela ne dit pas combien il y en a . )

----------------------------------------------------