Aller au contenu principal
Physique, Chimie et Informatique > Terminales Spé. NSI

Les graphes

Au programme de la partie « Structures de données »

Contenus Capacités attendues Commentaires
Graphes : structures relationnelles. Sommets, arcs, arêtes, graphes orientés ou non orientés. - Modéliser des situations sous forme de graphes.
- Écrire les implémentations correspondantes d’un graphe : matrice d’adjacence, liste de successeurs/de prédécesseurs.
- Passer d’une représentation à une autre.
On s’appuie sur des exemples comme le réseau routier, le réseau électrique, internet, les réseaux sociaux.
- Le choix de la représentation dépend du traitement qu’on veut mettre en place : on fait le lien avec la rubrique « algorithmique ».

Au programme de la partie « Algorithmique »

Contenus Capacités attendues Commentaires
Algorithmes sur les graphes. - Parcourir un graphe en profondeur d’abord, en largeur d’abord.
- Repérer la présence d’un cycle dans un graphe.
- Chercher un chemin dans un graphe.
- Le parcours d’un labyrinthe et le routage dans internet sont des exemples d’algorithme sur les graphes.
- L’exemple des graphes permet d’illustrer l’utilisation des classes en programmation.

Documents

Sous-sections de Les graphes

Physique, Chimie et Informatique > Terminales Spé. NSI > Les graphes

Représentation d'un graphe en informatique

Plusieurs modes de représentation peuvent être implémentés pour stocker des graphes : matrices d’adjacence (ou sommet-sommet), listes des voisins, des successeurs ou des prédécesseurs. Lors de cette séance nous allons écrire les classes réalisant ces implémentations.

Structure de graphe basée sur une liste d’adjacence

  1. Écrire le code de la méthode __init__ de la classe Sommet dont la spécification est :

    def __init__(self: Sommet, val: str) -> None:
        """
        Initialisation d'un sommet.
        """

    Remarque : La classe Sommet possède deux attributs :

    • val représente la valeur du sommet ou son étiquette. Cet attribut est de type chaîne de caractères (str) ;
    • adj représente la liste des sommets adjacents au sommet, instance de la classe. Cet attribut référence une liste de sommets ; lors de l’initialisation d’un sommet il doit référencer une liste vide.
Réponse
class Sommet:
"""
Représentation d'un sommet.
"""

def __init__(self: Sommet, val: str) -> None:
    """
    Initialisation du sommet.
    """
    self.val = val
    self.adj = []  # Sommets adjacents
  1. Ajouter au code de la classe Sommet la re-définition de la méthode __repr__ donnée ci-dessous :

    def __repr__(self: Sommet) -> str:
        rep = str(self.val) + " : ["
        for i, sommet in enumerate(self.adj):
            rep += str(sommet.val)
            if i < len(self.adj) - 1:
                rep += ", "
        rep += "]"
        return rep

    Cette méthode permet de représenter un sommet sous la forme d’une chaîne de caractères.

  2. Tester la définition de la classe Sommet en ajoutant les lignes de code suivantes au fichier :

    if __name__ == "__main__":
        s1 = Sommet("a")
        s2 = Sommet("b")
        s3 = Sommet("c")
        s1.adj.append(s2)
        s1.adj.append(s3)
        print(s1)
        print(s2)
  3. Écrire le code de la méthode __init__ de la classe Graphe dont la spécification est :

    def __init__(self: Graphe, valeurs: str = "") -> None:
        """
        La liste des sommets peut être passée dans une
        chaîne de caractères. Chaque sommet doit alors être
        séparé du précédent par une virgule.
    
        Hypothèse : chaque sommet n'est présent qu'une seule
        fois dans valeurs.
        """

    Remarque : La classe Sommet possède un seul attribut, sommets. Ce dernier référence une liste d’objets de type Sommet. Cette liste est initialement :

    • Soit vide,

    • Soit constituée des sommets passés en argument lors de l’initialisation d’un objet de type Graphe.

Réponse
class Graphe:
    """
    Représentation du graphe.
    """

    def __init__(self: Graphe, valeurs: str = "") -> None:
        """
        La liste des sommets peut être passée dans une
        chaîne de caractères. Chaque sommet doit être
        séparé du précédent par une virgule.

        Hypothèse : chaque sommet n'est présent qu'une seule
        fois dans valeurs.
        """
        self.sommets = []  # liste des sommets

        if valeurs != "":
            for sommet in valeurs.split(","):
                self.sommets.append(Sommet(sommet))
  1. Ajouter au code de la classe Graphe la re-définition de la méthode __repr__ donnée ci-dessous :

    def __repr__(self: Graphe) -> str:
        """
        Représentation du graphe sous forme d'une chaîne de
        caractères.
        """
        rep = "{"
        for i, sommet in enumerate(self.sommets):
            rep += repr(sommet)
            if i < len(self.sommets) - 1:  # Ajout de la virgule sauf dernier tour
                rep += ", "
        rep += "}"
        return rep

    Cette méthode permet de représenter un graphe sous la forme d’une chaîne de caractères.

  2. Tester la définition de la classe Graphe à l’aide du code suivant, sous les lignes de code de la question 3 :

    g1 = Graphe("a,b,c,d")
    print(g1)
  3. Écrire le code de la méthode existe_sommet dont la spécification est :

    def existe_sommet(self: Graphe, s: str) -> bool:
        """
        Vérifie que le sommet s existe bien dans le graphe.
        """
Réponse
def existe_sommet(self: Graphe, s: str) -> bool:
    """
    Vérifie que le sommet s existe bien dans le graphe.
    """
    sommet_present = False  # Sommet pas présent
    for sommet in self.sommets:  # sommet référence un objet
        if sommet.val == s:
            sommet_present = True
    return sommet_present
  1. Tester le code précédent en ajoutant les instructions suivantes, à la fin du fichier :

    print(f"Sommet g présent dans le graphe : {g1.existe_sommet('g')}")
    print(f"Sommet a présent dans le graphe : {g1.existe_sommet('a')}")
  2. Écrire le code de la méthode ajout_sommet dont la spécification est :

    def ajout_sommet(self: Graphe, val: str) -> None:
        """
        Ajout du sommet de valeur val au graphe.
    
        Si le sommet est déjà présent dans le graphe une exception
        est levée.
        """
