¶ Exercice 1 - Passage d'une représentation à une autre
Dans cet exercice, nous utiliserons le graphe ci-dessous :
Question 1 - Écrire une fonction matrice_to_dico. Cette fonction prend en paramètre une liste de sommets et une matrice d'adjacence représentant un graphe. Elle permet de convertir cette matrice en un dictionnaire de voisins.
def matrice_to_dico(sommets, matrice) -> dict:
return
Question 2 - Écrire une fonction dico_to_matrice. Cette fonction prend en paramètre un dictionnaire de voisins représentant un graphe. Elle permet de convertir ce dictionnaire en une matrice d'adjacence.
def dico_to_matrice(dico) -> list:
return
Question 3 - Écrire la liste d'adjacence et le dictionnaire de voisins représentant le graphe ci-dessous. Vous essayerez vos deux fonctions.
¶ Exercice 2 - Une classe Graphe
¶ Partie 1 - Initialisation
L’objectif de ce TP est d’implémenter un graphe en utilisant une classe.
La classe Graphe peut être définie avec 2 attributs :
dicoqui représente un dictionnaire de voisins. Le dictionnaire sera vide par défaut.orientequi indique si le graphe est orienté ou non.
Question 1 - Créer un nouveau fichier Graphe.py.
Question 2 - Écrire la classe Graphe ainsi que son constructeur. Il permet d'initialiser les attributs de la classe.
>>> g = Graphe(False)
Question 3 - Écrire une méthode ajouter_sommet. Cette méthode prend en paramètre une chaîne de caractères ou un entier représentant l’identifiant du sommet. Elle permet d’ajouter un sommet au graphe.
- Il faut empêcher les sommets ayant le même identifiant.
def ajouter_sommet(self, sommet) -> None:
pass
Question 4 - Écrire une méthode ajouter_arete. Cette méthode prend en paramètre 2 sommets. Elle permet d’ajouter une arête au graphe, reliant 2 sommets existants.
- Elle crée une arête uniquement si les 2 sommets existent.
def ajouter_arete(self, s1, s2) -> None
pass
Question 5 - Écrire une méthode affiche Cette méthode permet d'afficher le graphe selon le format suivant.
>>> g = Graphe(False)
>>> g.affiche()
A -> ['B', 'D']
B -> ['C']
C -> ['E', 'F']
D -> ['E']
E -> ['B']
F -> []
G -> ['C']
Question 6 - Dans un fichier main.py, écrire un programme permettant de représenter les deux graphes ci-dessous.
¶ Partie 2 - Méthodes utiles
Question 7 - Écrire la méthode ordre. Cette méthode retourne l'ordre du graphe.
def ordre(self) -> int :
return
Question 8 - Écrire la méthode degre. Cette méthode prend en paramètre un sommet de graphe. . Elle retourne le degré du sommet passé en paramètre.
def degre(self, sommet) -> int:
return
Question 9 - Écrire la méthode voisins. Cette méthode prend en paramètre un sommet du graphe. Elle retourne la liste des voisins du sommet passé en paramètre.
def voisins(self, sommet) -> list :
return
Question 10 - Écrire la méthode arete_presente. Cette méthode prend en paramètre deux sommets de graphe. La méthode retourne True si une arête ou un arc est présent entre les deux sommets passés en paramètre. False sinon.
def arete_presente(self, s1, s2) -> bool:
return
Question 11 - Écrire la méthode supprimer_arete. Cette méthode prend en paramètre deux sommets de graphe. Elle supprime l'arête entre les deux sommets passés entre paramètre.
- On vérifiera que l’arête existe bien entre les 2 sommets.
- On fera attention à l’orientation ou non du graphe.
def supprimer_arete(self, s1, s2) -> None:
pass
Question 12 - Écrire la méthode supprimer_sommet. Cette méthode prend en paramètre un sommet du graphe. Cette méthode supprime le sommet passé en paramètre.
def supprimer_sommet(self, sommet) -> None:
pass