duranton.net

Chapitre 19 : Les graphes orientés.

Introduction :

Un graphe orienté est une structure composée de sommets reliés par des arcs ayant un sens.

Les graphes orientés sont utilisés pour modéliser des situations où le sens des relations est important, comme les liens entre pages web, les dépendances ou les chemins à sens unique.

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:

A 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 de Emma?
  3. Quel est le degré sortant de Emma?
  4. Quel est le dégré de Laura?
  5. Citer un cycle initalisé 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:

  

    

    

      >>>