Réponse
def ajout_sommet(self: Graphe, val: str) -> None:
    """
    Ajout du sommet de valeur val.

    Si le sommet est déjà présent dans le graphe une exception
    est levée.
    """
    if self.existe_sommet(val):
        raise Exception("Sommet déjà présent dans le graphe !")

    self.sommets.append(Sommet(val))
  1. Tester le code précédent en ajoutant les instructions suivantes, à la fin du fichier :

    g1.ajout_sommet("e")
    print(g1)
  2. Écrire le code de la méthode recuperation_sommet dont la spécification est :

    def recuperation_sommet(self: Graphe, s: str) -> Sommet:
        """
           Récupère l'objet de type sommet, présent dans la liste
        sommets, dont la valeur/étiquette est s.
           Lève une exception si le sommet n'existe pas.
        """

​ Remarque : Cette méthode simplifie l’écriture des méthodes suivantes.

Réponse
def recuperation_sommet(self: Graphe, s: str) -> Sommet:
    """
    Récupère le sommet de valeur s.
    Lève une exception si le sommet n'existe pas.
    """
	if not self.existe_sommet(s):
	    raise Exception(f"Le sommet {s} n'existe pas.")

	for objet_sommet in self.sommets:
	    if objet_sommet.val == s:
	        return objet_sommet
  1. Écrire le code de la fonction existe_arete dont la spécification est :

    def existe_arête(self, s1: str, s2: str) -> bool:
        """
        Détermine si l'arête {s1, s2} existe dans le graphe.
    
        Ne vérifie pas l'existence de l'arête {s2, s1}.
        Lève une exception si l'un des sommets n'existe pas.
        """
Réponse
def existe_arête(self, s1: str, s2: str) -> bool:
    """
    Détermine si l'arête {s1, s2} existe dans le graphe.

    Ne vérifie pas l'existence de l'arête {s2, s1}.
    Lève une exception si l'un des sommets n'existe pas.
    """
	objet_sommet_depart = self.recuperation_sommet(s1)
	objet_sommet_arrivee = self.recuperation_sommet(s2)

	return objet_sommet_arrivee in objet_sommet_depart.adj
  1. Écrire le code de la fonction ajout_arete dont la spécification est :

    def ajout_arete(self: Graphe, s1: str, s2: str) -> None:
        """
        Ajoute l'arête (ou l'arc) {s1, s2} au graphe.
    
        Si les sommets n'existent pas, on lève une exception.
        Si l'arête existe déjà, on lève une exception.
        Ne crée pas l'arête {s2, s1}.
        """
Réponse
def ajout_arete(self: Graphe, s1: str, s2: str) -> None:
    """
    Ajoute l'arête (ou l'arc) {s1, s2} au graphe.

    Si les sommets n'existent pas, on lève une exception.
    Si l'arête existe déjà, on lève une exception.
    Ne crée pas l'arête {s2, s1}.
    """
    # L'arête existe-t-elle déjà ?
    if self.existe_arête(s1, s2):
        raise Exception("Arête existe déjà !")

    # Récupération des sommets
    sommet_depart = self.recuperation_sommet(s1)
    sommet_destination = self.recuperation_sommet(s2)

    # Ajout du sommet s2 à la liste des adjacents de s1
    sommet_depart.adj.append(sommet_destination)
  1. Tester le code précédent en ajoutant les instructions suivantes, à la fin du fichier :

    g1.ajout_arete("a", "b")
    g1.ajout_arete("b", "a")
    g1.ajout_arete("a", "e")
    # g1.ajout_arete("a", "b")
    g1.ajout_arete("c", "e")
    g1.ajout_arete("e", "c")
    print(g1)
  2. Écrire le code de la fonction est_non_oriente dont la spécification est :

    def est_non_oriente(self: Graphe) -> bool:
        """
        Détermine si le graphe est non orienté.
        """
Réponse
def est_non_oriente(self: Graphe) -> bool:
    """
    Détermine si le graphe est non orienté.
    """
    for sommet1 in self.sommets:
        for sommet2 in sommet1.adj:
            if not self.existe_arête(sommet2.val, sommet1.val):
                return False
    return True
  1. Tester le code précédent en ajoutant les instructions suivantes, à la fin du fichier :

    print(f"Le graphe est non orienté : {g1.est_non_oriente()}")
    g1.ajout_arete("e", "a")
    print(f"Le graphe est non orienté : {g1.est_non_oriente()}")
  2. On souhaite maintenant écrire le code de la fonction construction_matrice dont la spécification est :

    def construction_matrice(self: Graphe) -> list[list[int]]:
        """
        Construction de la matrice sommet - sommet du graphe.
        """

    Compléter le code suivant :

    def construction_matrice(self: Graphe) -> list[list[int]]:
        """
        Construction de la matrice sommet - sommet du graphe.
        """
        val_sommets_ordonnees = sorted([sommet.val for sommet in self.sommets])
    
        matrice = .....  # Initialisation de la matrice
        for nom_sommet in val_sommets_ordonnees:
            # Récupération de l'objet de type sommet associé au nom
            sommet = .....
            # Récupération des noms des sommets adjacents
            nom_sommets_adjacents = [
                sommet_adj.val for sommet_adj in sommet.adj]
    
            ligne_matrice = .....         # Initialisation de la ligne de la matrice
            for i in range(len(val_sommets_ordonnees)):
                if val_sommets_ordonnees[i] in nom_sommets_adjacents:
                    ......
                else:
                    ......
            .....  # Ajout de la ligne à la matrice
    
        return matrice
