duranton.net
Connexion

Chapitre 19 : Les graphes orientés.

Introduction :

Sur le web, une page renvoie vers une autre… mais l'inverse n'est pas toujours vrai. Une rue peut être à sens unique, une tâche peut devoir être terminée avant qu'une autre commence.

Comment représenter des relations qui ont un sens, une direction ? Et qu'est-ce que cela change lorsqu'on cherche un chemin d'un point à un autre ?

1. Degrés et adjacence dans un graphe orienté

Un graphe orienté est un ensemble de sommets reliés entre eux par des arcs ayant un sens (une direction).

Dans un tel graphe :

Exemple :

Dans cet exemple :

Deux sommets sont adjacents s’il existe un arc qui relie l’un à l’autre.

Dans un graphe orienté, on distingue :

Si rien n'est précisé, on considérera que l'adjacence est sortante.

2. Exercice : adjacence, degré et cycles dans un graphe orienté.

À faire dans le cahier.

On considérera ici que les adjacences sont sortantes.

Dans le graphe ci-dessous :

  1. Citer les sommets adjacents à Emma.
  2. Quel est le degré entrant d'Emma ?
  3. Quel est le degré sortant d'Emma ?
  4. Quel est le degré de Laura ?
  5. Citer un cycle initialisé en Fiona.
  6. Justifier qu'aucun cycle n'est initialisé en David.

3. Exercice : Graphe orienté (arcs, successeurs, prédécesseurs)

On travaille avec un graphe orienté : une relation A -> B signifie qu'il existe un arc allant de A vers B.

On représente le graphe avec un dictionnaire self.arcs où :

  • chaque clé est un sommet (string),
  • chaque valeur est la liste des successeurs (sommets atteints par un arc sortant).

Compléter les méthodes demandées en respectant strictement les documentations.

Exemple de graphe orienté utilisé dans l'exercice :

class GrapheOriente: def __init__(self) -> None: """ Initialise un graphe orienté. Représentation : - self.arcs est un dictionnaire : * clé : sommet (str) * valeur: liste des successeurs (list[str]) Exemple : - si A -> B et A -> C, alors self.arcs["A"] peut valoir ["B", "C"]. """ self.arcs = {} def ajouter_sommet(self, sommet: str) -> None: """ Ajoute un sommet au graphe s il n existe pas déjà. """ if sommet not in self.arcs: self.arcs[...] = ... def ajouter_arc(self, source: str, destination: str) -> None: """ Ajoute un arc source -> destination. Remarques : - Si un sommet n existe pas, il est créé automatiquement. - On accepte les doublons si l appel est répété (ce n est pas bloquant pour cet exercice). """ self.ajouter_sommet(...) self.ajouter_sommet(...) ... def successeurs(self, sommet: str) -> list: """ Retourne la liste des successeurs de sommet (arcs sortants). Contraintes : - Si le sommet n existe pas, renvoyer une liste vide. - Le résultat doit être une liste (ordre quelconque). """ ... def predecesseurs(self, sommet: str) -> list: """ Retourne la liste des prédécesseurs de sommet (arcs entrants). Exemple : - si A -> C et B -> C, alors predecesseurs("C") doit contenir ["A", "B"] (ordre quelconque). Contraintes : - Si le sommet n existe pas, renvoyer une liste vide. - Ne pas mettre de doublons dans la liste retournée. """ ... def est_arc(self, source: str, destination: str) -> bool: """ Renvoie True si l arc source -> destination existe, False sinon. Contraintes : - Si source n existe pas, renvoyer False. """ ... def degre_sortant(self, sommet: str) -> int: """ Retourne le degré sortant de sommet (nombre d arcs sortants). Contraintes : - Si le sommet n existe pas, renvoyer 0. """ ... def degre_entrant(self, sommet: str) -> int: """ Retourne le degré entrant de sommet (nombre d arcs entrants). Idée : - Parcourir tous les sommets u du graphe et compter combien de fois sommet apparaît dans self.arcs[u]. Contraintes : - Si le sommet n existe pas, renvoyer 0. """ ... # Graphe d exemple arcs_exemple = [ ("A", "B"), ("A", "C"), ("B", "D"), ("C", "D"), ("D", "E"), ("C", "A") ] g = GrapheOriente() for (u, v) in arcs_exemple: g.ajouter_arc(u, v) # Visualisation print("Arcs :", g.arcs) print("Successeurs de A :", sorted(g.successeurs("A"))) print("Predecesseurs de D :", sorted(g.predecesseurs("D"))) print("Arc A->C :", g.est_arc("A", "C")) print("Arc B->A :", g.est_arc("B", "A")) print("Degre sortant de C :", g.degre_sortant("C")) print("Degre entrant de A :", g.degre_entrant("A"))

Tests :

Affichage :

Console :


    

      >>>
      
    

  














  
4. Exercice : Détecter un cycle dans un grand graphe orienté


  

    
On modélise un système de dépendances entre des tâches (graphe orienté).

    
Un arc A -> B signifie : pour exécuter B, il faut avoir terminé A avant.

    
Si le graphe contient un cycle, alors certaines tâches sont impossibles à ordonner : on tourne en rond.


    

        
    


    
Comment détecter un cycle (explication) :

    
    
      
  • On explore le graphe avec un parcours en profondeur.
    • 
      
  • On donne à chaque sommet un état :
    • 
      
      
        
    • "jamais_visite"
      • 
        
    • "en_cours_d_exploration"
      • 
        
    • "termine"
      • 
      
    
      
  • Si pendant l'exploration on suit un arc u -> v avec v déjà "en_cours_d_exploration", alors on a détecté un cycle.
    • 
    


    
