Notion de graphe
Après avoir visionné la vidéo, répondre aux questions suivantes.
- Question 1 : comment représenter des réseaux routiers, téléphoniques ou sociaux graphiquement ?
- Question 2 : à quoi correspond un sommet ?
- Question 3 : à quoi correspond une arête ?
- Question 4 : quelles différences de représentation existe-il entre une flèche orientée dans un sens ou dans les deux sens ?
- Question 5 : comment définit-on un plus court chemin entre deux sommets A et B d'un graphe ?
- Question 6 : quelle est la définition d'un diamètre ?
Caractéristiques d'un graphe
- La distance entre deux sommets dans un graphe est le nombre de liens constituant le plus court chemin entre eux. Cela traduit le degré de séparation entre deux individus.
- Le diamètre d'un graphe est la plus grande distance que l'on peut trouver entre deux sommets. Cela traduit à quel point les utilisateurs sont éloignés les uns des autres dans le réseau social.
- Le centre d'un graphe est le sommet dont la distance maximale aux autres sommets est la plus petite. Il peut y en avoir plusieurs. Cela correspond à un utilisateur en plein cœur du réseau social.
- Le rayon d'un graphe correspond à la distance maximale entre le centre et les autres sommets du graphe. Cela traduit à quel point certains sommets sont éloignés du centre du graphe.
Quelques exercices d'application
Un petit exemple
À partir de ce graphe, compléter
le tableau suivant (à reproduire sur une feuille).
| Distance de | A | B | C | D | E | Distance la plus grande par ligne |
|---|---|---|---|---|---|---|
| A | ||||||
| B | ||||||
| C | ||||||
| D | ||||||
| E |
Grâce au tableau, identifier le centre du graphe, son diamètre et son rayon.
Représenter un réseau social de 6 personnes
Représenter sous forme d'un graphe, un réseau social constitué de 6 personnes A, B, C, D, E, et F, où :
- A est ami avec B et D
- B est ami avec A, C et E
- C est ami avec B et E
- D est ami avec A et E
- E est ami avec F
| Distance de | A | B | C | D | E | F | Distance la plus grande par ligne |
|---|---|---|---|---|---|---|---|
| A | |||||||
| B | |||||||
| C | |||||||
| D | |||||||
| E | |||||||
| F |
Un peu plus gros
Dans ce réseau, donner
- Un chemin de longueur 4 (composé de 4 arêtes) pour aller de Y à D.
- Le plus court chemin pour aller de Y à D.
- Le centre (ou un des centres) du réseau.
- Le rayon du réseau.
- Le diamètre du réseau.
D'autres vidéos sur les graphes
Un point de vue un peu plus mathématique.