Réponse
def construction_matrice(self: Graphe) -> list[list[int]]:
    """
    Construction de la matrice sommet - sommet du graphe.
    """
    val_sommets_ordonnees = sorted([sommet.val for sommet in self.sommets])

    matrice = []  # Initialisation de la matrice

    for nom_sommet in val_sommets_ordonnees:
        # Récupération de l'objet de type sommet associé au nom
        sommet = self.recuperation_sommet(nom_sommet)
        # Récupération des noms des sommets adjacents
        nom_sommets_adjacents = [sommet_adj.val for sommet_adj in sommet.adj]

        ligne_matrice = []  # Initialisation de la ligne de la matrice
        for i in range(len(val_sommets_ordonnees)):
            if val_sommets_ordonnees[i] in nom_sommets_adjacents:
                ligne_matrice.append(1)
            else:
                ligne_matrice.append(0)
        matrice.append(ligne_matrice)  # Ajout de la ligne à la matrice

    return matrice
  1. Tester le code précédent en ajoutant les instructions suivantes, à la fin du fichier :

    print(f"Matrice : {g1.construction_matrice()}")
  2. Écrire le code de la méthode representation_matrice dont la spécification est :

    def representation_matrice(self: Graphe) -> str:
        """
        Retourne une chaîne de caractères qui permet un
        affichage classique de la matrice (lignes x colonnes).
        """

    Tester le code.

Réponse
def representation_matrice(self: Graphe) -> str:
    """
    Retourne une chaîne de caractères qui permet un
    affichage classique de la matrice (lignes x colonnes).
    """
    matrice = self.construction_matrice()

    rep = ""
    nbre = len(matrice)  # nombre de lignes et de colonnes
    for i in range(nbre):
        for j in range(nbre):
            rep += str(matrice[i][j]) + "\t"
        rep += "\n"
    return rep

Extensions possibles

Il est possible de compléter la classe en définissant les méthodes suivantes :

  • taille, de spécification :

    def taille(self: Graphe) -> int:
        """
        Retourne le nombre de sommets dans le graphe.
        """
  • rend_non_oriente, de spécification :

    def rend_non_oriente(self: Graphe) -> None:
        """
        Assure que pour toute arête {s1, s2} il existe une
        arête {s2, s1}. Si ce n'est pas le cas, cette arête
        est créée.
        """
  • suppression_arete, de spécification :

    def suppression_arete(self: Graphe, s1: str, s2: str) -> None:
        """
        Supprime l'arête {s1, s2} si elle existe, lève une exception
        dans le cas contraire.
        """
  • suppression_sommet, de spécification :

    def suppression_sommet(self: Graphe, s: str) -> None:
        """
        Supprime le sommet s s'il existe, lève une exception dans
        le cas contraire.
    
        S'assure avant la suppression du sommet que toute arrête
        dans laquelle il intervient est supprimée.
        """
Physique, Chimie et Informatique > Terminales Spé. NSI > Les graphes

Représentation d'un graphe en informatique

Plusieurs modes de représentation peuvent être implémentés pour stocker des graphes : matrices d’adjacence (ou sommet-sommet), listes des voisins, des successeurs ou des prédécesseurs. Lors de cette séance nous allons écrire les classes réalisant ces implémentations.

Matrice sommet-sommet

  1. Écrire le code de la classe GrapheM qui implémente une matrice sommet-sommet.
    La spécification du constructeur de la classe est :
def __init__(self: GrapheM, mat: List[List[int]]) -> None:
    """
    Constructeur de la classe.
    """

Remarque : cette classe possède l’attribut mat qui référence la matrice d’adjacence.

Solution
class GrapheM:
    """
    Implémentation de la représentation
    matricielle d'un graphe.
    """

    def __init__(self: GrapheM, mat: List[List[int]]) -> None:
        """
        Constructeur de la classe.
        """
        self.mat = mat
  1. Ajouter à la classe GrapheM une redéfinition de la méthode spéciale __str__ de façon à ce qu’un appel à la fonction print avec comme argument un objet représentant un graphe donne un affichage qui rappelle celui d’une matrice (lignes et colonnes).
Solution
def __str__(self: GrapheM) -> str:
    rep = ""
    for i in range(len(self.mat)):
        rep = rep + str(self.mat[i][0])  # Premier élement de la ligne
        for j in range(1, len(self.mat[0])):
            rep = rep + " " + str(self.mat[i][j])
        rep = rep + "\n"
    return rep
  1. Écrire le code d’une fonction main qui permet de tester l’implémentation de la classe et la représentation du graphe à l’écran.
    Choisir comme matrices tests
$$
M_1 =
\begin{pmatrix}
1 & 1 & 0 \cr
0 & 1 & 1 \cr
0 & 0 & 1 \cr
\end{pmatrix}
\text{ et }
M_2 =
\begin{pmatrix}
0 & 1 & 1 & 0 \cr
1 & 0 & 1 & 1 \cr
1 & 1 & 0 & 1 \cr
0 & 1 & 1 & 0 \cr
\end{pmatrix}
$$
Remarque
Les sommets du graphe sont représentés par des entiers naturels.
Solution
def main():
    """Fonction principale"""
    mat1 = [[1, 1, 0], [0, 1, 1], [0, 0, 1]]
    mat2 = [[0, 1, 1, 0], [1, 0, 1, 1], [1, 1, 0, 1], [0, 1, 1, 0]]

    graph11 = GrapheM(mat1)
    graph21 = GrapheM(mat2)

    print(graph11)
    print(graph21)


main()
  1. Représenter les deux graphes sur une feuille.

  2. Écrire le code de la méthode nbre_sommets qui détermine le nombre de sommets du graphe.
    Jeu de tests :

assert graph11.nbre_sommets() == 3
assert graph21.nbre_sommets() == 4
Solution

Une matrice sommet-sommet est carrée ; le nombre de lignes est donc égal au nombre de colonnes.

def nbre_sommets(self: GrapheM) -> int:
    """
    Retourne le nombre de sommets du graphe
    """
    return len(self.mat)
  1. Écrire le code de la fonction est_lie dont la spécification est :
def est_lie(self: GrapheM, i: int, j: int) -> bool:
    """
    Retourne True s'il existe une relation (arête ou arc)
    entre les sommets i et j, False sinon.
    """

Jeu de tests possible :