On doit lancer un parcours en profondeur sur tous les sommets qui restent en état "jamais_visite" :

    
    
      
  • Un graphe peut être non connexe : il peut y avoir plusieurs groupes de sommets séparés.
    • 
      
  • Donc on ne lance pas un seul DFS : on doit lancer un DFS depuis chaque sommet encore "jamais_visite".
    • 
      
  • Pour un résultat déterministe, on parcourra les sommets de départ dans l'ordre alphabétique avec sorted.
    • 
    


    
Compléter la méthode contient_cycle(self) -> bool.


    
Exemples :

    
# g_grand_cycle contient un cycle -> True
# g_grand_sans  ne contient pas de cycle -> False

  


  
  
class GrapheOriente:
    def __init__(self) -> None:
        """
        Graphe orienté représenté par un dictionnaire d adjacence.

        Représentation :
        - self.arcs : dict[str, list[str]]
          * chaque clé est un sommet
          * chaque valeur est la liste des successeurs (arcs sortants)
        """
        self.arcs: dict = {}

    def ajouter_sommet(self, sommet: str) -> None:
        """
        Ajoute un sommet au graphe s il n existe pas déjà.
        """
        if sommet not in self.arcs:
            self.arcs[sommet] = []

    def ajouter_arc(self, source: str, destination: str) -> None:
        """
        Ajoute un arc orienté source -> destination.
        """
        self.ajouter_sommet(source)
        self.ajouter_sommet(destination)
        self.arcs[source].append(destination)

    def explorer_et_detecter_cycle(self, sommet: str, etat: dict) -> bool:
        """
        Explore le graphe en profondeur (DFS) a partir de 'sommet' pour detecter un cycle.
    
        Parametres :
        - sommet : str, sommet de depart pour cette exploration
        - etat : dict[str, str], etat de chaque sommet parmi :
            * "jamais_visite"
            * "en_cours_d_exploration"
            * "termine"
    
        Principe :
        - On marque le sommet courant en "en_cours_d_exploration".
        - Pour chaque successeur v de sommet :
            * si v est "en_cours_d_exploration", on a trouve un cycle (retour True)
            * si v est "jamais_visite", on continue l exploration depuis v
        - Quand tous les successeurs sont traites, on marque sommet en "termine".
    
        Retour :
        - True si un cycle est detecte pendant cette exploration
        - False sinon
        """
        etat[sommet] = "en_cours_d_exploration"
    
        for voisin in sorted(self.arcs[sommet]):
            if etat[voisin] == "en_cours_d_exploration":
                ...
            if etat[voisin] == "jamais_visite":
                if self.explorer_et_detecter_cycle(voisin, etat):
                    ...
    
        etat[sommet] = "termine"
        return ...


    def contient_cycle(self) -> bool:
        """
        Renvoie True si le graphe orienté contient au moins un cycle, False sinon.
    
        IMPORTANT (sommets de depart) :
        - On initialise avec un dictionnaire etat où les clés sont les sommets du graphe associés au string jamais_visite.
        - on lance une exploration DFS depuis chaque sommet qui est encore "jamais_visite".
        """
        etat = {}

        for s in self.arcs:
            etat[s] = ...
        
    
        for sommet in sorted(self.arcs.keys()):
            ...
                ...
                    ...
    
        return ...


# ----------------------------------------------------
# Grand graphe d exemple : version AVEC cycle
# ----------------------------------------------------
aretes_grand_cycle = [
    ("A", "B"), ("A", "C"), 
    ("A", "D"),
    ("B", "E"), ("B", "F"),
    ("C", "F"), ("C", "G"),
    ("D", "G"), ("D", "H"),
    ("E", "I"), ("E", "J"),
    ("F", "J"), ("F", "K"),
    ("G", "K"), ("G", "L"),
    ("H", "M"),
    ("I", "N"), ("J", "N"),
    ("J", "O"), ("K", "O"),
    ("L", "P"), ("M", "P"),
    ("N", "Q"), ("O", "Q"),
    ("O", "R"), ("P", "R"),
    ("Q", "S"), ("R", "S"),
    ("S", "T"),
    # liens supplementaires (toujours sans cycle ici)
    ("C", "E"), ("D", "F"), ("H", "J"), ("M", "O"),

    # --- cycle : H -> J -> L -> H ---
    ("H", "J"), ("J", "L"), ("L", "H")
]

g_grand_cycle = GrapheOriente()
for (u, v) in aretes_grand_cycle:
    g_grand_cycle.ajouter_arc(u, v)


# ----------------------------------------------------
# Grand graphe d exemple : version SANS cycle
# (on retire l arc L -> H)
# ----------------------------------------------------
aretes_grand_sans = [
    (u, v) for (u, v) in aretes_grand_cycle if not (u == "L" and v == "H")
]

g_grand_sans = GrapheOriente()
for (u, v) in aretes_grand_sans:
    g_grand_sans.ajouter_arc(u, v)


# Prints de visualisation
print("Nombre de sommets (avec cycle) :", len(g_grand_cycle.arcs))
print("Nombre d arcs (avec cycle)     :", sum(len(g_grand_cycle.arcs[s]) for s in g_grand_cycle.arcs))
print("Cycle ? (avec cycle)           :", g_grand_cycle.contient_cycle())
print()
print("Nombre de sommets (sans cycle) :", len(g_grand_sans.arcs))
print("Nombre d arcs (sans cycle)     :", sum(len(g_grand_sans.arcs[s]) for s in g_grand_sans.arcs))
print("Cycle ? (sans cycle)           :", g_grand_sans.contient_cycle())



  
  

  
Tests :

  


  
Affichage :

  


  
Console :

  

    

    

      >>>