Les implémentations.

Les interfaces

Si on souhaite créer une classe Graphe les interfaces à fournir sont :

Créer le graphe (on peut demander l'orientation ou non).
Ajouter un sommet (avec un nom).
Ajouter une arete (avec les pondérations).
Donner la liste des sommets.
Donner le voisinage d'un point.
Donner le degré d'un point.
...

Matrice d'adjacence.

Definitions

A un graphe donné dont les sommets sont numérotés de 1 à n et qui admet au plus une arrete par voisin, on associe une matrice dite d'adjacence dont la case de la ligne i et de colonne j est égal à 0 s'il n'y a pas d’arête entre le sommet i et le sommet j où la pondération de l'arrête sinon (par défaut la pondération est 1).

Exemple

La matrice associée est :

Exercice

Faire la matrice d'adjacence des graphes suivants :
Construire le graphe qui correspond aux matrices suivantes :
- 0 1 1 1 0 0
  
  1 0 0 0 1 1
  
  1 0 0 1 1 0
  
  1 0 1 0 0 1
  
  0 1 1 0 0 1
  
  0 1 0 1 1 0
- 0 1 0 0 0 0
  
  1 0 1 0 1 1
  
  0 1 0 0 0 0
  
  0 1 0 0 0 0
  
  0 1 0 0 0 0
  
  0 1 0 0 0 0
Donner le degré des sommets du graphe suivant :

0 1 1 10 0 1

1 0 0 0 1 1

1 20 0 1 1 0

1 0 5 0 0 1

0 1 4 0 0 1

1 1 0 1 1 0

Implémentation avec les matrices d'adjacence

Remarque

L’implémentation prend de la place en mémoire, en effet on conserve la pondération de chaque arête dans la matrice d'adjacence même si elle n'existe pas.

On n'est pas obligé de faire de la programmation objet à la place on peut conserver et travailler directement sur la matrice d'adjacence (pour des raisons de performance par exemple mais dans ce cas mieux vaut utiliser NumPy qui permet d'utiliser des tableaux se rapprochant de ceux du C (soit plus rapide) ou alors utiliser le C directement).

Implémentation avec les dictionnaires

Remarque

Voici la fonction de test :

Exercices

Exercice

Dessiner une représentation graphique des graphes du script exercice.

En utilisant une des deux implémentations, créer une instance des graphes ci-dessous :

Implémenter une fonction qui donne le degré d'un sommet.

Implémenter une fonction qui teste si le graphe est orienté ou non.

Implémenter une fonction qui donne le nombre de sommets.

Implémenter une fonction qui donne le nombre d’arêtes.

Implémenter une fonction qui prend une liste de sommets et qui retourne si le chemin existe dans le graphe. On donnera en retour un tuple avec un booléen (true , False) et si le chemin existe la longueur du trajet, 0 si le chemin n'existe pas.

Implémenter une fonction qui retourne True si le graphe est complet et false sinon.