assert graph11.est_lie(1, 1) == True
assert graph11.est_lie(0, 1) == True
assert graph11.est_lie(2, 0) == False
Solution
def est_lie(self: GrapheM, i: int, j: int) -> bool:
    """
    Retourne True s'il existe une relation (arête ou arc)
    entre les sommets i et j, False sinon.
    """
    return self.mat[i][j] != 0
  1. Quelle est la particularité de la matrice sommet-sommet d’un graphe non orienté ?
Solution

La matrice est symétrique par rapport à la diagonale.

  1. Écrire le code de la fonction est_non_oriente dont la spécification est
def est_non_oriente(self: GrapheM) -> bool:
    """
    Retourne True si le graphe est non orienté
    (si la matrice est symétrique) et False si le
    graphe est orienté.
    """

Jeu de tests :

assert graph11.est_non_oriente() == False
assert graph21.est_non_oriente() == True
Solution
def est_non_oriente(self: GrapheM) -> bool:
    """
    Retourne True si le graphe est non orienté
    (si la matrice est symétrique) et False si le
    graphe est orienté.
    """
    n = len(self.mat)

    for i in range(n):
        for j in range(i + 1, n):
            if self.mat[i][j] != self.mat[j][i]:
                return False
    return True

Liste d’adjacence

Dans cette partie, on implémente la liste d’adjacence (liste des voisins) d’un graphe non orienté ou la liste des successeurs d’un graphe orienté.

  1. Écrire le code de la classe GrapheL qui implémente une liste des voisins.
    La spécification du constructeur de la classe est :
def __init__(self: GrapheL, lst: List[List[int]]) -> None:
    """
    Constructeur de la classe.
    """

Remarque : cette classe possède l’attribut lst qui référence une liste d’adjacence.

Solution
class GrapheL:
    """
    Implémentation de la liste des voisins d'un graphe non orienté.
    """

    def __init__(self, lst: List[List[int]]) -> None:
        self.lst = lst
  1. Ajouter à la classe GrapheL une redéfinition de la méthode spéciale __str__ de façon à ce qu’un appel à la fonction print avec comme argument un objet représentant un graphe donne un affichage qui rappelle celui d’une liste de listes.
Solution
def __str__(self: GrapheLV) -> str:
    """
    Représentation sous forme d'une chaîne de caractères de l'objet.
    """
    rep = ""

    for i in range(len(self.lst)):
        rep += "{} :".format(i)
        for j in range(len(self.lst[i])):
            rep += " " + str((self.lst[i][j]))
        rep += "\n"

    return rep
  1. Tester le code précédent à l’aide des listes des voisins/successeurs des graphes dont les matrices sommet-sommet sont données dans la première section.
Solution
lst1 = [[0, 1], [1, 2], [2]]
lst2 = [[1, 2], [0, 2, 3], [0, 1, 3], [1, 2]]

graph12 = GrapheL(lst1)
graph22 = GrapheL(lst2)

print(graph12)
print(graph22)
  1. Écrire le code de la méthode nbre_sommets qui détermine le nombre de sommets du graphe.
    Jeu de tests :
assert graph12.nbre_sommets() == 3
assert graph22.nbre_sommets() == 4
Solution
def nbre_sommets(self: GrapheL) -> int:
    """
    Retourne le nombre de sommets du graphe.
    """
    return len(self.lst)
  1. Écrire le code de la fonction est_lie dont la spécification est :
def est_lie(self: GrapheL, i: int, j: int) -> bool:
    """
    Retourne True s'il existe une relation (arête ou arc) entre les sommets i et j, False sinon.
    """

Jeu de tests possible :

assert graph12.est_lie(1, 1) == True
assert graph12.est_lie(0, 1) == True
assert graph12.est_lie(2, 0) == False
Solution
def est_lie(self: GrapheL, i: int, j: int) -> bool:
    """
    Retourne True s'il existe une relation (arête ou arc) entre les sommets i et j, False sinon.
    """
    return j in self.lst[i]
  1. Écrire le code de la fonction est_non_oriente dont la spécification est
def est_non_oriente(self: GrapheL) -> bool:
    """
    Retourne True si le graphe est non orienté, False sinon.
    """

Jeu de tests :

assert graph12.est_non_oriente() == False
assert graph22.est_non_oriente() == True
Solution
def est_non_oriente(self: GrapheL) -> bool:
    """
    Retourne True si le graphe est non orienté (si la matrice est symétrique) et False si le graphe est orienté.
    """
    for i in range(len(self.lst)):
        for j in range(len(self.lst[i])):
            s = self.lst[i][j]  # sommet
            if i not in self.lst[s]:
                return False
    return True

Passage d’une représentation à l’autre

  1. Ajouter à la classe GrapheL la méthode lst_to_mat dont la spécification est :
def lst_to_mat(self: GrapheL) -> GrapheM:
    """
    Génère la matrice sommet-sommet à partir de la liste des voisins/successeurs.
    """

Tests :

graph13 = graph12.lst_to_mat()
print(graph13)
graph23 = graph22.lst_to_mat()
print(graph23)
Solution
def lst_to_mat(self: GrapheL) -> GrapheM:
    """
    Génère la matrice sommet-sommet à partir de la liste des
    voisins/successeurs.
    """
    mat = []
    n = len(self.lst)

    for i in range(n):
        ligne = []
        for j in range(n):
            if j in self.lst[i]:
                ligne.append(1)
            else:
                ligne.append(0)
        mat.append(ligne)

    return GrapheM(mat)
  1. Ajouter à la classe GrapheM la méthode mat_to_lst dont la spécification est :
def mat_to_lst(self: GrapheM) -> GrapheL:
    """
    Génère la liste des voisins/successeurs à partir de la matrice sommet-sommet.
    """

Tests :

graph14 = graph11.mat_to_lst()
print(graph14)
graph24 = graph21.mat_to_lst()
print(graph24)
Solution
def mat_to_lst(self: GrapheM) -> GrapheL:
    """
    Génère la liste des voisins/successeurs à partir de la matrice sommet-sommet.
    """
    liste = []  # liste des listes pour tous les sommets
    for i in range(len(self.mat)):
        rel = []  # relation pour le sommet i
        for j in range(len(self.mat)):
            if self.mat[i][j] != 0:
                rel.append(j)
        liste.append(rel)
    return GrapheL(liste)

