Leçon : Introduction au graphe
Motivations
- Justifier qu’une représentation graphique est un graphe ;
- justifier qu’un graphe est simple ou orienté ; complet ;
- déterminer le degré d’un sommet ;
- reconnaître deux sommets adjacents ;
- résoudre des problèmes concrets de la vie courante à l’aide d’un graphe.
Prérequis
Considérons la figure ci-contre puis donner le nombre de sommets et d’arêtes
de ce quadrilatère.
Situation de vie
Voici les déplacements d’un élève de première scientifique sur quelques
jours : École–Maison, École–Chapelle, École–Stade, Stade–Chapelle et
Stade–Maison. On matérialise l’école, la maison, la chapelle et le stade par
les points E, M, C et S et les déplacements entre les points par un segment.
Faire le graphique présentant tous les déplacements de cet élève.
Activité d’apprentissage
Considérons le graphe suivant :
- Déterminer le nombre de sommets.
- Déterminer le nombre total d’arêtes.
- Recopier et compléter le tableau suivant :
| Sommet |
Nombre de segment connecté au sommet |
| E |
|
| M |
|
| S |
|
| C |
|
| TOTAL |
|
Résumé
A- Vocabulaire
Un graphe est un ensemble constitué des ensembles
$S=\{S_1,S_2,S_3,\ldots,S_n\}$ de points appelés sommets et
d’un ensemble $A=\{A_1,A_2,A_3,\ldots,A_m\}$ d’arêtes ou de segments qui relient
les sommets.
Il est possible de définir un graphe sous le modèle
$G=(S,A)$ où $\text{card}(S)$ est le nombre de sommets et
$\text{card}(A)$ est le nombre d’arêtes. $G$ est le nom du graphe.
Une arête est un segment qui relie deux sommets
(on parlera d’arc dans un graphe orienté).
Exemple
La figure ci-contre est un graphe de 6 sommets et
8 arêtes.
Remarque
Dans un graphe, la longueur des arêtes et la disposition des sommets importent peu. Exemple :
Tous ces graphes sont identiques car le plus important est le nombre
de sommets et le nombre d’arêtes. Pour le cas présenté, tous ces graphes
ont 6 sommets et 8 arêtes.
Une boucle est une arête reliant un sommet à lui-même.
L’arête multiple survient lorsqu’il existe plusieurs arêtes
entre deux sommets.
Deux sommets sont dits adjacents lorsqu’une seule arête relie
ces deux sommets.
Un sommet est dit isolé lorsqu’aucune arête ne relie ce sommet
aux autres sommets.
Une chaîne est une suite d’arêtes consécutives.
La longueur de la chaîne est donnée par le nombre d’arêtes
que la chaîne comporte.
Exemple
- Le sommet C a une boucle.
- Les sommets A et D sont adjacents.
- Entre les sommets A et B il y a des arêtes multiples.
- D – A – C – B est une chaîne de longueur 4.
Cycle : est une chaîne dont les deux extrémités sont
confondues (on parlera de circuit dans un graphe orienté).
B- Caractéristique d’un graphe
L’ordre d’un graphe est le nombre total de sommets de ce graphe.
Le degré d’un sommet est le nombre d’arêtes reliant ce sommet.
Le degré d’un graphe est donné par la valeur maximale
du degré des sommets.
Dans le cas spécifique d’un sommet à boucle, la boucle est comptée
pour deux fois lors du calcul du degré de ce sommet.
Exemple
Soit le graphe ci-dessus.
- Préciser l’ordre et le nombre d’arêtes.
- Pour chaque sommet, préciser le degré.
- Donner le degré du graphe.
C- Propriété
Dans un graphe simple, la somme totale des degrés de tous les sommets
est égale au double du nombre d’arêtes.
Exercice d’application 1
Soit $G$ le graphe ci-dessus défini par $G=\{5,8\}$.
- Calculer le degré de chaque sommet.
- Déduire le degré du graphe.
- Donner par calcul le nombre d’arêtes.
Exercice d’application 2
Lors d’une rencontre de 6 amis où tous se sont échangés des poignées de main
en guise de salutation :
-
Faire un graphique représentant la situation
(en considérant les amis comme sommets et les salutations comme arêtes).
- Déterminer le degré de chaque sommet.
- Vérifier que la somme des degrés est de 30.
- Déduire le nombre de salutations faites entre les 6 amis.
D- Type de graphe
Un graphe simple est un graphe qui ne contient pas de boucle
et pas d’arêtes multiples.
Un graphe complet est un graphe dans lequel tous les sommets
sont adjacents.
Exemple de graphe complet
Un graphe orienté est un graphe dans lequel chaque arête a un
sens de parcours (matérialisé par une flèche).
Exemple de graphe orienté
Un graphe est dit connexe lorsque pour tout sommet
$S_i$ et $S_j$, il existe toujours un chemin reliant les sommets
$S_i$ et $S_j$.
Exemple de graphe connexe
Un graphe est dit stable lorsque tous ses sommets ne sont
reliés par aucune arête.
Exercice 1
Sur le plan ci-dessus, les points $A$, $B$, $D$ et $E$ sont des sites où
l’électricité doit poser de l’éclairage de couleur
(sommets) comme décoration durant le concert et interconnecter par des fils
(arêtes). Le plan d’opération voudrait qu’un fil électrique ne connecte pas
des lampes de même couleur.
Combien de couleurs faut-il prévoir au minimum ?
Exercice 2
Une chaîne de diffusion de match de football souhaite diffuser les matchs de
première league anglaise de football ayant 20 équipes au départ telle que
les matchs doivent se jouer en aller-retour et toutes les équipes doivent
s’affronter.
Les droits de diffusion sont fixés à 20 000 francs
le match diffusé. En cas de versement caché pour une diffusion totale,
une réduction de 15 % est possible.
-
Aidez cette chaîne à évaluer le coût pour uniquement la diffusion des
matchs aller.
-
Aidez cette chaîne à évaluer le coût pour une diffusion totale
(des matchs aller-retour).
