Biconnexité
Cette feuille en Postscript

1  Qu'est qu'un graphe, exactement ?

Dans cette séance un graphe est défini comme une paire (X,A) où X est un ensemble (fini) de sommets si et A un ensemble d'arcs notés si → sj dans le cas des graphes orientés et si ↔ sj dans le cas des graphes non-orientés. Dans ce dernier cas si ↔ sj et sj ↔ si désignent le même arc.
  1. Un chemin, est une suite de sommets et d'arcs s1 → s2 → … → sk. Un chemin est simple quand tous ses sommets sont deux à deux distincts.

    Monter que si il existe un chemin de s à s' (on suppose s ≠ s'), alors il existe un chemin simple de s à s'.

  2. Un cycle est un chemin de s à s dont tous les arcs sont deux à deux distincts et dont tous les sommets sont distincts, sauf pour s qui apparaît exactement deux fois.

    Montrer, dans un graphe orienté, que si il existe un chemin de s à lui même, alors il existe un cycle. Qu'en est-il pour les graphes non-orientés ?

  3. Un arbre T est défini rapidement inductivement, comme soit un sommet unique et aucun arc, ou un sommet-racine s, n sommets fils (c'est-à dire n arcs s → s1, ...s → sn) et n sous arbres T1, ...Tn de racines respectives s1, ...sn. En tentant de montrer qu'un arbre ne contient pas de cycle, préciser la définition.
Solution.


2  Profondeur d'abord (Tarjan)

Voici un parcours en profondeur d'abord, tel tel que présenté par R. Tarjan.
  static private int numOrder ;
  static private int [] num ;
  static private void doTarjan (int s, int pere) {
    numOrder++ ; num[s] = numOrder ;

    for (List p = succ[s] ; p != null ; p = p.next) {
      int n = p.val ;
      if (num[n] == 0) {
        System.out.println("Arbre : " + s + " -> " + n) ;
        doTarjan(n, s) ;
      } else if (num[n] < num[s] && n != pere) {
        System.out.println("Retour : " + s + " -> " + n) ;
      }
    }
  }

  static void tarjan(int s) {
    numOrder = 0 ; num = new int[succ.length] ;
    doTarjan(s,s) ;
  }
  1. R. Tarjan prétend que, appliqué à un graphe non-orienté, le parcours en profondeur d'abord revient à orienter le graphe. Justifier, puis nuancer.

  2. Parcourir le graphe suivant.


  3. Un palmier est un graphe orienté (X,A), dont les arcs se partionnent en T et R tels que : (X,T) est un arbre, les arcs de R relient un sommet à un de ses ancêtres dans (X,T). Justifier que le parcours construit un palmier.

  4. Discuter la présence de cycles dans le graphe d'origine selon que le parcours affiche « Retour » ou pas. Puis considérer le cas d'un graphe orienté.
Solution.


3  Points d'articulation

On considère désormais un graphe connexe et non-orienté (X,A), sans arcs d'un sommet à lui même. Un point d'articulation a est un sommet tel qu'il existe deux autres sommets distincts s et t connectés et que a appartient à tous les chemins de s à t. (Autrement dit la suppression du sommet a coupe à coup sûr le lien entre s et t). Un graphe qui ne contient pas de point d'articulation est biconnexe.

Par ailleurs on peut définir une relation (d'équivalence) sur les arcs, deux arcs sont équivalents quand il sont égaux ou si existe un cycle les contenant tous deux. Un graphe est biconnexe quand tous ses arcs sont en relation.
  1. Les graphes suivants sont-ils biconnexes ?
        


  2. Montrer l'équivalence des deux définitions de graphe biconnexe.

  3. Toujours selon Tarjan, le programme suivant identifie les points d'articulation.
      // renvoie le numéro du point d'attache
          private static int doFindArticulation (int s, int pere) {
            int lowpt ; boolean found = false ;
        ++numOrder ; lowpt = num[s] = numOrder ;

            for (List p = succ[s] ; p != null ; p = p.next) {
              int n = p.val ;
              if (num[n] == 0) {
                int lowN = doFindArticulation(n, s) ;
            lowpt = Math.min(lowN,lowpt) ;
                if (lowN >= num[s]) {
              System.out.println("Articulation : " + s) ;
            }
          }     else if (num[n] < num[s] && n != pere) {
            lowpt = Math.min(num[n],lowpt) ;
          }
        }
            return lowpt ;
      }

          static void findArticulations(int s) {
        numOrder = 0 ; num =     new int[succ.length] ;
            int nfils = 0 ;

        numOrder++ ; num[s] = numOrder ;
            for (List p = succ[s] ; p != null ; p = p.next) {
              int n = p.val ;
              if (num[n] == 0) {
            doFindArticulation(n, s) ;
            nfils++ ;
          }
        }
            if (nfils > 1)
          System.out.println("La racine " + s + " est un point d'articulation") ;
      }
    Appliquer le programme au graphe de l'exercice précédent.

  4. Un sommet peut-il être affiché deux fois ? Si oui donner un exemple.

  5. Justifier la correction du programme. Le comparer à celui du poly.
Solution.


4  Composantes biconnexes

Les composantes biconnexes sont intuitivement les composantes connexes du graphe une fois supprimés les point d'articulation. Plus précisément,la relation d'équivalence sur les arcs définit les classes d'équivalence A1, A2, ..., Ak des arcs du graphe (X,A). On peut alors définir les ensembles X1, X2, ..., Xk de sommets participant respectivement aux arcs de A1, A2, ..., Ak.

Il est évident que les graphes (Xi,Ai) sont biconnectés (et en un sens maximaux). Il semble logique que les points d'articulations sont les éventuels points communs des Xi (on ne tentera aucune preuve).
  1. Trouver les composantes biconnexes des graphes non-biconnexes déjà vus.

  2. Concevoir, en utilisant une pile d'arcs, un programme qui affiche les (arcs des) composantes biconnexes, à raison d'une ligne par composante biconnexe.
Solution.


5  Calcul naïf des composantes fortement connexes

  1. Rappeler la définition des composantes fortement connexes dans un graphe orienté.
  2. Caractériser la composante fortement connexe d'un sommet à l'aide du graphe des prédécesseurs (ou graphe inverse).
  3. Concevoir un algorithme simple pour afficher les composantes fortement connexes. Indication : on utilisera le graphe des des prédécesseurs, et deux méthodes d'exploration partageant un tableau de marques.
  4. Trouver un exemple d'exécution qui montre que l'algorithme est au moins quadratique (en le nombre de sommet).
  5. Programmer.
Solution.


This document was translated from LATEX by HEVEA and HACHA.