Code complet

Code complet en ligne
Physique, Chimie et Informatique > Terminales Spé. NSI > Les graphes

Parcours en profondeur : écriture du code en Python

Écriture d’une classe Graphe

L’objectif de cette partie est l’écriture du code modélisant un graphe orienté. La représentation choisie est celle d’un dictionnaire de successeurs (en cours et dans le document 15,2 on a étudié les représentations par des matrice et liste de successeurs).
La représentation par un dictionnaire de successeurs présente de nombreux avantages. Par exemple,

  • les sommets peuvent être des entiers ou des chaînes de caractères quelconques ;
  • La complexité de la liste des successeurs est directement proportionnelle au nombre de successeurs pour un sommet donné. L’occupation mémoire est donc faible si les sommets possèdent peu de successeurs.
    Remarque : dans le cas d’une matrice d’adjacence, la taille est fixe et comporte N2N^2 éléments si le nombre de sommets est égal à NN.

Remarque

Contrairement à ce qui a été fait dans le document 15,2, la classe qui va être implémentée ici permettra d’initialiser un graphe vide, puis de le constituer progressivement.

  1. Initialiser la classe Graphe. La méthode __init__ a pour seule fonction l’affectation d’un dictionnaire vide à l’attribut succ.

    Solution
    from __future__ import annotations
    from typing import List, Union
    
    
    class Graphe:
        def __init__(self: Graphe) -> None:
            self.succ = {}

  2. Créer la méthode ajouter_sommet dont la spécification est :

def ajouter_sommet(self: Graphe, s: Union[int, str]) -> None:
    """
    Ajoute le sommet s (entier ou chaîne de caractères) au graphe
    s'il n'est pas déjà présent.
    s est une clé du dictionnaire succ. Sa valeur associée par défaut
    est une liste vide.
    """
Solution
def ajouter_sommet(self: Graphe, s: Union[int, str]) -> None:
    """
    Ajoute le sommet s (entier ou chaîne de caractères) au graphe
    s'il n'est pas déjà présent.
    s est une clé du dictionnaire succ. Sa valeur associée par défaut
    est une liste vide.
    """
    if s not in self.succ.keys():
        self.succ[s] = []
  1. Créer la méthode ajouter_arc dont la spécification est :
def ajouter_arc(self: Graphe, s1: Union[int, str], s2: Union[int, str]) -> None:
    """
    Ajoute s2 à la liste des successeurs de s1. Si s1 et s2 n'existent pas, ils sont
    créés en utilisant la méthode ajouter_sommet.
    """
Solution
def ajouter_arc(self: Graphe, s1: Union[int, str], s2: Union[int, str]) -> None:
    """
    Ajoute s2 à la liste des successeurs de s1. Si s1 et s2 n'existent pas, ils sont
    créés en utilisant la méthode ajouter_sommet.
    """
    self.ajouter_sommet(self, s1)
    self.ajouter_sommet(self, s2)
    if s2 not in self.succ[s1]:
        self.succ[s1].append(s2)
  1. Créer la méthode existe_arc dont la spécification est :
def existe_arc(self: Graphe, s1: Union[int, str], s2: Union[int, str]) -> bool:
    """
    Retourne True si l'arc s1 -> s2 existe.
    """
Solution
def existe_arc(self: Graphe, s1: Union[int, str], s2: Union[int, str]) -> bool:
    """
    Retourne True si l'arc s1 -> s2 existe.
    """
    return s2 in self.succ[s1]
  1. Créer la méthode liste_sommets dont la spécification est :
def liste_sommets(self: Graphe) -> List[Union[int, str]]:
    """
    Retourne la liste des sommets du graphe.
    """
Solution
def liste_sommets(self: Graphe) -> List[Union[int, str]]:
    """
    Retourne la liste des sommets du graphe.
    """
    return list(self.succ.keys())
  1. Créer la méthode nbre_sommets dont la spécification est :
def nbre_sommets(self: Graphe) -> int:
    """
    Retourne le nombre de sommets du graphe.
    Utilise la méthode liste_sommets.
    """
Solution
def nbre_sommets(self: Graphe) -> int:
    """
    Retourne le nombre de sommets du graphe.
    Utilise la méthode liste_sommets.
    """
    return len(self.liste_sommets())
  1. Créer la méthode liste_successeurs dont la spécification est :
def liste_successeurs(self: Graphe, s: Union[int, str]) -> List[Union[int, str]]:
    """
    Retourne la liste des successeurs du sommet s1.
    """
Solution
def liste_successeurs(self: Graphe, s: Union[int, str]) -> List[Union[int, str]]:
    """
    Retourne la liste des successeurs du sommet s1.
    """
    return self.succ[s1]
  1. Dans la partie principale du programme, entrer les instructions qui permettent de coder le graphe suivant :
    graph TD
        A(0) --> B(1)
        B --> C(2)
        A --> D(3)
        D --> B
    
Solution
g = Graphe()
g.ajouter_arc(0, 1)
g.ajouter_arc(0, 3)
g.ajouter_arc(1, 2)
g.ajouter_arc(3, 1)

Parcours en profondeur basé sur la récursivité

  1. Reprendre la fonction parcours_profondeur proposée dans le document 15,3 et la transformer en méthode de la classe Graphe. Sa nouvelle spécification est alors :
def parcours_profondeur(
    self: Graphe, vus: List[Union[int, str]], s: Union[int, str]
) -> None:
    """
    Parcours en profondeur depuis le sommet s.
    Cette méthode prend en argument la liste des sommets déjà visités. Lors du premier appel
    cette liste doit être vide.
    Le parcours est accessible par lecture de la liste vus.
    """
