Partie L6 · exercices 39 à 44
Modéliser des relations : sommets, arêtes, distances
Un graphe représente des relations entre des objets :
Réseau routier (villes et routes), réseau social (personnes et amitiés), plan de métro (stations et lignes) : ce sont des graphes.
Un lotissement est divisé en parcelles. Deux parcelles sont voisines si elles ont une frontière commune (pas seulement un coin).
Dessine le graphe de voisinage : un sommet par parcelle, une arête entre deux parcelles voisines.
Fais la liste des voisins de chaque parcelle avant de dessiner. Attention à B : touche-t-elle D ?
📝 réponses dans ton compte rendu, exercice 39
Le propriétaire de la parcelle B achète un bout de la parcelle C, tandis que la parcelle F est séparée en deux (F et G).
Dessine le nouveau graphe de voisinage. Quelles arêtes ont disparu ? Lesquelles sont apparues ?
B occupe maintenant toute la largeur : elle sépare A de C.
📝 réponses dans ton compte rendu, exercice 40
| Mot | Définition | Exemple sur le graphe |
|---|---|---|
| adjacents | deux sommets reliés par une arête | A et B |
| chaîne | suite de sommets reliés deux à deux par des arêtes | C–A–B–E |
| longueur d'une chaîne | nombre d'arêtes de la chaîne | C–A–B–E a pour longueur 3 |
| distance entre deux sommets | longueur de la plus courte chaîne qui les relie | distance de A à E : 2 |
| excentricité d'un sommet | plus grande distance entre ce sommet et les autres | voir exercice 42 |
| diamètre du graphe | plus grande des excentricités | |
| rayon du graphe | plus petite des excentricités | |
| centre du graphe | sommet(s) dont l'excentricité est égale au rayon |
Vigilance
La distance est la longueur de la chaîne la plus courte ; l'excentricité est la plus grande de ces distances. On mélange souvent les deux.
Le sommet G n'a qu'un seul voisin : toute chaîne vers G passe par lui.
📝 réponses dans ton compte rendu, exercice 41
Recopie et complète le tableau des distances entre les sommets du graphe d'exemple, puis la colonne des excentricités.
| A | B | C | D | E | F | G | Excentricité | |
|---|---|---|---|---|---|---|---|---|
| A | 0 | |||||||
| B | 0 | |||||||
| C | 0 | |||||||
| D | 0 | |||||||
| E | 0 | |||||||
| F | 0 | |||||||
| G | 0 |
Déduis-en le diamètre, le rayon et le centre du graphe.
Le tableau est symétrique : la distance de A à B est la même que de B à A.
Pour chaque ligne, l'excentricité est le plus grand nombre de la ligne.
📝 réponses dans ton compte rendu, exercice 42
Un réseau social est formé par une famille de 5 personnes : deux membres quelconques de la famille sont toujours en contact.
Dans un graphe complet, toutes les distances valent 1.
📝 réponses dans ton compte rendu, exercice 43
Deux familles, l'une de 5 personnes (A à E), l'autre de 4 personnes (F à I), sont chacune représentées par un graphe complet. Elles sont en contact par deux de leurs membres : A et F.
Calcule d'abord l'excentricité de A, puis celle de B (qui doit passer par A pour atteindre l'autre famille).
📝 réponses dans ton compte rendu, exercice 44
Synthèse