29 - Graphe : cycles et parcours

⏪

⏬

⏩

1 - Cycle

2 - profondeur

3 - Graphe orienté

4 - Les chemins

5 - Non orienté

6 - FAQ

Imaginons que nous désirions voyager d'un sommet A à un sommet B. Si ce voyage est possible :

le parcours en largeur permettra de trouver l'UN des chemins optimaux s'il en existe un.
le parcours en profondeur de base permettra peut-être de trouver UN chemin (même s'il existe ce n'est pas certain qu'on le trouve et il ne sera pas nécessairement optimal).

Aujourd'hui, nous allons analyser le parcours en profondeur d'un graphe de façon à

Détecter la présence d'un cycle (au programme)
Utiliser le parcours en profondeur pour analyser la topologie du graphe et supprimer quelques arêtes de façon à empêcher un programme-robot de tourner à l'infini sur le graphe (pas au programme mais sympa pour le Grand Oral).

Lorsque ce parcours est utilisé, il permet de trouver TOUS les chemins en mettant de côté les arêtes problématiques car engendrant d'un cycle.

Logiciel nécessaire pour l'activité : -

Prérequis : Algo : Parcours en profondeur d'un Arbre

Evaluation ✎ : -

Documents de cours : open document ou pdf

MODE COURS (cacher les questions)

1 - Détection de cycle dans un graphe

⇩ ⇧ ⤊

L'une des utilisations du parcours en profondeur est de détecter la présence de cycle dans un graphe non orienté.

On peut utiliser une technique similaire avec un parcours en largeur mais on ne va alors détecter que la présence d'un cycle possible depuis le sommet de départ choisi.

Avec le parcours en profondeur, nous allons pouvoir détecter la présence d'un cycle dans le graphe, sans considération de point de départ.

1.1 Principe général de la détection dans un graphe NON ORIENTE

Le principe est simple : on a découvert un cycle si nous sommes en train de visiter un sommet u :

qui mène à un autre sommet v GRIS(c'est à dire déjà visité)
et que v n'est pas le parent de u (sinon cela veut juste dire qu'on vient de bouger de v vers u)

Si ces deux conditions sont réunies, cela veut dire qu'on pourrait repartir dans un sommet déjà visité et revenir une deuxième fois au même endroit. C'est bien un cycle.

Sans gestion du parent, le chemin A-D-A formerait un cycle sur le graphe non orienté suivant. Or, souvenez vous que, lorsqu'on utilise une arête, on considère qu'elle est utilisé dans les deux sens.

Pour parvenir à détecter le parent, il faut donc :

Soit gèrer la notion de parent et couleur (comme avec notre dictionnaire parcours
Soit gérer les sommets découverts et mémoriser qui est le parent du sommet courant.

Commençons par simplement adapté le parcours en profondeur pour voir comment nous pourrions détecter les cycles.

01° Lancer, lire et commenter les lignes de ce programme pour en comprendre le principe.

# CONSTANTES ======================================================================
 
BLANC = 0
GRIS  = 1
NOIR  = 2
 
 
# FONCTIONS ======================================================================
 
def est_cyclique(g:'dict[int, list]') -> bool:
    """Prédicat qui renvoie True si le graphe possède un cycle (au moins un)"""
 
    # INITIALISATION
    parcours = {}              # Création du dictionnaire (qui sera un dict de dict)
    for u in g.keys():         # ...
        parcours[u] = {}       # ...
        parcours[u]['couleur'] = BLANC    # Initialisation de la couleur
        parcours[u]['parent'] = None      # Initialisation du parent
 
    # PARCOURIR
    for u in g.keys():                              # ...
        if parcours[u]['couleur'] == BLANC:         # ...
            if visiter_profondeur(u, g, parcours):  # ...
                return True                         # ...
 
    return False       # si on arrive ici, c'est qu'il n'y a pas de cycle dans le graphe
 
def visiter_profondeur(u:int, g:'dict[int, list]', parcours:dict) -> bool:
    """Visite un sommet u en particulier et renvoie True si on détecte un cycle"""
 
    parcours[u]['couleur'] = GRIS               # ...
 
    for v in g[u]:                              # ...
        if parcours[v]['couleur'] == GRIS and parcours[u]['parent'] != v:
            return True        
        elif parcours[v]['couleur'] == BLANC:       # ...
            parcours[v]['parent'] = u               # ...
            if visiter_profondeur(v, g, parcours):  # ...
                return True                         # ...
 
    parcours[u]['couleur'] = NOIR               # u est totalement exploré
    return False   # ...
 
 
# PROGRAMME PRINCIPAL =========================================================
 
if __name__ == '__main__':
    graphe = {
    5: [9, 1],
    6: [2, 7, 8],
    7: [4, 6],
    8: [6, 9],
    9: [5, 8],
    1: [3, 2, 5],
    2: [3, 1, 4, 6],
    3: [1, 2, 4],
    4: [2, 3, 7]
    }
 
    print(est_cyclique(graphe))

Correction ?

...CORRECTION...

# CONSTANTES ======================================================================
 
BLANC = 0
GRIS  = 1
NOIR  = 2
 
 
# FONCTIONS ======================================================================
 
def est_cyclique(g:'dict[int, list]') -> bool:
    """Prédicat qui renvoie True si le graphe possède un cycle (au moins un)"""
 
    # INITIALISATION
    parcours = {}              # Création du dictionnaire (qui sera un dict de dict)
    for u in g.keys():         # Pour chaque sommet du graphe
        parcours[u] = {}       # La clé u de parcours a comme valeur associée un dict 
        parcours[u]['couleur'] = BLANC    # Initialisation de la couleur
        parcours[u]['parent'] = None      # Initialisation du parent
 
    # PARCOURIR
    for u in g.keys():                              # Pour chaque sommet du graphe
        if parcours[u]['couleur'] == BLANC:         # S'il est encore Non découvert
            if visiter_profondeur(u, g, parcours):  # Si la visite de u détecte un cycle
                return True                         # on répond qu'on a un cycle
 
    return False       # si on arrive ici, c'est qu'il n'y a pas de cycle dans le graphe
 
def visiter_profondeur(u:int, g:'dict[int, list]', parcours:dict) -> bool:
    """Visite un sommet u en particulier et renvoie True si on détecte un cycle"""
 
    parcours[u]['couleur'] = GRIS               # Signale que u est découvert
 
    for v in g[u]:                              # Pour chaque sommet v de la liste d'adj de u
        if parcours[v]['couleur'] == GRIS and parcours[u]['parent'] != v:
            return True        
        elif parcours[v]['couleur'] == BLANC:       # Si v est non découvert
            parcours[v]['parent'] = u               # u est son parent
            if visiter_profondeur(v, g, parcours):  # si la visite de v détecte un cycle
                return True                         # on signale qu'on peut atteindre un cycle depuis u
 
    parcours[u]['couleur'] = NOIR               # u est totalement exploré
    return False   # si on arrive ici c'est qu'on a pas détecté de cycle depuis ce sommet
 
 
# PROGRAMME PRINCIPAL =========================================================
 
if __name__ == '__main__':
    graphe = {
    5: [9, 1],
    6: [2, 7, 8],
    7: [4, 6],
    8: [6, 9],
    9: [5, 8],
    1: [3, 2, 5],
    2: [3, 1, 4, 6],
    3: [1, 2, 4],
    4: [2, 3, 7]
    }
 
    print(est_cyclique(graphe))

Néanmoins, si le but est de simplement détecter la présence d'un cycle, on peut créer un code beaucoup plus ciblé.

Pour cela, nous allons réaliser les modifications suivantes :

plus de couleurs mais juste un tableau des sommets decouverts
pour savoir qui est le parent du sommet courant, on lui envoie simplement en argument.
on peut donc supprimer le dictionnaire parcours qui ne serait utile que si on voulait connaitre la topologie complète du graphe.

02° On utiilse maintenant les 3 points énoncés ci-dessus. Sans pouvoir le lancer réellement (puisqu'il manque l'autre fonction), compléter cette nouvelle version de la fonction est_cyclique() pour qu'elle soit opérationnelle.

def est_cyclique(g:dict[int, list]) -> bool:
    """Prédicat qui renvoie True si le graphe possède un cycle (au moins un)"""
 
    # INITIALISATION
    decouverts = ...            # Création du tableau des sommets decouverts
 
    # PARCOURIR
    for u in ...:                              # Pour chaque sommet du graphe
        if ...:         # S'il est encore Non découvert
            if visiter_profondeur(u, g, decouverts, None):   # Si la visite de u détecte un cycle
                return ...                         # on répond qu'on a un cycle
 
    return ...       # si on arrive ici, c'est qu'il n'y a pas de cycle dans le graphe

Correction ?

...CORRECTION...

def est_cyclique(g:dict[int, list]) -> bool:
    """Prédicat qui renvoie True si le graphe possède un cycle (au moins un)"""
 
    # INITIALISATION
    decouverts = []            # Création du tableau des sommets decouverts
 
    # PARCOURIR
    for u in g.keys():                              # Pour chaque sommet du graphe
        if not(u in decouverts)           :         # S'il est encore Non découvert
            if visiter_profondeur(u, g, decouverts, None):   # Si la visite de u détecte un cycle
                return True                         # on répond qu'on a un cycle
 
    return False       # si on arrive ici, c'est qu'il n'y a pas de cycle dans le graphe

03° Compléter maintenant la seconde fonction pour qu'elle puisse interagir correctement avec la première.

# FONCTIONS ======================================================================
 
def est_cyclique(g:dict[int, list]) -> bool:
    """Prédicat qui renvoie True si le graphe possède un cycle (au moins un)"""
 
    # INITIALISATION
    decouverts = []            # Création du tableau des sommets decouverts
 
    # PARCOURIR
    for u in g.keys():                              # Pour chaque sommet du graphe
        if not(u in decouverts)           :         # S'il est encore Non découvert
            if visiter_profondeur(u, g, decouverts, None):   # Si la visite de u détecte un cycle
                return True                         # on répond qu'on a un cycle
 
    return False       # si on arrive ici, c'est qu'il n'y a pas de cycle dans le graphe
 
def visiter_profondeur(u:int, g:dict[int, list], decouverts:list, parent:int|None) -> bool:
    """Visite un sommet u en particulier et renvoie True si on détecte un cycle"""
 
    ...                                 # Signale que u est découvert
 
    for v in ...:                              # Pour chaque sommet v de la liste d'adj de u
        if v in ... and ... != ...:
            return ...        
        elif not(...):               # Si v est non découvert
            if visiter_profondeur(..., ..., ..., ... ):  # si la visite de v détecte un cycle
                return True                      # on signale qu'on peut atteindre un cycle depuis u
 
    return False   # si on arrive ici c'est qu'on a pas détecté de cycle depuis ce sommet
 
 
# PROGRAMME PRINCIPAL =========================================================
 
if __name__ == '__main__':
    graphe = {
    5: [9, 1],
    6: [2, 7, 8],
    7: [4, 6],
    8: [6, 9],
    9: [5, 8],
    1: [3, 2, 5],
    2: [3, 1, 4, 6],
    3: [1, 2, 4],
    4: [2, 3, 7]
    }
 
    print(est_cyclique(graphe))

Correction ?

...CORRECTION...

# FONCTIONS ======================================================================
 
def est_cyclique(g:dict[int, list]) -> bool:
    """Prédicat qui renvoie True si le graphe possède un cycle (au moins un)"""
 
    # INITIALISATION
    decouverts = []            # Création du tableau des sommets decouverts
 
    # PARCOURIR
    for u in g.keys():                              # Pour chaque sommet du graphe
        if not(u in decouverts)           :         # S'il est encore Non découvert
            if visiter_profondeur(u, g, decouverts, None):   # Si la visite de u détecte un cycle
                return True                         # on répond qu'on a un cycle
 
    return False       # si on arrive ici, c'est qu'il n'y a pas de cycle dans le graphe
 
def visiter_profondeur(u:int, g:dict[int, list], decouverts:list, parent:int|None) -> bool:
    """Visite un sommet u en particulier et renvoie True si on détecte un cycle"""
 
    decouverts.append(u)                                 # Signale que u est découvert
 
    for v in g[u]:                              # Pour chaque sommet v de la liste d'adj de u
        if v in decouverts and parent != v:
            return True        
        elif not(v in decouverts):               # Si v est non découvert
            if visiter_profondeur(v, g, decouverts, u ):  # si la visite de v détecte un cycle
                return True                      # on signale qu'on peut atteindre un cycle depuis u
 
    return False   # si on arrive ici c'est qu'on a pas détecté de cycle depuis ce sommet
 
 
# PROGRAMME PRINCIPAL =========================================================
 
if __name__ == '__main__':
    graphe = {
    5: [9, 1],
    6: [2, 7, 8],
    7: [4, 6],
    8: [6, 9],
    9: [5, 8],
    1: [3, 2, 5],
    2: [3, 1, 4, 6],
    3: [1, 2, 4],
    4: [2, 3, 7]
    }
 
    print(est_cyclique(graphe))

04° Compléter le code ou les commentaires selon les lignes pour obtenir une version impérative opérationnelle.

# FONCTIONS ======================================================================
 
def est_cyclique(g:dict[int, list]) -> bool:
    """Prédicat qui renvoie True si le graphe possède un cycle"""
 
    # INITIALISATION
    d = ...                     # Tableau des sommets découverts
 
    # PARCOURIR
    for u in ...:               # Pour chaque sommet u du graphe
        # On remplace la pile d'appels par une vraie Pile
        pile = []                    # ...
        pile.append( (u, None) )     # ...
 
        # Equivalent impératif de visiter(u)
        while pile:                        # ...
            s, parent = ...        # On dépile le sommet suivant et son parent
            if ...:                # Si s est non découvert
                ...                # Signale que s est découvert
                for v in g[s]:             # ...
                    if ... and ...:
                        return ...
                    else:
                        ...  # On empile v et son parent s
    return ...
 
 
# PROGRAMME PRINCIPAL =========================================================
 
if __name__ == '__main__':
    graphe = {
    5: [1, 9],          # [9, 1] en récursif
    6: [8, 7, 2],       # [2, 7, 8] en récursif
    7: [6, 4],          # [4, 6] en récursif
    8: [9, 6],          # [6, 9] en récursif
    9: [8, 5],          # [5, 8] en récursif
    1: [3, 2, 5],       # [5, 2, 3] en récursif
    2: [6, 4, 1, 3],    # [3, 1, 4, 6] en récursif
    3: [4, 2, 1],       # [1, 2, 4] en récursif
    4: [2, 3, 7]        # [7, 3, 2] en récursif
    }
 
    print(est_cyclique(graphe))

Correction ?

...CORRECTION...

# FONCTIONS ======================================================================
 
def est_cyclique(g:dict[int, list]) -> bool:
    """Prédicat qui renvoie True si le graphe possède un cycle"""
 
    # INITIALISATION
    d = []                     # Tableau des sommets découverts
 
    # PARCOURIR
    for u in g.keys():               # Pour chaque sommet u du graphe
        # On remplace la pile d'appels par une vraie Pile
        pile = []                    # Création d'une Pile vide
        pile.append( (u, None) )     # On empile u et son parent (None)
 
        # Equivalent impératif de visiter(u)
        while pile:                        # Tant que la pile n'est pas vide
            s, parent = pile.pop()         # On dépile le sommet s suivant
            if not(s in d):                # Si s est non découvert
                d.append(s)                # Signale que s est découvert
                for v in g[s]:             # Pour chaque sommet v de la liste d'adj de s
                    if (v in d) and (parent != v):
                        return True
                    else:
                        pile.append( (v, s) )  # On empile v et son parent s
    return False
 
 
# PROGRAMME PRINCIPAL =========================================================
 
if __name__ == '__main__':
    graphe = {
    5: [1, 9],          # [9, 1] en récursif
    6: [8, 7, 2],       # [2, 7, 8] en récursif
    7: [6, 4],          # [4, 6] en récursif
    8: [9, 6],          # [6, 9] en récursif
    9: [8, 5],          # [5, 8] en récursif
    1: [3, 2, 5],       # [5, 2, 3] en récursif
    2: [6, 4, 1, 3],    # [3, 1, 4, 6] en récursif
    3: [4, 2, 1],       # [1, 2, 4] en récursif
    4: [2, 3, 7]        # [7, 3, 2] en récursif
    }
 
    print(est_cyclique(graphe))

1.2 Principe général de la détection dans un graphe ORIENTE

Le principe est encore plus simple : on a découvert un cycle si nous sommes en train de visiter un sommet u qui mène à un autre sommet v GRIS (c'est à dire déjà visité mais pas terminé)

Nous n'avons plus besoin de vérifier que v n'est pas le parent de u car le graphe est orienté : si le graphe possède un arc (u, v) et un arc (v, u), c'est bien un cycle.

Ainsi sur le graphe orienté ci-dessous, A-D-A représente bien un cycle contrairement au cas non orienté précédent : l'utilisation de l'arc (a, d) ne désactive pas l'arc (d, a).

La seule différence vient de la ligne 34 : nous n'avons plus qu'à tester si le sommet est GRIS, pas d'histoire de parent.

# CONSTANTES ======================================================================
 
BLANC = 0
GRIS  = 1
NOIR  = 2
 
 
# FONCTIONS ======================================================================
 
def est_cyclique(g:'dict[int, list]') -> bool:
    """Prédicat qui renvoie True si le graphe possède un cycle (au moins un)"""
 
    # INITIALISATION
    parcours = {}              # Création du dictionnaire (qui sera un dict de dict)
    for u in g.keys():         # Pour chaque sommet du graphe
        parcours[u] = {}       # La clé u de parcours a comme valeur associée un dict 
        parcours[u]['couleur'] = BLANC    # Initialisation de la couleur
        parcours[u]['parent'] = None      # Initialisation du parent
 
    # PARCOURIR
    for u in g.keys():                              # Pour chaque sommet du graphe
        if parcours[u]['couleur'] == BLANC:         # S'il est encore Non découvert
            if visiter_profondeur(u, g, parcours):  # Si la visite de u détecte un cycle
                return True                         # on répond qu'on a un cycle
 
    return False       # si on arrive ici, c'est qu'il n'y a pas de cycle dans le graphe
 
def visiter_profondeur(u:int, g:'dict[int, list]', parcours:dict) -> bool:
    """Visite un sommet u en particulier et renvoie True si on détecte un cycle"""
 
    parcours[u]['couleur'] = GRIS               # Signale que u est découvert
 
    for v in g[u]:                              # Pour chaque sommet v de la liste d'adj de u
        if parcours[v]['couleur'] == GRIS:
            return True        
        elif parcours[v]['couleur'] == BLANC:       # Si v est non découvert
            parcours[v]['parent'] = u               # u est son parent
            if visiter_profondeur(v, g, parcours):  # si la visite de v détecte un cycle
                return True                         # on signale qu'on peut atteindre un cycle depuis u
 
    parcours[u]['couleur'] = NOIR               # u est totalement exploré
    return False   # si on arrive ici c'est qu'on a pas détecté de cycle depuis ce sommet

2 - [Hors programme] Parcours complet en profondeur d'un graphe

⇩ ⇧ ⤊

En réalité, nous allons faire exactement comme dans l'activité précédente, nous allons simplement rajouter deux informations sur les sommets lors du parcours. Voici donc deux nouveaux attributs qu'il faudra rajouter aux sommets :

la date debut où le sommet a été découvert et visité la première fois (passage de BLANC à GRIS)
la date fin où le sommet a été entièrement traité (tous ses arcs ou arêtes ont été utilisés, passage de GRIS à NOIR)

Pour gérer les dates, nous allons simplement utiliser un nombre (stocké via une variable date) qu'on incrémentera de un à chaque fois :

qu'on commence l'exploration d'un sommet (passage de BLANC à GRIS) ou
qu'on finalise l'exploration d'un sommet (passage de GRIS à NOIR).

Comment gérer ce nombre ?

Nous pourrions utiliser une variable globale mais vous savez maintenant que cette possibilité est à éviter dans la mesure du possible.
Nous pourrions transmettre la référence d'une variable mutable créée pour l'occassion et ne contenant qu'un compteur qu'on incrémente à chaque étape (un tableau, un dictionnaire...)
Nous pourrions simplement rajouter un attribut date au graphe g. C'est sans doute le plus simple si c'est possible puisque g est déjà créé.

Voici alors l'algorithme complet réel d'un parcours en profondeur sur un graphe orienté :

Algorithme du parcours en profondeur (sur un graphe orienté)

Remarque : on peut l'utiliser également sur un graphe non orienté mais on ne gagnera en réalité pas d'informations supplémentaires par rapport à la version sans date de l'activité précédente.

ENTREES

Un graphe noté g

SORTIE

Aucune ici mais on peut facilement modifier l'algorithme pour qu'il renvoie par exemple l'Arbre ou la Forêt du parcours. En réalité ici, on stocke l'arbre directement via les sommets : on leur attribue un parent.

ALGORITHME PARCOURS EN PROFONDEUR

on initialise le compteur d'étapes du graphe

g.date ← 0

on initialise tous les sommets

POUR chaque sommet u appartenant au graphe g

u.couleur ← BLANC

u.parent ← VIDE

u.debut ← 0

u.fin ← 0

Fin Pour

on lance le traitement des sommets un par un

POUR chaque sommet u appartenant au graphe g

SI u.couleur est BLANC

si on arrive ici, c'est que le sommet n'a pas encore été découvert

visiter_en_profondeur(u, g)

Fin Si

Fin Pour

Renvoyer VIDE (∅)

ALGORITHME de visiter_en_profondeur(u, g)

g.date ← g.date + 1

u.debut ← g.date

u.couleur ← GRIS

POUR chaque sommet v de la liste d'adjacence du sommet u

SI v.couleur est BLANC

si on arrive ici, c'est que le sommet n'a pas encore été visité

v.parent ← u.

visiter_en_profondeur(v, g)

Fin Si

Fin Pour

ici, tous les sommets adjacents ont été tentés

g.date ← g.date + 1

u.fin ← g.date

u.couleur ← NOIR

Renvoyer VIDE (∅)

Avant d'utiliser les nouvelles informations que nous allons obtenir, voyons ce que nous obtenons sur un exemple de parcours : les informations debut et fin apparaissent à gauche et à droite du noeud dans l'Arbre de parcours obtenu (et au dessus du sommet dans la liste des sommets).

Animation du parcours — CLIQUER SUR L'IMAGE pour ANIMER ou STOPPER

3 - [Hors programme] Détection des cycles dans un graphe orienté avec le parcours complet

⇩ ⇧ ⤊

Voyons comment détecter les cycles à l'aide d'un parcours en profondeur.

Comme vous le voyez, on obtient donc maintenant beaucoup plus d'informations. Voici les mêmes informations représentées sous forme chronologique : les étapes vers la droite et l'ordre de découverte vers le bas.

Graphique montrant les dates de découverte des sommets — Les dates des sommets et l'ordre de découverte

Avec un peu de réflexion, on se rend compte que les dates suffisent : elles permettent de retrouver si besoin l'ordre de découverte (et cet ordre ne sert à rien en soi). Voici donc le graphique que nous allons utiliser pour raisonner :

Graphique montrant les dates des sommets — Les dates des sommets

On notera U l’intervalle du sommet u et V l’intervalle du sommet v.

Pour l'instant, notre exploration des graphes est très incomplète : on n'a sélectionné que certains arcs et nous en avons supprimé beaucoup : avec notre forêt, on pourrait croire que depuis les sommets S7 et S8 on ne peut pas joindre le reste du graphe.

Arcs de liaison : on descend d'un niveau exactement

Les arcs en noir sont nommés les arcs de liaison : ce sont les arcs qu'on a utilisé pendant le parcours en profondeur : on est entré la première fois dans ce sommet par ce arc.

Ces arcs sont ceux qui caractérisent l'Arbre de parcours obtenu. Un Arc de liaison fait donc descendre exactement d'un niveau dans l'Arbre de parcours : il relie un sommet parent à son enfant direct.

Exemples : (S6, S3), (S1,S4), (S2,S5)...

Comment le programmme peut-il les détecter ?

Un arc (u,v) est un arc de liaison si u est le parent du sommet v dans l'Arbre de parcours. Seul le lien de parenté importe.

05° Pourquoi l’arc (S8,S7) n’est-il pas un arc de liaison sur ce parcours ?

Correction ?

...CORRECTION...

S8 n'est pas le père de S7 sur l'Arbre de parcours : on découvre S8 en venant de S7 et pas l'inverse.

05-b° Que deviendrait l’arc (S8,S7) dans le cas où on commencerait l’exploration par S8 par exemple ?

Correction ?

...CORRECTION...

Puisque la liste d'adjacence de S8 est [S6,S7], on commencerait l'exploration en partant d'abord vers S6. On lance donc l'exploration de toute la partie de gauche. Mais on ne pourrait pas découvrir S8 depuis S6.

Après avoir passé S6 en NOIR, on reviendrait donc en S8 pour tester l'arc (S8, S7) : S7 étant encore BLANC dans ce cas, cet arc deviendrait un arc de liaison.

05-c° La dénomination des arcs est-elle dépendante ou indépendante du choix de l’ordre des sommets dans un graphe quelconque ?

Correction ?

...CORRECTION...

La classification des arcs dépend des sommets qu'on explore en premier. Un arc peut changer de classification si on change l'ordre des découvertes : la forêt obtenue change.

Nous allons donc maintenant voir comment savoir si l'un des arcs grisés provoque un cycle ou pas. De cette façon, nous pourrons garder certains arcs en gris : ceux qui ne provoqueront pas de cycle en venant de S6.

Arc S4 vers S2

Cet Arc là ne doit pas être visité en venant de S6 : il provoque un retour en arrière car S2 est un ancêtre de S4.

Arcs arrière : on remonte d'un ou plusieurs niveaux

Les arcs arrière sont les arcs qui relient un sommet à l'un de ces ancêtres dans l'Arbre de profondeur. Ils permettent de revenir en arrière dans le parcours et de créer un cycle.

Ainsi venant de S6, on voit qu'emprunter (S4,S2) crée un cycle puisqu'on repasse nécessairement par le sommet S2 que nous avons forcément déjà traversé en venant de S6.

Comment le programme peut-il les détecter ?

Un arc (u,v) est un arc arrière si l'intervalle du sommet u de départ est inclus dans l'intervalle du sommet v de destination. On remonte donc vers un ancêtre.

U ⊂ V

Exemple : (S4, S2).

06-a° Que peut-on dire de l'intervalle [5;6] du sommet de départ S4 par rapport à celui [3;10] du sommet de destination S2 ?

[5; 6] ⊂ [3;10]
[3;10] ⊂ [5; 6]
[5; 6] ∈ [3;10]
[3;10] ∈ [5; 6]

Correction ?

...CORRECTION...

[5; 6] ⊂ [3;10] : oui, l'intervalle [5;6] est inclus dans [3;10]
[3;10] ⊂ [5; 6] : faux
[5; 6] ∈ [3;10] : faux, appartient est utilisé pour désigner un élément appartenant à un ensemble et pas un ensemble par rapport à un autre ensemble.
[3;10] ∈ [5; 6] : faux

06-b° Existe-il d'autres arcs arrière sur ce parcours en profondeur ?

Correction ?

...CORRECTION...

Trouver les chemins disponibles via la détection des cycles dans un graphe orienté AVEC les dates

Si on cherche naïvement les chemins disponibles dans un graphe, l'utilisation d'un cycle engendre en machine une infinité de solutions : on tourne une fois, on tourne deux fois...

Comment éviter les cycles ?

un graphe possèdant un arc arrière contient au moins un cycle.
un graphe ne possèdant pas d'arc arrière ne contient pas de cycle.

Eviter les cycles revient donc à supprimer les arcs arrière lors du déplacement dans le graphe.

07° Dessiner le graphe simplifié où les arcs arrière sont supprimés mais tous les autres sont utilisables.

Correction ?

...CORRECTION...

08° Ecrire les 4 chemins partant de S6 en menant à un "cul de sac" : vous n'avez bien entendu pas le droit d'utiliser un arc arrière. Vous pouvez par contre utiliser les arcs grisés.

1er chemin : S6 - S3 - S2 - S1 - S4

...

Correction ?

...CORRECTION...

S6 - S3 - S2 - S1 - S4
S6 - S3 - S2 - S5 - S4
S6 - S3 - S5 - S4
S6 - S5 - S4

09° Utiliser le graphe simplifié pour fournir tous les chemins explorables dans ce graphe partant de S7 sans réaliser de cycle. Pensez à utiliser la réponse à la question 07...

Correction ?

...CORRECTION...

Il suffit d'explorer le graphe en partant de S7 et en se dirigeant vers le bas à chaque fois.

Deux manières de rejoindre "l'étape S6" : S7 vers S6 ou S7 vers S8 vers S6.

On obtient donc le double de possibilités par rapport à la question 07.

S7-S6-S3-S2-S1-S4
S7-S6-S3-S2-S5-S4
S7-S6-S3-S5-S4
S7-S6-S5-S4
S7-S8-S6-S3-S2-S1-S4
S7-S8-S6-S3-S2-S5-S4
S7-S8-S6-S3-S5-S4
S7-S8-S6-S5-S4

10° Imaginons que chacun des sommets représente les pièces d'un jeu où on peut perdre ou gagner des pièces d'or.

S7 : +50 po
S8 : + 10 po
S6 : - 20 po
S3 : + 50 po
S2 : - 10 po
S5 : + 20 po
S1 : + 40 po
S4 : - 20 po

Par quel chemin passer ?

Correction ?

...CORRECTION...

Il suffit d'explorer le graphe en partant de S7 et en se dirigeant vers le bas à chaque fois.

On voit immédiatement que le chemin passant par S8 ne peut qu'être positif par rapport au chemin se dirigeant directement vers S6.

S7-S8-S6-S3-S2-S1-S4 : 100 po
S7-S8-S6-S3-S2-S5-S4 : 80 po
S7-S8-S6-S3-S5-S4 : 90 po
S7-S8-S6-S5-S4 : 40 po

Le premier chemin est donc préférable ici.

Trouver les chemins disponibles via la détection des cycles dans un graphe orienté SANS les dates

On peut trouver la nature des arcs au fur et à mesure de l’exploration, sans les dates :

Lors de l'exploration, si :

on teste un arc menant à un sommet BLANC, il s'agit d'un arc de liaison : on le mémorise.
on teste un arc menant à un sommet GRIS, il s'agit d'un arc arrière : on ne le mémorise pas (ou on mémorise qu'on ne doit pas l'emprunter).
on teste un arc menant à un sommet NOIR, il s'agit d'autres types d'arcs. On peut juste dire qu'il ne s'agit ni d'un arc arrière, ni d'un arc de liaison.

Mais il faudra mémoriser sa nature dans une nouvelle structure de données gérant les arcs.

Dans ce cours, j'ai préféré utiliser les dates mais on pourrait modifier les listes d'adjacence pour y intégrer une information supplémentaire sur la nature de l'arc. On la place à 'ok' initialement et on change à 'arrière' si on détecte un arc arrière.

Exemple avec le sommet S2 :

Plutôt que de stocker [1,5] dans la liste d'adjacence de S2,
on pourrait ainsi stocker [(1,'ok'), (5, 'ok')]
qui deviendrait [(1,'ok'), (5, 'ok')] à la fin du parcours en profondeur.

De la même façon, celle de S4 passerait de [(2, 'ok')] à [(2, 'arrière')].

11° Utiliser l'animation du parcours en profondeur sur ce graphe orienté. A quel moment détecte-t-on le premier arc arrière uniquement graçe à la couleur du sommet de destination ? Ce graphe contient-il des cycles ?

Correction ?

...CORRECTION...

On détecte le premier arc arrière au moment du test de l'arc (S4,S2) : il mène au sommet S2 déjà GRIS.

Puisqu'on vient de détecter un arc arrière, ce graphe contient au moins un cycle.

Conclusion

Pour visiter tous les chemins disponibles à partir d’une « racine » sans risque de tourner en rond, il suffit d’éviter les arcs arrière en les détectant :

soit avec les dates stockées dans les sommets
soit avec la couleur du sommet-destination des arcs lors du parcours initial en profondeur

4 - [Hors programme] Affiner la connaissance des chemins avec les dates

⇩ ⇧ ⤊

Qu'apportent les dates alors ?

La datation permet de distinguer deux autres types d'arcs, ceux qui ne sont ni des arcs de liaison, ni des arcs arrière. Nous allons voir :

les arcs avant : les arcs permettant de descendre plus rapidement dans l'Arbre de parcours obtenu. Une sorte de raccourci.
les arcs transverse : les arcs qui relient des sommets dont aucun des deux n'est l'ancêtre de l'autre.

L'utilisation des dates permet donc d'apporter des informations supplémentaires sur la structure de la Forêt de parcours obtenue.

Regardons maintenant comment caractériser les autres arcs, ceux qui ne sont ni des arcs de liaison, ni des arcs arrière.

Arcs avant : on descend de plus d'un niveau

Les arcs avant sont les arcs (u,v) reliant un sommet-départ u à l'un de ses descendants v dans l'arbre, sans que v ne soit le fils de u.

Exemple d'un arc avant Arc avant du point du vue des intervalles

L'arc (S6, S3) est juste un arc de liaison car S6 est le parent direct de S3.

L'arc (S6, S5) est un arc avant puisqu'il permet de joindre S5 plus rapidement qu'en passant par S3.

Comment le programme peut-il les détecter ?

Un arc (u,v) est un arc avant si

l'intervalle du sommet-destination v est inclus dans l'intervalle du sommet-départ u.
u n'est pas le parent de v (ça c'est un arc de liaisons)

V ⊂ U
u ≠ v.parent

Ici l'intervalle [8;9] de S5 est bien inclus dans l'intervalle [1;12] de S6 sans que S6 ne soit le parent de S5.

12° Trouver les autres arcs avant présents dans le parcours en profondeur proposé :

Correction ?

...CORRECTION...

Le seul autre arc avant est l'arc (S3,S5).

L'intervalle [8;9] de S5 est bien inclus dans l'intervalle [2;11] de S3 sans que S3 ne soit le parent direct de S5.

Arcs transverse : les liaisons entre sommets sans relation d'ancêtre-descendance

On y trouve donc les derniers arcs.

L'arc (S5,S4) est un exemple d'arc transerve entre sommet d'un même Arbre de parcours.

L'arc (S7,S6) est un exemple d'arc transerve entre sommet de deux Arbres différent de la Forêt de parcours.

Comment le programme peut-il les détecter ?

Un arc (u,v) est un arc transverse si les intervalles des sommets u et v sont disjoints, c'est à dire qu'ils n'ont pas de dates communes.

U ∩ V = ∅

[8;9] de S5 est bien disjoint avec [5;6] de S4.

[13;16] de S7 est bien disjoint avec [1;12] de S6.

Trouver un chemin dans un graphe

A partir de cette recherche, basée sur un départ supposé de S6, nous sommes capables d'obtenir les chemins sans cycle reliant les différents sommets.

Il suffit pour cela de simplifier le graphe en interdisant l'utilisation des arcs arrière mais en autorisant tous les autres.

Vous pouvez voir, à gauche, le graphe simplifié après suppression des arcs arrière.

A droite, une autre représentation du même graphe en utilisant le squelette de la forêt de parcours initial. Attention, le rajout des arcs avant et transverse sur la Forêt de parcours la transforme en graphe puisque certains noeuds de l'arbre peuvent mainteant avoir plusieurs parents : S4 ou S6 par exemple. Ce ne sont donc plus des noeuds d'Arbre mais des sommets de Graphe.

L'association des informations trouvées lors du parcours nous permet néanmoins d'affirmer que, sur ce parours, le sommet S7 est un peu particulier puisqu'il est le seul sommet n'ayant pas de prédecesseur : la forme de droite correspond à ce qu'on peut nommer un tri topologique : on trace l'ordre dans lequel on doit nécessairement visiter les sommets pour partir du sommet et atteindre le fond. Remplacer les sommets par les étapes de résolution d'un problème (construire un immeuble ?) et vous aurez compris qu'on aurait ici plusieurs manières de résoudre le problème (on voit que lors de la construction, certaines étapes que nous avions iniitialement prévues ne sont pas forcément utiles puisqu'on peut les contourner et aboutir à la même situation finale !).

Il faut néanmoins bien comprendre que les deux formes sont similaires et représentent bien le même parcours dans ce graphe simplifié.

Résumé sur les arcs et le parcours en profondeur d'un graphe orienté

On notera U l’intervalle du sommet u et V l’intervalle du sommet v.

Type d'arc	Détection avec dates	Détection sans date
Arc de liaison (u,v)	u est le parent de v. u = v.parent	L'arc mène vers un sommet BLANC
Arc arrière (u,v)	L'intervalle de u est inclus dans celui de v U ⊂ V	L'arc mène vers un sommet GRIS
Arc avant (u,v)	u n'est pas le parent de v ET l'intervalle de v est inclus dans celui de u V ⊂ U u ≠ v.parent	L'arc mène vers un sommet NOIR (mais c'est le cas d'un arc transverse aussi)
Arc transverse (u,v)	Les intervalles de v et u sont disjointsbr> U ∩ V = ∅	L'arc mène vers un sommet NOIR (mais c'est le cas d'un arc avant aussi)

5 - [Hors programme] Détection des cycles dans un graphe non orienté avec ce parcours

⇩ ⇧ ⤊

Sur un graphe non orienté, difficile de séparer une arête arrière d'une arête avant puisqu'on peut suivre l'arête dans le deux sens. Or, soit on autorise l'accès à une arête (dans les deux sens), spot on n'en autorise pas l'accès (dans les deux sens).

Un graphe non orienté ne possède que des arêtes DE LIAISON et des arềtes ARRIERE.

Le choix de la classification d'une arête se fait simplement lors de sa première utilisation.

13° Utiliser l'animation du parcours en profondeur sur ce graphe non orienté. Tracer les intervalles. Trouver les arcs arrière. En déduire s'il existe des cycles dans ce graphe non orienté.

Correction ?

...CORRECTION...

14° Tracer les intervalles obtenus sur ce parcours. Trouver les arcs arrière. En déduire s'il existe des cycles dans ce graphe non orienté.

Correction ?

...CORRECTION...

Détection des cycles dans un graphe non orienté

Un parcours sur un graphe non orienté ne possède que

des arêtes de liaison ou
des arêtes arrière.

Dans un graphe non orienté, l'arête va être empruntée dans les deux sens pendant le parcours (contrairement à un arc qui n'est emprunté que dans un seul sens). On considère que l'arête est du type correspondant au premier type rencontré :

Lors de la première utilisation de l'arête dans le parcours, l'arête mène à un sommet BLANC : c'est une "arête de liaison".
Lors de la première utilisation de l'arête dans le parcours, l'arête mène à un sommet GRIS : c'est une "arête arrière" et on vient de détecter un cycle.

Comme il va falloir ne tenir compte que du premier passage, il faudra mémoriser le passage. Donc, autant utiliser l'algorithme en profondeur avec datation.

Par contre, si vous utilisez l'algorithme dans votre tête, la couleur de la première utilisation en utilisant votre cerveau pour mémoriser suffit.

15° Utiliser l'animation du parcours en profondeur sur ce graphe non orienté. En tant qu'humain, à quel moment détecte-t-on la première arête arrière ? Ce graphe contient-il des cycles ?

Correction ?

...CORRECTION...

Voici le moment où on détecte la première fois la présence d'une arête arrière et donc la présence de cycle : on emprunte l'arête reliant S2 et S3 pour la première fois et on obtient un sommet destination GRIS.

Attention : ce n'est PAS cette étape : nous avons déjà emprunté l'arête dans le sens (S1,S2) et l'arête a alors été déclarée de liaison. Le deuxième passage dans le sens (S2,S1) mène à un sommet GRIS mais cela ne change rien : le type "liaison" a déjà été attribué.

Résumé sur les arcs et le parcours en profondeur d'un graphe non orienté

Type d'arc	Détection avec dates	Détection sans date (1er utilisation de l'arête)
Arête de liaison {u,v}	u est le parent de v. u = v.parent	L'arête mène vers un sommet BLANC
Arête arrière {u,v}	L'intervalle de u est inclus dans celui de v U ⊂ V	L'arc mène vers un sommet GRIS

Finissons avec un complément totalement optionnel pour voir qu'on utilise bien les arêtes dans les deux sens. Si vous avez le temps.

On peut bien entendu se passer des dates mêmes avec un ordinateur mais il faudra trouver un moyen de mémoriser les passages d'une façon ou d'une autre pour ne tenir compte que du premier.

Ou alors, il faudra veuiller à parvenir à caractériser l'arête correctement la deuxième fois également :

La détection des cycles devient : lors de l'exploration, si

l'arête mène à un sommet BLANC : c'est une "arête de liaison" rencontrée pour la première fois.
l'arête mène à un sommet GRIS mais qui est le parent du sommet de départ : c'est une "arête de liaison" rencontrée dans l'autre sens.
l'arête mène à un sommet GRIS sans que la destination ne soit le parent du sommet de départ : c'est une "arête arrière" rencontrée pour la première fois.
l'arête mène à un sommet NOIR : c'est une "arête arrière" rencontré pour la deuxième fois.

Type d'arc	Détection sans date (1er utilisation de l'arête)	Détection sans date (2e utilisation de l'arête)
Arête de liaison {u,v}	L'arête mène vers un sommet BLANC	L'arête mène vers un sommet GRIS qui se trouve être le parent de u
Arête arrière {u,v}	L'arc mène vers un sommet GRIS qui n'est pas le parent de u	L'arc mène vers un sommet NOIR

Comme vous le voyez, autant utiliser les dates ou un autre système qui ne catégorise l'arête que la première fois qu'on la rencontre.

16° Que peut-on dire de l'arête (S1,S3) lors de sa première utilisations ? lors de sa deuxième utilisation ?

Correction ?

...CORRECTION...

Première utilisation : S1 n'est pas le parent de S3. Or la destination est GRIS : il s'agit donc d'une arête arrière.

Deuxième utilisation : la destination est NOIR : il s'agit donc toujours d'une arête arrière.

17° Que peut-on dire de l'arête (S2,S3) lors de sa première utilisations ? lors de sa deuxième utilisation ?

Correction ?

...CORRECTION...

Première utilisation : la destination est BLANC : il s'agit donc d'une arête de liaison.

Deuxième utilisation : la destination S2 est GRIS mais S2 est le parent de S3 : il s'agit donc toujours d'une arête arrière.

6 - FAQ

⇩ ⇧ ⤊

Arcs arrière ou arrières

On écrit arcs arrière sans accord car ils font opposition aux arcs avant.

De la même façon, on note arcs tranverse et pas arcs transverses.

Avant, arrière et transverse font référence à une direction et ne sont pas des adjectifs ici.

Activité publiée le 09 05 2021
Dernière modification : 09 05 2021
Auteur : ows. h.

⏪

⏫

⏩