Remarque.
Attention, j’ai modifié le nom d’une méthode : voisins s’appelle désormais liste_successeurs.
Solution
def parcours_profondeur(
    self: Graphe, vus: List[Union[int, str]], s: Union[int, str]
) -> None:
    """
    Parcours en profondeur depuis le sommet s.
    Cette méthode prend en argument la liste des sommets déjà visités. Lors du premier appel
    cette liste doit être vide.
    Le parcours est accessible par lecture de la liste vus.
    """
    if s not in vus:
        vus.append(s)
        for v in self.liste_successeurs(s):
            parcours_profondeur(self, vus, v)
  1. Créer la méthode existe_chemin dont la spécification est :
def existe_chemin(self: Graphe, s1: Union[int, str], s2: Union[int, str]) -> bool:
    """
    Retourne True s'il existe un chemin depuis s1 jusqu'à s2.
    """
Solution
def existe_chemin(self: Graphe, s1: Union[int, str], s2: Union[int, str]) -> bool:
    """
    Retourne True s'il existe un chemin depuis s1 jusqu'à s2.
    """
    vus = []
    self.parcours_profondeur(self, vus, s1)
    return s2 in vus
  1. Vérifier le code précédent en utilisant le graphe proposé à la question 8.

Comment construire le chemin entre s1 et s2 ?\

  • Remplacer, dans la méthode parcours_profondeur la liste vus par un dictionnaire dont les clés sont les sommets visités et les valeurs associées sont les sommets prédécesseurs. Attribuer la valeur None au sommet de départ.
  • Une fois le parcours en profondeur achevé, on peut vérifier qu’il existe un chemin en vérifiant si les deux sommets sont dans la liste des valeurs du dictionnaire.
  • Une fois le parcours en profondeur achevé, on peut donner le parcours en remontant le dictionnaire depuis le sommet d’arrivée.
  1. Modifier le code des méthodes parcours_profondeur et existe_chemin à partir des consignes ci-dessus.

  2. Créer la méthode chemin_entre dont la spécification est :

def chemin_entre(
    self: Graphe, s1: Union[int, str], s2: Union[int, str]
) -> List[Union[int, str]]:
    """
    Vérifie que le chemin entre s1 et s2 existe puis le retourne sous la forme d'une liste.
    """

Parcours en profondeur basé sur la structure pile

  1. Écrire le code de la classe Pile. En plus de la méthode __init__ cette classe doit posséder les méthodes est_vide, empiler et depiler.

  2. Adapter le code de la fonction proposée dans le document document 15,3 afin de la transformer en méthode de la classe Graphe.

Physique, Chimie et Informatique > Terminales Spé. NSI > Les graphes

Coloration d'un graphe

L’objectif de cette séance est de découvrir comment colorier chaque sommet d’un graphe à l’aide d’un algorithme glouton.

Info

Colorier un graphe signifie associer une couleur à chacun de ses sommets de façon à ce que deux sommets liés par une arête n’aient pas la même couleur (deux sommets non adjacents peuvent avoir la même couleur).

Colorier un graphe avec un nombre minimal de couleurs est un problème difficile mais l’utilisation d’un algorithme glouton permet de résoudre le problème, au prix d’un nombre de couleurs qui n’est pas toujours minimal.

