Graphes

Les Graphes: implémentations

Objectifs

- Modéliser des situations sous forme de graphes.

- Écrire les implémentations

- correspondantes d’un graphe : matrice d’adjacence, dictionnaire d'adjacence.

Exercice 1

On cherche a représenter les liens d'amitié entre les personnes d'un réseau social.

On choisit de représenter les liens entre les usagers avec une matrice d'adjacence, si les personnes ont un lien, on met un 1 dans la case correspondante du tableau et s'ils n'ont aucun lien on met un 0, la ligne du tableau pour Alice est complétée :

- Alice est liée avec Emma la case Ligne Alice et colonne Emma = 1 et  la case Ligne Emma  et colonne  Alice=1

- Alice n'est pas liée avec Chloé, la case Ligne Alice et colonne Chloé = 0 et  la case Ligne Chloé  et colonne  Alice= 0

1.1)  Compléter le tableau

1.2) Proposer une matrice d'adjacence pour représenter les liens entre ces personnes.

2.3) Proposer la fonction  sont_amis ( matrice, nom1, nom2) qui prend comme arguments votre matrice et le nom de deux personnes, cette fonction renvoie True si les deux personnes sont liées et False dans le cas contraire.

Exercice 2

On choisit maintenant de représenter les liens entre les usagers avec un dictionnaire dont les clés sont les sommets ( les personnes) et la valeur des clés un ensemble dont le contenu sont les amis de la personne représentée par la clé.

2.1)  Proposer l'implémentation de ce dictionnaire.

2.2) Proposer la fonction  sont_amis ( dico, nom1, nom2) qui prend comme arguments votre dictionnaire et le nom des deux personnes, cette fonction renvoie True si les deux personnes sont liées et False dans le cas contraire.

Créé avec HelpNDoc Personal Edition: Générateur de documentation et EPub facile