Graphe

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

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 :

   1 2 3 4

   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.

É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 $N^2$ éléments si le nombre de sommets est égal à $N$.

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.

• Cours et exercices non corrigés

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 :

1
2
3
4

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.

• Cours et exercices non corrigés