Remarques

  • Les couleurs seront représentées par des nombres entiers débutant à la valeur 0.
  • La classe Graphe du document Représentation d’un graphe sera utilisée.
    Son code est reproduit ci-dessous.
    Code
    """
    Représentation d’un graphe à l'aide d'une liste d'adjacence.
    """
    
    from __future__ import annotations
    
    
    class Sommet:
        """
        Représentation d'un sommet.
        """
    
        def __init__(self: Sommet, val: str) -> None:
            """
            Initialisation du sommet.
            """
            self.val = val
            self.adj = []  # Sommets adjacents
    
        def liste_adjacents(self: Sommet) -> list[Sommet]:
            """
            Retourne la liste des sommets adjacents.
            """
            return self.adj
    
        def ajoute_adjacent(self: Sommet, som: Sommet) -> None:
            """Ajoute un sommet adjacent"""
            self.adj.append(som)
    
        def __repr__(self: Sommet) -> str:
            rep = str(self.val) + " : ["
            for i, sommet in enumerate(self.adj):
                rep += str(sommet.val)
                if i < len(self.adj) - 1:
                    rep += ", "
            rep += "]"
            return rep
    
    
    class Graphe:
        """
        Représentation du graphe.
        """
    
        def __init__(self: Graphe, valeurs: str = "") -> None:
            """
            La liste des sommets peut être passée dans une
            chaîne de caractères. Chaque sommet doit être
            séparé du précédent par une virgule.
    
            Hypothèse : chaque sommet n'est présent qu'une seule
            fois dans valeurs.
            """
            self.sommets = []  # liste des sommets
    
            if valeurs != "":
                for sommet in valeurs.split(","):
                    self.sommets.append(Sommet(sommet))
    
        def liste_sommets(self: Graphe) -> list[Sommet]:
            """
            Retourne la liste des sommets du graphe.
            """
            return self.sommets
    
        def ajout_sommet(self: Graphe, val: str) -> None:
            """
            Ajout du sommet de valeur val.
    
            Si le sommet est déjà présent dans le graphe une exception
            est levée.
            """
            if self.existe_sommet(val):
                raise Exception("Sommet déjà présent dans le graphe !")
    
            self.sommets.append(Sommet(val))  # Ajout de l'objet de type Sommet
    
        def existe_sommet(self: Graphe, s: str) -> bool:
            """
            Vérifie que le sommet s existe bien dans le graphe.
            """
            sommet_present = False  # Sommet pas présent
            for sommet in self.sommets:  # sommet référence un objet
                if sommet.val == s:
                    sommet_present = True
                    break
            return sommet_present
    
        def recuperation_sommet(self: Graphe, s: str) -> Sommet:
            """
            Récupère le sommet de valeur s.
            Lève une exception si le sommet n'existe pas.
            """
            if not self.existe_sommet(s):
                raise Exception(f"Le sommet {s} n'existe pas.")
    
            for objet_sommet in self.sommets:
                if objet_sommet.val == s:
                    return objet_sommet
    
        def ajout_arete(self: Graphe, s1: str, s2: str) -> None:
            """
            Ajoute l'arête (ou l'arc) {s1, s2} au graphe.
    
            Si les sommets n'existent pas, on lève une exception.
            Si l'arête existe déjà, on lève une exception.
            Ne crée pas l'arête {s2, s1}.
            """
            # L'arête existe-t-elle déjà ?
            if self.existe_arête(s1, s2):
                raise Exception("Arête existe déjà !")
    
            # Récupération des sommets
            sommet_depart = self.recuperation_sommet(s1)
            sommet_destination = self.recuperation_sommet(s2)
    
            # Ajout du sommet s2 à la liste des adjacents de s1
            sommet_depart.ajoute_adjacent(sommet_destination)
    
        def existe_arête(self, s1: str, s2: str) -> bool:
            """
            Détermine si l'arête {s1, s2} existe dans le graphe.
    
            Ne vérifie pas l'existence de l'arête {s2, s1}.
            Lève une exception si l'un des sommets n'existe pas.
            """
            objet_sommet_depart = self.recuperation_sommet(s1)
            objet_sommet_arrivee = self.recuperation_sommet(s2)
    
            return objet_sommet_arrivee in objet_sommet_depart.liste_adjacents()
    
        def est_non_oriente(self: Graphe) -> bool:
            """
            Détermine si le graphe est non orienté.
            """
            for sommet1 in self.sommets:
                for sommet2 in sommet1.liste_adjacents():
                    if not self.existe_arête(sommet2.val, sommet1.val):
                        return False
            return True
    
        def construction_matrice(self: Graphe) -> list[list[int]]:
            """
            Construction de la matrice sommet - sommet du graphe.
            """
            val_sommets_ordonnees = sorted([sommet.val for sommet in self.sommets])
    
            matrice = []  # Initialisation de la matrice
    
            for nom_sommet in val_sommets_ordonnees:
                # Récupération de l'objet de type sommet associé au nom
                sommet = self.recuperation_sommet(nom_sommet)
                # Récupération des noms des sommets adjacents
                nom_sommets_adjacents = [sommet_adj.val for sommet_adj in sommet.adj]
    
                ligne_matrice = []  # Initialisation de la ligne de la matrice
                for i in range(len(val_sommets_ordonnees)):
                    if val_sommets_ordonnees[i] in nom_sommets_adjacents:
                        ligne_matrice.append(1)
                    else:
                        ligne_matrice.append(0)
                matrice.append(ligne_matrice)  # Ajout de la ligne à la matrice
    
            return matrice
    
        def representation_matrice(self: Graphe) -> str:
            """
            Retourne une chaîne de caractères qui permet un
            affichage classique de la matrice (lignes x colonnes).
            """
            matrice = self.construction_matrice()
    
            rep = ""
            nbre = len(matrice)  # nombre de lignes et de colonnes
            for i in range(nbre):
                for j in range(nbre):
                    rep += str(matrice[i][j]) + "\t"
                rep += "\n"
            return rep
    
        def __repr__(self: Graphe) -> str:
            """
            Représentation du graphe sous forme d'une chaîne de caractères.
            """
            rep = "{"
            for i, sommet in enumerate(self.sommets):
                rep += repr(sommet)
                # Ajout de la virgule sauf dernier tour de boucle
                if i < len(self.sommets) - 1:
                    rep += ", "
            rep += "}"
            return rep
    
        def suppression_arete(self: Graphe, s1: str, s2: str) -> None:
            """
            Supprime l'arête {s1, s2} si elle existe, lève une exception
            dans le cas contraire.
            """
            pass
    
        def suppression_sommet(self: Graphe, s: str) -> None:
            """
            Supprime le sommet s s'il existe, lève une exception dans
            le cas contraire.
    
            S'assure avant la suppression du sommet que toute arrête
            dans laquelle il intervient est supprimée.
            """
            pass
    
        def rend_non_oriente(self: Graphe) -> None:
            """
            Assure que pour toute arête {s1, s2} il existe une
            arête {s2, s1}. Si ce n'est pas le cas, cette arête
            est créée.
            """
            pass
    
        def taille(self: Graphe) -> int:
            """
            Retourne le nombre de sommets dans le graphe.
            """
            return len(self.sommets)
    
    
    if __name__ == "__main__":
        s1 = Sommet("a")
        s2 = Sommet("b")
        s3 = Sommet("c")
        s1.adj.append(s2)
        s1.adj.append(s3)
        print(s1)
        print(s2)
    
        g1 = Graphe("a,b,c,d")
        print(g1)
        print(f"Sommet g présent dans le graphe : {g1.existe_sommet('g')}")
        print(f"Sommet a présent dans le graphe : {g1.existe_sommet('a')}")
        g1.ajout_sommet("e")
        print(g1)
        g1.ajout_arete("a", "b")
        g1.ajout_arete("b", "a")
        g1.ajout_arete("a", "e")
        # g1.ajout_arete("a", "b")
        g1.ajout_arete("c", "e")
        g1.ajout_arete("e", "c")
        print(g1)
        print(f"Le graphe est non orienté : {g1.est_non_oriente()}")
        g1.ajout_arete("e", "a")
        print(f"Le graphe est non orienté : {g1.est_non_oriente()}")
        print(f"Matrice : {g1.construction_matrice()}")
        print(g1.representation_matrice())
        print(f"Taille du graphe : {g1.taille()}")
    
        print("---------------------")
        g2 = Graphe("a,b,c,d,e,f,g")
        print(f"Taille du graphe : {g2.taille()}")
        g2.ajout_arete("a", "d")
        g2.ajout_arete("a", "b")
        g2.ajout_arete("a", "c")
        g2.ajout_arete("b", "a")
        g2.ajout_arete("b", "c")
        g2.ajout_arete("b", "d")
        g2.ajout_arete("b", "f")
        g2.ajout_arete("c", "a")
        g2.ajout_arete("c", "b")
        g2.ajout_arete("c", "e")
        g2.ajout_arete("d", "a")
        g2.ajout_arete("d", "b")
        g2.ajout_arete("d", "f")
        g2.ajout_arete("e", "c")
        g2.ajout_arete("f", "b")
        g2.ajout_arete("f", "d")
        g2.ajout_arete("f", "g")
        g2.ajout_arete("g", "f")
        print(f"Le graphe est non orienté : {g2.est_non_oriente()}")
        print(g2.representation_matrice())
        print(g2.liste_sommets())

