Bureau d'étude PEIP - IS

TP2

Vous allez devoir télécharger et remplir le fichier tp2.py. Il s'agit d'un fichier python contenant le prototype (c'est à dire la première ligne) de plusieurs fonctions de base sur les graphes.

On commence pour cela par présenter deux façon de modéliser les graphes en pythons : les listes d'adjacence et les matrices d'adjacence. À titre d'exemple, on donne une liste et une matrice qui représentent le même graphe.

On donne pour commencer des fonctions permettant d'afficher une liste d'adjacence et une matrice d'adjacence dans la console. On se propose ensuite de développer les fonctions de bases suivantes :

• - degre_mat(v,m) : retourne le degré d'un sommet v (un entier) dans le graphe représenté par la matrice d'adjacence m
• - degre_list(v,l) : retourne le degré d'un sommet v (un entier) dans le graphe représenté par la liste d'adjacence l
• - degreGraphe(m) : retourne le degré du graphe représenté par la matrice d'adjacence m
• - degreGraphe(l) : retourne le degré du graphe représenté par la liste d'adjacence l
• - ordreGraphe_mat(m) : retourne l'ordre du graphe représenté par la matrice d'adjacence m
• - ordreGraphe_list(l) : retourne l'ordre du graphe représenté par la liste d'adjacence

Attention, ces fonctions ne doivent pas faire plus de quelques lignes chacune. Elles sont là pour vérifier que vous avez bien compris les notions d'ordres sur les graphes et ce que contiennent les liste et matrice d'adjacence.

On propose ensuite de développer les fonctions suivantes :

• - mat_to_list(m) : transforme une matrice m représentant un graphe sous la forme d'une matrice d'adjacence en une liste d'adjacence.
• - list_to_mat(l) : transforme cette fois une liste d'adjacence en matrice d'adjacence.
• - check_mat_list(m,l) : permet de vérifier si une matrice d'ajdacence m et une liste d'adjacence l représentent le même graphe. On demande de ne pas utiliser les fonctions précédente. Attention, il faut faire attention à la taille des éléments manipulés avant de faire des boucles (nombre de sommets, etc.)