Le code du fichier fourni comporte les instructions suivantes :

g2 = Graphe("a,b,c,d,e,f,g")
    g2.ajout_arete("a", "d")
    g2.ajout_arete("a", "b")
    g2.ajout_arete("a", "c")
    g2.ajout_arete("b", "a")
    g2.ajout_arete("b", "c")
    g2.ajout_arete("b", "d")
    g2.ajout_arete("b", "f")
    g2.ajout_arete("c", "a")
    g2.ajout_arete("c", "b")
    g2.ajout_arete("c", "e")
    g2.ajout_arete("d", "a")
    g2.ajout_arete("d", "b")
    g2.ajout_arete("d", "f")
    g2.ajout_arete("e", "c")
    g2.ajout_arete("f", "b")
    g2.ajout_arete("f", "d")
    g2.ajout_arete("f", "g")
    g2.ajout_arete("g", "f")
  1. Quelle est la taille de ce graphe ?

  2. Représenter ce graphe.

  3. Donner la matrice d’adjacence de ce graphe.

Lancer le programme et vérifier la validité des vos réponses.

Principe de l’algorithme

On parcourt tous les sommets du graphe dans un ordre arbitraire, et pour chaque sommet, on lui attribue la première couleur qui n’est pas déjà attribuée à ses sommets adjacents.

  1. Mettre en œuvre cet algorithme, à la main, sur le graphe proposé dans le code fourni.

L’implémentation de l’algorithme en Python nécessite la définition de deux fonctions : coloriage et choix_couleur dont les spécifications sont :

def coloriage(g: Graphe) -> tuple[dict[str, int], int]:
    """
    Colorie le graphe g passé en argument.
    Retourne un tuple constitué du dictionnaire des couleurs pour chaque
    sommet et du nombre de couleurs utilisées.
    """

et

def choix_couleur(sommet: Sommet, couleurs: dict[str, int]) -> int:
    """
    Choisi la première couleur disponible en fonction de celles
    déjà attribuées aux sommets adjacents.
    """

Remarque : la fonction coloriage appelle la fonction choix_couleur.

  1. Écrire le code Python de ces deux fonctions.
Aide pour l’écriture de la fonction coloriage

La fonction doit :

  • Initialiser à 0 la variable nbre_couleurs. Elle comptabilise le nombre de couleurs différentes utilisées lors du coloriage du graphe.
  • Initialiser au dictionnaire vide la variable couleurs. Ce dictionnaire a pour clés les étiquettes des sommets visités et pour valeurs les couleurs associées.
  • Parcourir tous les sommets du graphe.
    • Pour chacun d’eux lui attribuer une couleur à l’aide de la fonction choix_couleur.
    • Incrémenter d’une unité le compteur de couleurs, si cette couleur n’a pas déjà été utilisée.
    • Mettre à jour le dictionnaire des couleurs.
  • Retourner le tuple constitué du dictionnaire des couleurs et de la variable qui comptabilise le nombre de couleurs utilisées.
Aide pour l’écriture de la fonction choix_couleur

La fonction doit :

  • Déterminer le nombre de sommets adjacents au sommet passé en argument.
  • Initialiser à False la liste de booléens couleurs_attribuees. Les indices de cette liste sont les couleurs déjà attribuées aux sommets adjacents du sommet étudié. La valeur True signifie que la couleur a été attribuée, False que la couleur est libre.
    Dans le pire des cas, tous les sommets adjacents ont déjà une couleur attribuée ; la première couleur attribuable sera donc l’indice nn. C’est la raison pour laquelle la longueur de la liste doit être égale à n+1n+1 si nn est le nombre de sommets adjacents.
  • Doit rechercher les couleurs des sommets adjacents.
    • Pour chaque sommet adjacent, elle doit vérifier dans le dictionnaire couleurs si ce sommet a déjà été colorier.
    • Si c’est le cas et que cette couleur est inférieure à nn, modifier à True la valeur de la liste couleurs_attribuees pour la couleur (indice) en question.
  • Doit rechercher la première couleur (indice) libre dans la liste couleurs_attribuees et la retourner.
Solution
def coloriage(g: Graphe) -> tuple[dict[str, int], int]:
    """
    Colorie le graphe g passé en argument.
    Retourne un tuple constitué du dictionnaire des couleurs pour chaque
    sommet et du nombre de couleurs utilisées.
    """
    nbre_couleurs = 0  # Nombre de couleurs utilisées
    couleurs = {}  # Dictionnaire des sommets colorés

    for sommet in g.liste_sommets():
        # Choix d'une couleur pour le sommet
        couleur = choix_couleur(sommet, couleurs)
        # Incrémentation du compteur de couleurs si nouvelle couleur
        if couleur not in couleurs.values():
            nbre_couleurs += 1
        # Ajout de ce sommet au dictionnaire des couleurs
        couleurs[sommet.val] = couleur

    return couleurs, nbre_couleurs


def choix_couleur(sommet: Sommet, couleurs: dict[str, int]) -> int:
    """
    Choisi la première couleur disponible en fonction de celles
    déjà attribuées aux sommets adjacents.
    """
    # Nbre de sommets adjacents
    n_adj = len(sommet.liste_adjacents())

    # Initialisation des couleurs déjà attribuées (indices de la liste)
    # + 1 assure d'avoir un choix possible pour le sommet étudié.
    couleurs_attribuees = [False for i in range(n_adj + 1)]

    # recherche des couleurs déjà attribuées
    for adj in sommet.liste_adjacents():  # Sommet adjacent
        if adj.val in couleurs.keys():  # Sommet déjà colorié
            couleur_attribuee = couleurs[adj.val]  # avec une valeur <= n
            if couleur_attribuee <= n_adj:
                couleurs_attribuees[couleur_attribuee] = True

    # Détermination de la couleur
    for i in range(len(couleurs_attribuees)):
        if not couleurs_attribuees[i]:
            return i